堆（Heap）的原理与C++实现

1. 什么是堆？

堆（Heap）是一种特殊的树形数据结构，通常用于实现优先队列。堆可以分为两种类型：

最大堆（Max Heap）：每个节点的值都大于或等于其子节点的值。
最小堆（Min Heap）：每个节点的值都小于或等于其子节点的值。

堆通常是一个完全二叉树，这意味着除了最后一层，其他层都是完全填满的，并且最后一层的节点都尽可能地靠左排列。

2. 堆的性质

完全二叉树：堆是一个完全二叉树，这意味着它可以用数组来高效地表示。
堆序性质：在最大堆中，父节点的值总是大于或等于其子节点的值；在最小堆中，父节点的值总是小于或等于其子节点的值。

Tips: 堆是`完全二叉树`，并非`二叉搜索树`

在数据结构中，完全二叉树和二叉搜索树是两种常见的树形结构，它们虽然都属于二叉树的范畴，但在定义、性质和应用场景上有显著的区别。下面我们将详细分析它们的区别。

特性	完全二叉树	二叉搜索树
定义	节点从上到下、从左到右依次填充	左子树 < 根节点 < 右子树
有序性	不一定有序	中序遍历结果有序
结构要求	必须是完全填充的（最后一层靠左）	无特殊结构要求，只需满足有序性
查找效率	不支持高效查找	支持高效查找（平衡时 O(log n)）
插入和删除	通常用于堆操作，不支持动态插入删除	支持动态插入和删除
应用场景	堆、优先队列	查找、排序、数据库索引
数组表示	可以用数组高效表示	通常用指针或引用表示

完全二叉树示例

节点从上到下、从左到右依次填充。
最后一层的节点靠左排列。

二叉搜索树示例

        10
       /  \
      5    15
     / \   / \
    2   7 12 20

左子树的所有节点值小于根节点，右子树的所有节点值大于根节点。
中序遍历结果为 [2, 5, 7, 10, 12, 15, 20]，是一个有序序列。

3. 堆的操作

堆的主要操作包括：

插入（Insert）：将一个新元素插入堆中，并保持堆的性质。
删除（Delete）：删除元素，并保持堆的性质。
查询（Query）：查询堆顶元素
构建堆（Build Heap）：将一个无序数组构建成一个堆。

4. 堆的实现

堆通常使用数组来实现。在从数组下标0开始存储的堆，对于一个索引为 i 的节点：

其父节点的索引为 (i - 1) / 2
其左子节点的索引为 2 * i + 1
其右子节点的索引为 2 * i + 2

4.1 堆的性质维护

堆的插入过程

假设我们有一个最大堆，初始堆为：[100, 19, 36, 17, 3, 25, 1, 2, 7]，其对应的完全二叉树结构如下（用数组表示）：

        100
      /     \
    19       36
   /  \     /  \
  17   3   25   1
 / \
2  7

插入一个新元素40
将新元素添加到堆的末尾：堆的数组表示为 [100, 19, 36, 17, 3, 25, 1, 2, 7, 40]，对应的完全二叉树结构如下：

     100
    /      \
   19      36
  /   \    / \
 17    3  25  1
/ \    /
2  7  40

向上调整（上浮）：从新插入的节点开始，与其父节点比较。如果当前节点的值大于父节点的值，则交换它们的位置。

40 的父节点是 3，40 > 3，交换它们的位置：

        100
      /      \
     19       36
    /  \     /  \
   17   40  25   1
  / \   /
 2  7  3

40 的新父节点是 19，40 > 19，交换它们的位置：

      100
    /      \
   40       36
  /  \     /  \
17   19  25   1
/ \   /
2  7 3

40 的新父节点是 100，40 < 100，停止调整。
最终，插入 40 后的堆为：[100, 40, 36, 17, 19, 25, 1, 2, 7, 3]。

总结:堆在插入元素后，需要进行上浮（up）操作，是不断与父节点比较，若父节点小于当前节点，则交换位置。具体代码实现示例如下：

//存储下标从1开始，以大根堆为例
void heap_up(int idx){
    while(idx != 1){
        int parent = idx >> 1;
        if(heap[parent] < heap[idx]){
            swap(heap[parent], heap[idx]);
            idx = parent;
        }
        else{
            break;
        }
    }
}

堆的删除过程

假设我们从上述堆中删除最大值（堆顶元素 100）。

将堆顶元素与最后一个元素交换：交换 100 和 3 的位置，得到 [3, 40, 36, 17, 19, 25, 1, 2, 7, 100]，然后删除最后一个元素（100），得到 [3, 40, 36, 17, 19, 25, 1, 2, 7]。这是因为我们在用数组存储堆的时候，头部元素的删除面临整个数组的移动，相当消耗计算资源，于是我们选择将头部元素和尾部元素进行交换，进行删除尾部，再调整堆
向下调整（下沉）：从堆顶开始，比较当前节点与其子节点的值，将当前节点与较大的子节点交换，直到满足堆的性质。

当前堆顶是 3，其子节点是 40 和 36，40 > 36，选择 40 与 3 交换得到：

      40
    /      \
   3       36
  /  \     /  \
17   19  25   1
/ \  
2  7

3 的新位置是左子树的根，其子节点是 17 和 19，19 > 17，选择 19 与 3 交换：

      40
    /      \
   19       36
  /  \     /  \
17   3  25   1
/ \  
2  7

最终，删除 100 后的堆为：[40, 19, 36, 17, 3, 25, 1, 2, 7]。

