常见数据结构-堆

堆详解：树的形，数组的心

深入理解堆的内部原理和手写实现

---

什么是堆

堆（Heap）是一种特殊的完全二叉树，满足堆性质：每个节点的值都大于等于（或小于等于）其子节点的值。

核心特点：用数组存储的完全二叉树，动态维护最值

两种堆

graph LR
    A[堆] --> B[最大堆 Max Heap]
    A --> C[最小堆 Min Heap]
    
    B --> B1[父节点 ≥ 子节点]
    B --> B2[根节点最大]
    
    C --> C1[父节点 ≤ 子节点]
    C --> C2[根节点最小]
    
    style A fill:#FFE4B5
    style B fill:#FF6B6B
    style C fill:#87CEEB

最大堆示例

     9            数组表示：[9, 7, 8, 3, 5, 6, 2]
   /   \          
  7     8         索引关系：
 / \   / \        - 父节点 i
3   5 6   2       - 左子节点 2i + 1
                  - 右子节点 2i + 2

最小堆示例

     1            数组表示：[1, 3, 2, 7, 5, 6, 8]
   /   \          
  3     2         特点：
 / \   / \        - 完全二叉树
7   5 6   8       - 父 ≤ 子

---

为什么用数组存储

完全二叉树的性质

完全二叉树可以用数组紧凑存储，不浪费空间：

        0
      /   \
     1     2
    / \   / \
   3   4 5   6

数组：[0, 1, 2, 3, 4, 5, 6]

索引计算公式

对于索引为 i 的节点：

关系	公式	说明
父节点	(i - 1) / 2	向下取整
左子节点	2 * i + 1	-
右子节点	2 * i + 2	-
是否有左子	2 * i + 1 < size	判断是否越界
是否有右子	2 * i + 2 < size	判断是否越界
最后非叶子	size / 2 - 1	建堆时的起点

记忆技巧：从 0 开始索引，左子 = 2i+1，右子 = 2i+2

---

堆的核心操作

1. 上浮（Sift Up）

使用场景：插入新元素后，恢复堆性质

原理：新元素与父节点比较，若违反堆性质则交换，重复直到根节点或满足条件

最大堆插入 10：

步骤1: 插入到末尾          步骤2: 与父节点比较
         9                        9
       /   \                    /   \
      7     8       →          10    8
     / \   / \                / \   / \
    3   5 6   2  10          3   5 6   2  7
                ↑                         ↑
            新插入                     上浮一次

步骤3: 继续比较            步骤4: 完成
         10                      10
       /   \                    /   \
      9     8       →          9     8
     / \   / \                / \   / \
    3   5 6   2  7           3   5 6   2  7
    ↑                        
  上浮到根

代码实现：

void siftUp(vector<int>& heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        
        // 最大堆：子节点 > 父节点时上浮
        if (heap[index] > heap[parent]) {
            swap(heap[index], heap[parent]);
            index = parent;
        } else {
            break;
        }
    }
}

时间复杂度：O(log n)，最多上浮 h 层（h 为树高）

---

2. 下沉（Sift Down）

使用场景：删除堆顶后，恢复堆性质

原理：用最后一个元素替换堆顶，然后与较大的子节点比较，若违反堆性质则交换，重复直到叶子节点或满足条件

最大堆删除堆顶：

步骤1: 用末尾替换堆顶      步骤2: 与子节点比较
         9                        2
       /   \                    /   \
      7     8       →          7     8
     / \   / \                / \   / 
    3   5 6   2              3   5 6
         删除 ↑                ↓
              2              下沉

步骤3: 交换并继续          步骤4: 完成
         7                        8
       /   \                    /   \
      2     8       →          7     6
     / \   /                  / \   / 
    3   5 6                  3   5 2
        ↓                              
      继续下沉                     稳定

代码实现：

void siftDown(vector<int>& heap, int index, int size) {
    while (2 * index + 1 < size) {  // 有左子节点
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int largest = index;
        
        // 找出父、左子、右子中最大的
        if (left < size && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < size && heap[right] > heap[largest]) {
            largest = right;
        }
        
        // 如果父节点最大，说明已满足堆性质
        if (largest == index) {
            break;
        }
        
        swap(heap[index], heap[largest]);
        index = largest;
    }
}

时间复杂度：O(log n)

---

3. 插入（Insert）

步骤：

1. 将新元素添加到数组末尾
2. 上浮调整

