C++中的堆和优先队列

1. 什么是堆？

堆是一种数据结构，它可以把最大或最小值放在根节点上。堆可以用数组、指针或完全二叉树来实现。堆可以有多个元素相同的节点，但它们的顺序和父节点、子节点的关系是明确的。

堆可以分为最大堆和最小堆，它们的规则分别是：最大堆的任何父节点的值都大于或等于它的子节点的值，最小堆的任何父节点的值都小于或等于它的子节点的值。

1.1 堆的基本操作

堆的基本操作有插入、删除和查找。它们对应的时间复杂度为O(logN)。插入操作把元素放入堆中，删除操作从堆中删除元素，查找操作找到堆中的一个元素。

1.2 堆的实现方式

堆的底层实现方式有多种，通常使用数组或指针实现。数组实现堆时，可以把根节点放在数组的第一个位置，左子节点和右子节点可以放在数组的第二个和第三个位置上；指针实现堆时，则需要每个节点都包含左子节点和右子节点的指针。

// c++实现小根堆
#include 
#include 
#include 
using namespace std;
int main() {
    vector heap;
    heap.push_back(-1);
    heap.push_back(3);
    heap.push_back(2);
    heap.push_back(5);
    heap.push_back(8);
    heap.push_back(7);
    make_heap(heap.begin(), heap.end(), greater());
    for(int i = 0; i < heap.size(); i++) {
        cout << heap[i] << " ";
    }
    return 0;
}

2. 什么是优先队列？

优先队列是一种带权值的队列，其中每个元素都有一个优先级。在优先队列中，高优先级的元素先出队列，低优先级的元素后出队列。不同于普通队列，普通队列中元素的顺序是先进先出，而在优先队列中，元素的顺序是由优先级决定的。

2.1 优先队列的实现方式

优先队列的实现方式有多种，通常使用堆来实现。由于堆有很好的优先级性质，可以很方便地用来实现优先队列。

// c++ STL实现优先队列
#include 
#include 
using namespace std;
int main() {
    priority_queue, greater> q;
    q.push(1);
    q.push(5);
    q.push(3);
    while(!q.empty()) {
        cout << q.top() << endl;
        q.pop();
    }
    return 0;
}

3. 堆和优先队列的应用

堆和优先队列通常用于解决一些需要高效率地查询最大值或最小值的问题。例如，在数据结构中，堆可以用来实现优先队列，它可以用来实现Dijkstra算法、Prim算法等。堆还可以用来排序，例如堆排序；在操作系统中，堆可以用来实现内存管理机制；在并发处理中，堆可以用来实现优先级调度。

3.1 堆排序

堆排序是典型的运用堆的排序算法，可以用堆来提升快速排序等排序算法的效率。堆排序可以稳定地排序，时间复杂度为O(nlogn)。

void heapSort(int arr[], int n) {
    // 建堆,从最后一个非叶子结点开始往前建堆
    for (int i = (n - 1) / 2; i >= 0; i--) {
        adjustDown(arr, n, i);
    }
    // 排序
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        adjustDown(arr, i, 0);
    }
}
void adjustDown(int arr[], int n, int i) {
    int temp = arr[i];
    int lchild = 2 * i + 1;
    while (lchild < n) {
        if (lchild + 1 < n && arr[lchild + 1] > arr[lchild]) {
            lchild++;
        }
        if (arr[lchild] > temp) {
            arr[i] = arr[lchild];
            i = lchild;
            lchild = 2 * i + 1;
        }
        else {
            break;
        }
    }
    arr[i] = temp;
}

3.2 最长连续子序列问题

最长连续子序列问题是一道经典的算法问题。我们需要找到一个序列中最长的连续子序列，时间复杂度最好为O(n)。这里用堆来实现。

#include 
#include 
#include 
#include 
using namespace std;
int longestConsecutive(vector& nums) {
    unordered_map used;
    for (auto i : nums) used[i] = false;
    int longest = 0;
    priority_queue, greater> pq;
    for (auto i : nums) {
        if (used[i]) continue;
        used[i] = true;
        int length = 1;
        pq.push(i);
        while (!pq.empty()) {
            int j = pq.top(); pq.pop();
            if (used.find(j - 1) != used.end() && !used[j - 1]) {
                used[j - 1] = true;
                pq.push(j - 1);
                length++;
            }
            if (used.find(j + 1) != used.end() && !used[j + 1]) {
                used[j + 1] = true;
                pq.push(j + 1);
                length++;
            }
        }
        longest = max(longest, length);
    }
    return longest;
}
int main(){
    vector nums;
    nums.push_back(100);
    nums.push_back(4);
    nums.push_back(200);
    nums.push_back(1);
    nums.push_back(3);
    nums.push_back(2);
    cout<
    return 0;
}