void heap_down(int idx){
    int size = top;
    while(1){
        int leftChild = idx * 2;
        int rightChild = idx * 2 + 1;
        int largest = idx;
        if(leftChild < size && heap[largest] < heap[leftChild]){
            largest = leftChild;
        }
        if(rightChild < size && heap[largest] < heap[rightChild]){
            largest = rightChild;
        }
        if (largest != idx) {
            swap(heap[idx], heap[largest]);
            idx = largest;
        } else {
            break;
        }
    }
}

4.2 C++ 实现最大堆

这里展示一个封装成对象的大根堆

#include <iostream>
#include <vector>
#include <algorithm>

class MaxHeap {
private:
    std::vector<int> heap;

    void heapifyUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap[index] > heap[parentIndex]) {
                std::swap(heap[index], heap[parentIndex]);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    void heapifyDown(int index) {
        int size = heap.size();
        while (true) {
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            int largest = index;

            if (leftChild < size && heap[leftChild] > heap[largest]) {
                largest = leftChild;
            }
            if (rightChild < size && heap[rightChild] > heap[largest]) {
                largest = rightChild;
            }

            if (largest != index) {
                std::swap(heap[index], heap[largest]);
                index = largest;
            } else {
                break;
            }
        }
    }

public:
    void insert(int value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }

    int extractMax() {
        if (heap.empty()) {
            throw std::out_of_range("Heap is empty");
        }
        int maxValue = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
        return maxValue;
    }

    void buildHeap(const std::vector<int>& array) {
        heap = array;
        for (int i = (heap.size() / 2) - 1; i >= 0; --i) {
            heapifyDown(i);
        }
    }

    void printHeap() const {
        for (int value : heap) {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }
};

int main() {
    MaxHeap maxHeap;
    maxHeap.insert(10);
    maxHeap.insert(20);
    maxHeap.insert(15);
    maxHeap.insert(30);
    maxHeap.insert(40);

    std::cout << "Max Heap: ";
    maxHeap.printHeap();

    std::cout << "Extracted Max: " << maxHeap.extractMax() << std::endl;
    std::cout << "Max Heap after extraction: ";
    maxHeap.printHeap();

    std::vector<int> array = {5, 3, 8, 1, 9};
    maxHeap.buildHeap(array);
    std::cout << "Max Heap built from array: ";
    maxHeap.printHeap();

    return 0;
}

4.2 代码解析

heapifyUp：用于在插入新元素后，从下往上调整堆，确保堆的性质。
heapifyDown：用于在删除堆顶元素后，从上往下调整堆，确保堆的性质。
insert：将新元素插入堆中，并调用 heapifyUp 进行调整。
extractMax：删除并返回堆顶元素，然后调用 heapifyDown 进行调整。
buildHeap：将一个无序数组构建成一个堆。

5. 堆的应用

优先队列：堆是实现优先队列的理想数据结构，因为可以快速获取和删除最大或最小元素。
堆排序：堆排序是一种基于堆的比较排序算法，时间复杂度为 O(n log n)。
Dijkstra算法：在图的单源最短路径算法中，堆用于高效地选择下一个要处理的节点。

6. 总结

堆是一种非常高效的数据结构，特别适用于需要频繁获取最大或最小元素的场景。通过数组实现堆，可以充分利用其完全二叉树的性质，使得插入、删除和构建堆的操作都能在 O(log n) 的时间内完成。

7.练习

ACWing模拟堆
这个题相较普通的堆，增添了一个需要维护的对象，就是这个数字是第几次插入的。所以我们需要额外维护两个数组pos和inv_pos，分别表示第k个插入的数在堆数组中的索引，和堆数组中第i个数是第几个插入的，完整代码如下：

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int maxn = 1e5 + 7;
int heap[maxn], top;
int pos[maxn], inv_pos[maxn];
void heap_swap(int a, int b){
    swap(heap[a], heap[b]);
    swap(pos[inv_pos[a]], pos[inv_pos[b]]);
    swap(inv_pos[a], inv_pos[b]);
}
void down(int idx){
    while(1){
        int leftChild = idx * 2;
        int rightChild = idx * 2 + 1;
        int smallest = idx;
        if(leftChild <= top && heap[leftChild] < heap[smallest])
            smallest = leftChild;
        if(rightChild <= top && heap[rightChild] < heap[smallest])
            smallest = rightChild;
        if(idx != smallest) {
            heap_swap(idx, smallest);
            idx = smallest;
        }
        else
            break;
    }
}
void up(int idx){
    while(idx != 1){
        int parent = idx >> 1;
        if(heap[parent] > heap[idx]){
            heap_swap(idx, parent);
            idx = parent;
        }
        else{
            break;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    string op;
    int x, k, cnt = 0;
    while(n--){
        cin>>op;
        if(op == "I"){
            cin>>x;
            heap[++top] = x;
            pos[++cnt] = top;
            inv_pos[top] = cnt;
            up(top);
        }
        else if(op == "PM"){
            cout<<heap[1]<<endl;
        }
        else if(op == "DM"){
            heap_swap(1, top);
            top--;
            down(1);
        }
        else if(op == "D"){
            cin>>k;
            int now = pos[k];
            heap_swap(now, top);
            top --;
            down(now);
            up(now);
        }
        else if(op == "C"){
            cin>>k>>x;
            heap[pos[k]] = x;
            up(pos[k]);
            down(pos[k]);
        }
    }
    return 0;
}