void insert(vector<int>& heap, int value) {
    heap.push_back(value);      // 添加到末尾
    siftUp(heap, heap.size() - 1);  // 上浮
}

时间复杂度：O(log n)

---

4. 删除堆顶（Extract Max/Min）

步骤：

1. 记录堆顶元素
2. 用最后一个元素替换堆顶
3. 删除最后一个元素
4. 下沉调整

int extractMax(vector<int>& heap) {
    if (heap.empty()) {
        throw runtime_error("Heap is empty");
    }
    
    int maxValue = heap[0];          // 记录最大值
    heap[0] = heap.back();           // 用末尾替换堆顶
    heap.pop_back();                 // 删除末尾
    
    if (!heap.empty()) {
        siftDown(heap, 0, heap.size());  // 下沉
    }
    
    return maxValue;
}

时间复杂度：O(log n)

---

5. 建堆（Build Heap）

方法1：自顶向下

逐个插入元素，每次插入后上浮调整。

vector<int> buildHeapTopDown(vector<int>& arr) {
    vector<int> heap;
    for (int num : arr) {
        insert(heap, num);  // O(log n) 插入
    }
    return heap;
}

时间复杂度：O(n log n)

---

方法2：自底向上（更优）

将数组看作完全二叉树，从最后一个非叶子节点开始，依次下沉调整。

原数组：[3, 2, 1, 7, 8, 4, 5]

步骤1：找最后非叶子节点 = size/2-1 = 2（值为1）
         3
       /   \
      2     1
     / \   / \
    7   8 4   5

步骤2：从索引2开始下沉
         3
       /   \
      2     5
     / \   / \
    7   8 4   1

步骤3：处理索引1
         3
       /   \
      8     5
     / \   / \
    7   2 4   1

步骤4：处理索引0（根节点）
         8
       /   \
      7     5
     / \   / \
    3   2 4   1

完成！最大堆构建完成

代码实现：

void buildHeap(vector<int>& heap) {
    int n = heap.size();
    
    // 从最后一个非叶子节点开始，向前遍历
    for (int i = n / 2 - 1; i >= 0; --i) {
        siftDown(heap, i, n);
    }
}

时间复杂度：O(n) 🎯

为什么是 O(n) 而不是 O(n log n)？

虽然每次下沉最坏是 O(log n)，但实际上：

• 叶子节点不需要下沉（占一半）
• 倒数第二层最多下沉 1 层（占 1/4）
• 倒数第三层最多下沉 2 层（占 1/8）
• …

总时间 = n/2 × 0 + n/4 × 1 + n/8 × 2 + … = O(n)

---

完整的堆类实现

class MaxHeap {
private:
    vector<int> heap;
    
    void siftUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[index] > heap[parent]) {
                swap(heap[index], heap[parent]);
                index = parent;
            } else {
                break;
            }
        }
    }
    
    void siftDown(int index) {
        int size = heap.size();
        while (2 * index + 1 < size) {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            int largest = index;
            
            if (left < size && heap[left] > heap[largest]) {
                largest = left;
            }
            if (right < size && heap[right] > heap[largest]) {
                largest = right;
            }
            
            if (largest == index) break;
            
            swap(heap[index], heap[largest]);
            index = largest;
        }
    }
    
public:
    MaxHeap() {}
    
    MaxHeap(vector<int> arr) : heap(arr) {
        // 建堆
        for (int i = heap.size() / 2 - 1; i >= 0; --i) {
            siftDown(i);
        }
    }
    
    void insert(int value) {
        heap.push_back(value);
        siftUp(heap.size() - 1);
    }
    
    int extractMax() {
        if (heap.empty()) {
            throw runtime_error("Heap is empty");
        }
        
        int maxValue = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        
        if (!heap.empty()) {
            siftDown(0);
        }
        
        return maxValue;
    }
    
    int getMax() const {
        if (heap.empty()) {
            throw runtime_error("Heap is empty");
        }
        return heap[0];
    }
    
    int size() const {
        return heap.size();
    }
    
    bool empty() const {
        return heap.empty();
    }
};

---

堆排序详解

算法思路

利用堆的性质进行排序：

1. 建堆：O(n)
2. 排序：依次取出堆顶（最大值），放到数组末尾

原数组：[3, 2, 1, 7, 8, 4, 5]

步骤1：建最大堆
[8, 7, 5, 3, 2, 4, 1]
 ↑ 最大值

