信息学竞赛模板（三）— 二叉堆

二叉堆

二叉堆是一种支持插入、删除、查询最值的数据结构，是一棵满足“堆性质”的完全二叉树。

最大堆（大根堆）

任意一个节点的权值都比其父节点要小。

在c++ STL中的使用方法：

priority_queue<int> heap;	//默认
priority_queue<int, vector<int>, less<int>> heap;	//降序排列，大根堆

最小堆（小根堆）

任意一个节点的权值都比起父节点要大。

在c++ STL中的使用方法：

priority_queue<int, vector<int>, greater<int>> heap; //升序排列，小根堆

自定义结构实现

struct Node{
    int x, y;
};

struct cmp{
    bool operator()(const Node &a, const Node &b){
        return a.x + a.y < b.x + b.y; //Node的 x 与 y 的和大的节点为根节点
        retrun a.x + a.y > b.x + b.y; //Node的 x 与 y 的和小的节点为根节点
    }
};

void func(){
    priority_queue<Node, vector<Node>, cmp> heap;
}

代码实现

#include<iostream>

using namespace std;

/**
 * 最大堆
 */
class MAX_HEAP {
private:
    int heap[100000];
    int n = 0;

    void up(int p) {    //向上移动位置 p 的元素
        while (p > 1) {
            if (heap[p] > heap[p / 2]) {
                swap(heap[p], heap[p / 2]);
                p /= 2;
            } else break;
        }
    }

    void down(int p) {  //向下移动位置 p 的元素
        int s = p * 2;  //p的左子节点
        while (s <= n) {
            if (s < n && heap[s] < heap[s + 1]) s++;    //选左右子节点中最大的
            if (heap[s] > heap[p]) {
                swap(heap[s], heap[p]);
                p = s, s = p * 2;
            } else break;
        }
    }

public:
    void insert(int val) {  //插入值
        heap[++n] = val;    //放到数组最后一个位置，即二叉堆最后一个位置
        up(n);
    }

    void extract() {    //移除堆顶的最值元素
        if (isEmpty()) return;
        heap[1] = heap[n--];
        down(1);
    }

    int getTop() {      //返回最值
        return heap[1];
    }

    bool isEmpty() {    //判断当前堆是否为空
        return n == 0;
    }
};

/**
 * 最小堆
 */
class MIN_HEAP {
private:
    int heap[100000];
    int n = 0;

    void up(int p) {    //向上移动位置 p 的元素
        while (p > 1) {
            if (heap[p] < heap[p / 2]) {
                swap(heap[p], heap[p / 2]);
                p /= 2;
            } else break;
        }
    }

    void down(int p) {  //向下移动位置 p 的元素
        int s = p * 2;  //p的左子节点
        while (s <= n) {
            if (s < n && heap[s] > heap[s + 1]) s++;    //选左右子节点中最小的
            if (heap[s] < heap[p]) {
                swap(heap[s], heap[p]);
                p = s, s = p * 2;
            } else break;
        }
    }

public:
    void insert(int val) {  //插入值
        heap[++n] = val;    //放到数组最后一个位置，即二叉堆最后一个位置
        up(n);
    }

    void extract() {    //移除堆顶的最值元素
        if (isEmpty()) return;
        heap[1] = heap[n--];
        down(1);
    }

    int getTop() {      //返回最值
        return heap[1];
    }

    bool isEmpty() {    //判断当前堆是否为空
        return n == 0;
    }
};

int main() {
    int a[] = {2, 5, 6, -1, 7, 3, 8, -10};
    int k = sizeof(a) / sizeof(int);

    MIN_HEAP heap;
    for (int i = 0; i < k; ++i) {
        heap.insert(a[i]);
        cout << heap.getTop() << endl;
    }
    cout << endl;
    while (!heap.isEmpty()) {
        cout << heap.getTop() << endl;
        heap.extract();
    }

    return 0;
}

输出

2
2
2
-1
-1
-1
-1
-10

-10
-1
2
3
5
6
7
8