堆

22 September 2021 - 2 mins read time
Tags: 基础知识学习

优先队列

概念：为元素指定优先级，优先级高的元素最先得到服务；优先级相同的元素按照其在队列中的顺序得到服务。

堆

堆不是优先队列，堆是优先队列的一种实现方式。

使用数组或链表无法保证插入和删除的时间复杂度为\(O(1)\), 使用堆可以保证时间复杂度为\(O(logN)\)。

定义：

完全二叉树；

每个节点的值都大于等于或小于等于其孩子结点的值；

特点：

可以在 $$ O(logN) $$的时间复杂度内完成插入操作；

可以在 $$ O(logN) $$的时间复杂度内完成删除操作；

可以在 $$ O(1) $$ 的时间复杂度内获取堆中的最大值或最小值。

分类：最大堆和最小堆。

最大堆：堆中每个节点的值都大于等于其孩子节点的值，堆顶元素是堆中的最大值。

最小堆：堆中每个节点的值都小于等于其孩子结点的值，堆顶元素是堆中的最小值。

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

void main() {
    vector<int> v{ 10, 20, 30, 5, 15 };

    // make_heap实现

    // 创建堆
    make_heap(v.begin(), v.end());
    cout << "initial max heap: " << v.front() << endl;

    // 插入元素
    v.push_back(99);
    push_heap(v.begin(), v.end());
    cout << "max heap after push: " << v.front() << endl;

    // 删除元素
    pop_heap(v.begin(), v.end());
    v.pop_back();
    cout << "max heap after pop: " << v.front() << endl;

    // 获取长度
    cout << v.size() << endl;

    // priority_queue实现

    // 构造空的优先队列，此时默认为最大堆
    priority_queue<int> big_heap;

    // 另一种构造最大堆的方法
    // greater和less是std实现的两个仿函数，其在类中实现了operator()，使得类具有了函数行为
    priority_queue<int, vector<int>, less<int>> big_heap2;

    // 构造最小堆
    priority_queue<int, vector<int>, greater<int>> small_heap;

    for (int i = 0; i < 10; i++) {
        big_heap.push(i);
        small_heap.push(i);
    }

    while (!big_heap.empty()) {
        cout << big_heap.top() << " ";
        big_heap.pop();
    }
    cout << endl;

    while (!small_heap.empty()) {
        cout << small_heap.top() << " ";
        small_heap.pop();
    }
    cout << endl;

    priority_queue<string> a;

    a.push("abc");
    a.push("abcd");
    a.push("dc");
 
    while (!a.empty()) {
        cout << a.top() << " ";
        a.pop();
    }
    cout << endl;

    return;
}