步骤2：堆顶与末尾交换
[1, 7, 5, 3, 2, 4 | 8]
 ↑              已排序

步骤3：缩小堆范围并下沉调整
[7, 3, 5, 1, 2, 4 | 8]
 ↑              已排序

步骤4：重复
[4, 3, 5, 1, 2 | 7, 8]
[5, 3, 4, 1, 2 | 7, 8]
...
[1, 2, 3, 4, 5, 7, 8]  完成！

代码实现

void heapSort(vector<int>& nums) {
    int n = nums.size();
    
    // 1. 建堆（从最后一个非叶子节点开始）
    for (int i = n / 2 - 1; i >= 0; --i) {
        heapify(nums, n, i);
    }
    
    // 2. 排序（依次取出堆顶）
    for (int i = n - 1; i > 0; --i) {
        swap(nums[0], nums[i]);   // 堆顶与末尾交换
        heapify(nums, i, 0);       // 调整堆
    }
}

void heapify(vector<int>& nums, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && nums[left] > nums[largest]) {
        largest = left;
    }
    if (right < n && nums[right] > nums[largest]) {
        largest = right;
    }
    
    if (largest != i) {
        swap(nums[i], nums[largest]);
        heapify(nums, n, largest);
    }
}

复杂度分析

• 时间复杂度：O(n log n)
  • 建堆：O(n)
  • n-1 次调整，每次 O(log n)
• 空间复杂度：O(1) 原地排序
• 稳定性：❌ 不稳定

堆排序的优缺点

优点	缺点
✅ 时间复杂度稳定	❌ 不稳定排序
✅ 原地排序，空间 O(1)	❌ 缓存不友好
✅ 不依赖输入分布	❌ 实际性能不如快排

---

堆 vs 其他数据结构

操作复杂度对比

数据结构	插入	删除最值	查看最值	查找任意元素
堆	O(log n)	O(log n)	O(1)	O(n)
无序数组	O(1)	O(n)	O(n)	O(n)
有序数组	O(n)	O(1)	O(1)	O(log n)
平衡二叉搜索树	O(log n)	O(log n)	O(log n)	O(log n)

堆的优势场景

graph LR
    A[什么时候用堆？] --> B[需要频繁获取最值]
    A --> C[不需要查找任意元素]
    A --> D[动态数据流]
    A --> E[Top K 问题]
    
    style A fill:#FFE4B5
    style B fill:#90EE90
    style E fill:#87CEEB

---

经典应用场景

1. Top K 问题

// 第 K 大元素
int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap;  // 最小堆
    
    for (int num : nums) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    
    return minHeap.top();
}

2. 合并 K 个有序链表/数组

vector<int> mergeKSorted(vector<vector<int>>& arrays) {
    auto cmp = [](tuple<int,int,int>& a, tuple<int,int,int>& b) {
        return get<0>(a) > get<0>(b);  // 最小堆
    };
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, decltype(cmp)> minHeap(cmp);
    
    // 初始化：每个数组的第一个元素
    for (int i = 0; i < arrays.size(); ++i) {
        if (!arrays[i].empty()) {
            minHeap.push({arrays[i][0], i, 0});
        }
    }
    
    vector<int> result;
    while (!minHeap.empty()) {
        auto [val, arrIdx, elemIdx] = minHeap.top();
        minHeap.pop();
        result.push_back(val);
        
        // 加入下一个元素
        if (elemIdx + 1 < arrays[arrIdx].size()) {
            minHeap.push({arrays[arrIdx][elemIdx + 1], arrIdx, elemIdx + 1});
        }
    }
    
    return result;
}

3. 数据流中位数

class MedianFinder {
private:
    priority_queue<int> maxHeap;  // 较小的一半
    priority_queue<int, vector<int>, greater<int>> minHeap;  // 较大的一半
    
public:
    void addNum(int num) {
        maxHeap.push(num);
        minHeap.push(maxHeap.top());
        maxHeap.pop();
        
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }
    
    double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.top();
        }
        return (maxHeap.top() + minHeap.top()) / 2.0;
    }
};

---

最大堆 vs 最小堆

何时使用？

graph TD
    A[选择堆类型] --> B{需要什么？}
    
    B -->|最大值| C[最大堆]
    B -->|最小值| D[最小堆]
    
    C --> E[直接获取]
    D --> F[直接获取]
    
    style A fill:#FFE4B5
    style C fill:#FF6B6B
    style D fill:#87CEEB

