数据结构之堆（Heap）

数据结构之堆（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. 操作复杂度概览

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. 实际应用场景

3. 相关数据结构对比

五、常见问题解答

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个排序链表）进行实践巩固。