堆

ZaynPei Lv6
  2025-10-01 11:00 2025-10-01 11:00 Created   2025-10-30 20:51:23 2025-10-30 20:51:23 Updated      2.4k Words  9 Mins

堆 (Heap)

堆也称作优先队列, 是一种特殊的树形数据结构，满足堆性质：在最大堆中，父节点的值总是大于等于其子节点的值；在最小堆中，父节点的值总是小于等于其子节点的值。

在 C++ 中，可以使用标准库中的 std::priority_queue 来实现堆, 需要头文件 <queue>。默认情况下，std::priority_queue 实现的是最大堆。如果需要实现最小堆，可以通过自定义比较函数来实现: std::priority_queue<Type, std::vector<Type>, std::greater<Type>> minHeap;

函数签名: 

1
2
3
4
5
template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;
- T：堆中存储的元素类型。 - Container：底层容器类型，默认是 std::vector<T> - Compare：比较函数对象类型，默认是 std::less，用于实现最大堆。使用 std::greater 可以实现最小堆。

构造函数: - priority_queue()：默认构造函数，创建一个空堆。 - priority_queue(InputIt first, InputIt last)：使用范围 [first, last) 内的元素构造堆。

不能在构造函数中直接传入 n 来表示堆的大小，因为堆的大小是动态变化的，可以通过 push 和 pop 操作来调整。

标准库中的堆主要支持以下操作: - push(const Type& value)：将元素 value 插入堆中, 复杂度为 O(log n)。 - pop()：移除堆顶元素, 复杂度为 O(log n), 因为需要重新调整堆结构。 - top()：返回堆顶元素, 复杂度为 O(1)。 - empty()：检查堆是否为空。 - size()：返回堆中元素的数量。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <queue>
#include <vector>
#include <functional>  // 用于 std::greater
int main() {
    // 最大堆
    std::priority_queue<int> maxHeap;
    maxHeap.push(3);
    maxHeap.push(1);
    maxHeap.push(4);
    int maxTop = maxHeap.top();  // maxTop = 4
    maxHeap.pop();  // 移除最大元素 4

    // 最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    minHeap.push(3);
    minHeap.push(1);
    minHeap.push(4);
    int minTop = minHeap.top();  // minTop = 1
    minHeap.pop();  // 移除最小元素 1

    std::vector<int> nums = {5, 2, 8, 1, 3};
    std::priority_queue<int> heap(nums.begin(), nums.end());  // 使用范围构造函数初始化堆, 复杂度为 O(n), 比逐个push更高效

    return 0;
}

对顶堆 (Dual Heaps)

对顶堆是一种同时维护最大堆和最小堆的数据结构，常用于动态数据流中查找中位数等问题。通过将数据分为两部分，最大堆存储较小的一半元素，最小堆存储较大的一半元素，可以高效地获取中位数。

