数据结构之堆（Heap）

---

一、堆的核心概念

1. 定义与性质

堆（Heap） 是一种特殊的完全二叉树数据结构，满足以下关键性质：

• 结构性：完全二叉树结构
  • 除最后一层外，其他层节点全满
  • 最后一层节点从左向右连续排列
• 有序性：
  • 最大堆（Max Heap）：∀i, arr[i] ≥ arr[2i+1] 且 arr[i] ≥ arr[2i+2]
  • 最小堆（Min Heap）：∀i, arr[i] ≤ arr[2i+1] 且 arr[i] ≤ arr[2i+2]

2. 存储方式

通过数组实现，利用完全二叉树的紧凑性：

索引关系（数组从0开始存储）：

• 父节点索引：parent(i) = (i-1)//2
• 左子节点：left(i) = 2i+1
• 右子节点：right(i) = 2i+2

存储示例：

       10              
      /  \             
     8    9           → 数组存储：[10,8,9,5,3,7,6]
    / \  / \          → 索引对应：0  1 2 3 4 5 6 
   5  3 7   6

---

二、核心操作与算法

1. 操作复杂度概览

操作	时间复杂度	空间复杂度	说明
插入元素	O(log n)	O(1)	最坏情况下调整到根节点
删除堆顶	O(log n)	O(1)	需要重建堆结构
查找极值	O(1)	O(1)	直接访问数组首元素
构建堆	O(n)	O(n)	Floyd算法优化
堆排序	O(n log n)	O(1)	原地排序

2. 关键操作详解

(1) 向上调整（Sift Up）

应用场景：插入新元素后维护堆性质

算法步骤：

1. 将新元素置于数组末尾
2. 与父节点比较：

   while index > 0:
       parent = (index-1) // 2
       if heap[parent] >= heap[index]: break
       swap(parent, index)
       index = parent
   

(2) 向下调整（Sift Down）

应用场景：删除堆顶后重建堆结构

算法步骤：

1. 堆顶元素与末尾交换
2. 删除末尾元素（原堆顶）
3. 逐层向下比较：

   void siftDown(vector<int>& heap, int index, int size) {
       while (true) {
           int left = 2 * index + 1;
           int right = 2 * index + 2;
           int target = index;
   
           if (left < size && heap[left] > heap[target])
               target = left;
           if (right < size && heap[right] > heap[target])
               target = right;
           
           if (target == index) break;
           swap(heap[index], heap[target]);
           index = target;
       }
   }
   

(3) Floyd建堆算法

优化原理：从最后一个非叶子节点（索引n/2-1）开始逆向调整

数学证明：

• 叶子节点数量 ≈ n/2，无需处理
• 总调整次数 = Σ(h-i)*2^i ≤ 2n → O(n)

// C++建堆实现
MaxHeap(const vector<int>& arr) {
    heap = arr;
    for (int i = heap.size()/2 - 1; i >= 0; i--) {
        siftDown(i, heap.size());
    }
}

---

三、完整代码实现（C++模板版）

#include <iostream>
#include <vector>
#include <functional>

template <typename T, typename Compare = std::less<T>>
class Heap {
private:
    std::vector<T> data;
    Compare comp;

    void siftUp(int idx) {
        while (idx > 0) {
            int parent = (idx - 1) / 2;
            if (!comp(data[parent], data[idx])) break;
            std::swap(data[parent], data[idx]);
            idx = parent;
        }
    }

    void siftDown(int idx, int size) {
        while (true) {
            int left = 2*idx + 1;
            int right = 2*idx + 2;
            int target = idx;

            if (left < size && comp(data[target], data[left])) 
                target = left;
            if (right < size && comp(data[target], data[right]))
                target = right;
            
            if (target == idx) break;
            std::swap(data[idx], data[target]);
            idx = target;
        }
    }

public:
    explicit Heap(const Compare& cmp = Compare()) : comp(cmp) {}

    Heap(const std::vector<T>& arr, const Compare& cmp = Compare()) : comp(cmp) {
        data = arr;
        for (int i = data.size()/2 - 1; i >= 0; --i) {
            siftDown(i, data.size());
        }
    }

    void push(const T& val) {
        data.push_back(val);
        siftUp(data.size()-1);
    }

