GabWiki

Appearance

堆 ​

模板题：堆排序、模拟堆

C++
// h存储堆中的值, h[1]是堆顶, x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b) {
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int k) {
    int min = k;
    if (k * 2 <= size && h[k * 2] < h[min]) min = k * 2;
    if (k * 2 + 1 <= size && h[k * 2 + 1] < h[min]) min = k * 2 + 1;
    if (k != min) {
        heap_swap(min, k);
        down(min);
    }
}

void up(int k) {
    while (k / 2 > 0 && h[k] < h[k / 2]) {
        heap_swap(k, k / 2);
        k /= 2;
    }
}

// O(n)时间把数组建成堆
for (int i = n / 2; i > 0; --i) down(i);
// h存储堆中的值, h[1]是堆顶, x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b) {
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int k) {
    int min = k;
    if (k * 2 <= size && h[k * 2] < h[min]) min = k * 2;
    if (k * 2 + 1 <= size && h[k * 2 + 1] < h[min]) min = k * 2 + 1;
    if (k != min) {
        heap_swap(min, k);
        down(min);
    }
}

void up(int k) {
    while (k / 2 > 0 && h[k] < h[k / 2]) {
        heap_swap(k, k / 2);
        k /= 2;
    }
}

// O(n)时间把数组建成堆
for (int i = n / 2; i > 0; --i) down(i);

Java API ​

Java API 中 PriorityQueue 默认是小根堆

Java
import java.util.*;

Queue<Integer> minHeap = new PriorityQueue<>(); // 小根堆
Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); // 大根堆
import java.util.*;

Queue<Integer> minHeap = new PriorityQueue<>(); // 小根堆
Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); // 大根堆

C++ STL ​

C++ STL 中 priority_queue 默认是大根堆

C++
#include <queue>

priority_queue<int, vector<int>, greater<int>> min_heap; // 小根堆
priority_queue<int> max_heap; // 大根堆
#include <queue>

priority_queue<int, vector<int>, greater<int>> min_heap; // 小根堆
priority_queue<int> max_heap; // 大根堆

自定义结构体重写排序规则示例 ​

C++
struct Info {
    int x, y;
};

struct InfoCmp {
    bool operator()(const Info& a, const Info& b) const {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y
    }
};

priority_queue<Info, vector<Info>, InfoCmp> pq;
struct Info {
    int x, y;
};

struct InfoCmp {
    bool operator()(const Info& a, const Info& b) const {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y
    }
};

priority_queue<Info, vector<Info>, InfoCmp> pq;