例如 LC295: 数据流的中位数, 实现一个支持以下两种操作的数据结构: - void addNum(int num) - 从数据流中添加一个整数到数据结构中。 - double findMedian() - 返回目前所有元素的中位数。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class MedianFinder {
private:
    priority_queue<int> maxHeap; // 存储较小一半的元素
    priority_queue<int, vector<int>, greater<int>> minHeap; // 存储较大一半的元素
public:
    MedianFinder() {}

    // 我们的目的是保持两个堆的大小尽量平衡, 即 maxHeap 的大小要么等于 minHeap, 要么比 minHeap 多 1
    void addNum(int num) {
        maxHeap.push(num);   // 在添加新元素时, 先将其添加到最大堆中
        minHeap.push(maxHeap.top());  // 然后将最大堆的堆顶元素移动到最小堆中(因为此时最大堆的堆顶可能大于最小堆的堆顶)
        maxHeap.pop();
        if(maxHeap.size()< minHeap.size()){ // 保持两个堆的大小平衡
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }
    
    double findMedian() {
        if(maxHeap.empty()) return 0;
        if(maxHeap.size()>minHeap.size()) return (double)maxHeap.top();  // 如果最大堆比最小堆多一个元素, 则中位数就是最大堆的堆顶
        else return (double)(maxHeap.top()+minHeap.top())/2;  // 否则中位数就是两个堆顶的平均值
        
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */
下面是 addNum 函数的详细步骤说明(先假定再平衡)

  1. 插入新元素到最大堆
    首先将 num 插入到 maxHeap，即 maxHeap.push(num);。此时，maxHeap 可能出现一个“叛徒”元素（即最大值），它实际上应该属于“后半部分”。

  2. 维护排序不变性
    将 maxHeap 的堆顶元素（最大值）移动到 minHeap：

    1
    2
    3
    int elementToMove = maxHeap.top();
    maxHeap.pop();
    minHeap.push(elementToMove);
    这样可以保证 maxHeap.top() <= minHeap.top()，即“排序不变性”得到满足。

  3. 维护平衡不变性
    经过前两步，maxHeap 和 minHeap 的元素数量可能失衡。需要检查并调整：

    1
    2
    3
    4
    5
    if (minHeap.size() > maxHeap.size()) {
         int elementToMoveBack = minHeap.top();
         minHeap.pop();
         maxHeap.push(elementToMoveBack);
    }
    这样可以保证 maxHeap.size() >= minHeap.size()，即“平衡不变性”得到满足。

总结：每次 addNum 操作的时间复杂度为 O(log N)。

堆中元素是pair

堆中的元素类型可以是 std::pair，这在需要根据多个属性进行排序时非常有用。堆的排序是基于 pair 的第一个元素进行的，如果第一个元素相等，则比较第二个元素。

例如LC347: 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq_map;
        for(const auto& num:nums){
            freq_map[num]++;
        }
        // num: freq
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> minHeap;
        for(const auto& pair: freq_map){
            int number = pair.first;
            int freq = pair.second;
            minHeap.push({freq, number});
            if(minHeap.size()>k){
                minHeap.pop();
            }
        }
        vector<int> ans;
        while(!minHeap.empty()){
            ans.push_back(minHeap.top().second);
            minHeap.pop();
        }
        return ans;
    }
};
这里我们的目的当然是要频率最高的 k 个元素, 因此我们使用了最小堆来维护当前频率最高的 k 个元素。但是如果堆中之存储频率的话, 那么当有多个元素频率相同的时候, 我们就无法区分到底是哪些元素了. 因此我们需要再堆中存储一个 pair, 不过在建立哈希表的时候, 我们是以 num 为 key, freq 为 value 的, 因此在插入堆的时候, 如果直接插入 {num, freq} 这样的话, 堆会根据 num 来排序, 这显然是不对的. 因此我们需要将 pair 的顺序反过来, 插入一个临时的 {freq, num}, 这样堆就会根据 freq 来排序了.

O(N) 建堆

堆的构建可以通过两种主要方法完成：逐个插入元素和使用“堆化”过程。逐个插入元素的时间复杂度为 O(N log N)，而使用堆化过程的时间复杂度为 O(N)。下面介绍如何使用堆化过程来高效地构建堆。

标准库中的 std::make_heap 函数, 以及构造函数中直接传入迭代器起始位置都是使用堆化的方法将一个范围内的元素转换为堆结构，时间复杂度为 O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void sift_down(std::vector<int>& heap, int n, int rootIndex) {
    // 步骤说明：将当前根节点视为最大值
    int largest = rootIndex; 
    
    // 步骤说明：计算左右子节点的索引 (0-based 索引)
    int leftChild = 2 * rootIndex + 1;
    int rightChild = 2 * rootIndex + 2;

    // 步骤说明：检查左子节点是否存在，并且是否大于当前最大值
    if (leftChild < n && heap[leftChild] > heap[largest]) {
        largest = leftChild;
    }

    // 步骤说明：检查右子节点是否存在，并且是否大于当前最大值
    if (rightChild < n && heap[rightChild] > heap[largest]) {
        largest = rightChild;
    }

    // 步骤说明：如果根节点不是最大的 (largest != rootIndex)
    if (largest != rootIndex) {
        // 步骤说明：将最大值交换到根节点
        std::swap(heap[rootIndex], heap[largest]);

        // 步骤说明：由于交换，原根节点的值被“下沉”到了 largest 位置，
        // 必须递归地对以 largest 为根的新子树继续执行下沉操作。
        sift_down(heap, n, largest);
    }
    // 否则，根节点已经是最大值，符合堆性质，停止操作。
}

void build_heap(std::vector<int>& arr) {
    int n = arr.size();
    
    // 步骤说明：找到最后一个非叶子节点。
    // 在 0-based 索引中，最后一个元素是 n-1，
    // 其父节点索引是 floor((n-1 - 1) / 2) = floor(n / 2) - 1。
    int lastParent = (n / 2) - 1;

    // 步骤说明：从最后一个非叶子节点开始，自底向上，
    // 依次对每个节点执行“下沉”操作。
    for (int i = lastParent; i >= 0; i--) {
        sift_down(arr, n, i);
    }
}

我们将一个数组（arr）视为一个“完全二叉树”。所有的叶子节点（在数组的后半部分，约 N/2 个）天然地满足堆的定义（因为它们没有子节点）。

我们从最后一个非叶子节点开始，向前遍历到根节点（arr[0]）。

  • 最后一个非叶子节点在数组中的索引是 (N/2) - 1。
  • 对遍历到的每个节点，执行一次 sift-down（下滤）操作。
    • sift-down 就是比较该节点与其子节点，如果不满足堆属性（例如最小堆中父节点比子节点大），就将它与较小的子节点交换，交换后，原节点 i 的值（现在位于 left或right 处）可能又小于了它新的子节点，因此必须递归地对 left 位置继续调用 sift_down

复杂度数学证明（O(N)）： - 假设堆的高度为 h（h ≈ log N）。 - 堆中高度为 0 的节点（即叶子节点）有 N/2 个。它们不需要下滤，工作量为 0。 - 堆中高度为 1 的节点（叶子的父节点）有 N/4 个。它们最多下滤 1 层。 - 堆中高度为 2 的节点有 N/8 个。它们最多下滤 2 层… - 堆中高度为 h 的节点（根节点）有 1 个。它最多下滤 h 层。 - 总工作量 S = (N/4 * 1) + (N/8 * 2) + (N/16 * 3) + … + (1 * h), 可以近似计算为 S ≈ N * (1/2 + 1/4 + 1/8 + … ) = N * 1 = O(N)。

On this page
堆
  1. 堆 (Heap)
    1. 对顶堆 (Dual Heaps)
    2. 堆中元素是pair
    3. O(N) 建堆