    void pop() {
        if (empty()) return;
        std::swap(data.front(), data.back());
        data.pop_back();
        siftDown(0, data.size());
    }

    const T& top() const {
        if (empty()) throw std::out_of_range("Heap is empty");
        return data.front();
    }

    bool empty() const { return data.empty(); }
    size_t size() const { return data.size(); }
};

// 使用示例
int main() {
    // 最大堆示例
    Heap<int> maxHeap;
    for(int num : {3,5,1,9,7}) maxHeap.push(num);
    std::cout << "Max Heap: ";
    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << " "; // 输出：9 7 5 3 1
        maxHeap.pop();
    }

    // 最小堆示例
    Heap<int, std::greater<int>> minHeap;
    for(int num : {3,5,1,9,7}) minHeap.push(num);
    std::cout << "\nMin Heap: ";
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " "; // 输出：1 3 5 7 9
        minHeap.pop();
    }
    
    return 0;
}

---

四、高级应用与扩展

1. 堆排序算法

template <typename T>
void heapSort(std::vector<T>& arr) {
    Heap<T> heap(arr);
    for (int i = arr.size()-1; i >= 0; --i) {
        arr[i] = heap.top();
        heap.pop();
    }
}

2. 实际应用场景

领域	具体应用	堆类型
操作系统	进程优先级调度	最大堆
网络路由	Dijkstra最短路径算法	最小堆
实时系统	高优先级任务处理	最大堆
机器学习	Top-K特征选择	最小堆
数据库系统	多路归并排序	胜者树/败者树

3. 相关数据结构对比

结构	插入	删除极值	查找极值	合并操作	空间
无序数组	O(1)	O(n)	O(n)	O(m+n)	O(n)
有序数组	O(n)	O(1)	O(1)	O(m+n)	O(n)
二叉搜索树	O(log n)	O(log n)	O(log n)	O(m+n)	O(n)
堆	O(log n)	O(log n)	O(1)	O(m+n)	O(n)

---

五、常见问题解答

Q1：堆与优先队列的关系？
→ 优先队列是抽象数据结构，堆是其最高效的物理实现方式

Q2：如何选择最大堆/最小堆？
→ 根据需求方向选择：最大堆用于快速获取最大值，最小堆用于最小值

Q3：堆的局限性有哪些？

• 不支持快速查找任意元素（O(n)）
• 合并两个堆效率低（O(m+n)）
• 不适合需要频繁修改非堆顶元素的场景

Q4：如何实现动态调整优先级？
引入索引堆（Index Heap）结构：

template <typename T>
class IndexHeap {
private:
    std::vector<int> indexes;  // 索引数组
    std::vector<T> keys;       // 实际数据存储
    // 添加反向索引表维护
    std::unordered_map<int, int> reverse; 
};

---

六、最佳实践建议

1. 优先选择标准库实现
   C++中优先使用priority_queue（底层默认用最大堆）：

   #include <queue>
   std::priority_queue<int> maxHeap; 
   std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
   

2. 海量数据处理技巧
   使用堆处理Top K问题的最佳实践：

   #include <queue>
   #include <vector>
   #include <functional>
   
   vector<int> find_top_k(const vector<int>& arr, int k) {
       if (k <= 0) return {};
       
       // 使用最小堆（greater比较器）
       priority_queue<int, vector<int>, greater<int>> min_heap;
       
       for (int num : arr) {
           if (min_heap.size() < k) {
               min_heap.push(num);
           } else {
               if (num > min_heap.top()) {
                   min_heap.pop();
                   min_heap.push(num);
               }
           }
       }
       
       // 将堆转换为有序结果
       vector<int> result;
       while (!min_heap.empty()) {
           result.push_back(min_heap.top());
           min_heap.pop();
       }
       reverse(result.begin(), result.end()); // 从大到小排序
       
       return result;
   }
   

3. 调试技巧
   可视化验证堆结构：

   void printHeap(const vector<int>& heap) {
       int level = 0, count = 1;
       for (int i=0; i<heap.size(); ++i) {
           cout << heap[i] << " ";
           if (i+1 == count) {
               cout << endl;
               level++;
               count += (1 << level);
           }
       }
   }
   

---

建议结合LeetCode练习题（如215.数组中的第K个最大元素、23.合并K个排序链表）进行实践巩固。