Top K 问题口诀

求大用小，求小用大

问题	使用的堆	原因
第 K 大元素	最小堆	保留最大的 K 个
第 K 小元素	最大堆	保留最小的 K 个
前 K 大	最小堆	淘汰小的，保留大的
前 K 小	最大堆	淘汰大的，保留小的

代码转换

// 最大堆（默认）
priority_queue<int> maxHeap;

// 最小堆（需要指定比较器）
priority_queue<int, vector<int>, greater<int>> minHeap;

// 自定义比较器
auto cmp = [](int a, int b) { return a > b; };  // 最小堆
priority_queue<int, vector<int>, decltype(cmp)> customHeap(cmp);

---

堆的变种

1. 二叉堆（Binary Heap）

我们刚才讲的就是二叉堆，最常用。

2. 斐波那契堆（Fibonacci Heap）

• 优点：合并操作 O(1)
• 缺点：实现复杂，常数因子大
• 应用：Dijkstra、Prim 算法的优化版本

3. 二项堆（Binomial Heap）

• 特点：多个二项树组成
• 应用：理论研究

---

常见陷阱与技巧

陷阱1：索引计算错误

// ❌ 错误：从1开始索引
int parent = i / 2;      // 不适用于从0开始的数组

// ✅ 正确：从0开始索引
int parent = (i - 1) / 2;
int left = 2 * i + 1;
int right = 2 * i + 2;

陷阱2：比较器方向搞反

// C++ priority_queue 的比较器与 sort 相反！

// 最小堆（堆顶最小）
auto cmp = [](int a, int b) { return a > b; };  // 注意是 >

// 最大堆（堆顶最大）
auto cmp = [](int a, int b) { return a < b; };  // 注意是 <

技巧1：建堆优化

// ❌ 低效：逐个插入 O(n log n)
for (int num : nums) {
    minHeap.push(num);
}

// ✅ 高效：批量建堆 O(n)
priority_queue<int> maxHeap(nums.begin(), nums.end());

技巧2：记住口诀

• 求大用小，求小用大
• 父节点 = (i-1)/2
• 左子 = 2i+1，右子 = 2i+2

---

思维导图

graph TD
    A[堆] --> B[基本概念]
    A --> C[核心操作]
    A --> D[应用场景]
    A --> E[经典算法]
    
    B --> B1[完全二叉树]
    B --> B2[数组存储]
    B --> B3[最大堆/最小堆]
    
    C --> C1[上浮 O log n]
    C --> C2[下沉 O log n]
    C --> C3[插入 O log n]
    C --> C4[删除堆顶 O log n]
    C --> C5[建堆 O n]
    
    D --> D1[Top K 问题]
    D --> D2[优先队列]
    D --> D3[堆排序]
    D --> D4[数据流统计]
    
    E --> E1[堆排序]
    E --> E2[Dijkstra]
    E --> E3[Huffman编码]
    
    style A fill:#FFE4B5
    style C fill:#87CEEB
    style D fill:#90EE90

---

总结

核心要点

1. 堆 = 完全二叉树 + 数组存储
2. 两个关键操作：上浮、下沉
3. 建堆优化：自底向上 O(n)
4. Top K 口诀：求大用小，求小用大

时间复杂度总结

操作	时间复杂度	备注
插入	O(log n)	上浮
删除堆顶	O(log n)	下沉
查看堆顶	O(1)	直接访问
建堆	O(n)	自底向上
堆排序	O(n log n)	n 次删除堆顶

代码模板

// 最大堆核心操作
class MaxHeap {
    // 上浮
    void siftUp(int i) {
        while (i > 0 && heap[i] > heap[(i-1)/2]) {
            swap(heap[i], heap[(i-1)/2]);
            i = (i - 1) / 2;
        }
    }
    
    // 下沉
    void siftDown(int i) {
        while (2*i+1 < size) {
            int j = 2*i+1;  // 左子
            if (j+1 < size && heap[j+1] > heap[j]) j++;  // 右子更大
            if (heap[i] >= heap[j]) break;
            swap(heap[i], heap[j]);
            i = j;
        }
    }
};

推荐练习：

• LeetCode 215 - 数组中的第K个最大元素
• LeetCode 347 - 前K个高频元素
• LeetCode 295 - 数据流的中位数
• LeetCode 23 - 合并K个升序链表

推荐阅读：

• 《算法导论》第6章：堆排序
• LeetCode 堆专题