06-堆（Heap）

💡 核心结论

堆本质

  • 定义：完全二叉树，满足堆性质（父节点≥/≤所有子节点）

  • 类型：最大堆（父≥子）、最小堆（父≤子）

  • 核心：快速找到最大/最小值O(1)，插入删除O(log n)

  • 实现：用数组存储，利用完全二叉树性质计算索引

  • 应用：优先队列、Top K问题、堆排序

数组索引公式（从0开始）

父节点: (i - 1) / 2
左子节点: 2i + 1
右子节点: 2i + 2

关键操作

操作

复杂度

说明

找最大/最小

O(1)

堆顶元素

插入

O(log n)

上浮调整

删除堆顶

O(log n)

下沉调整

建堆

O(n)

从底向上调整

堆 vs 其他结构

数据结构

找最大

插入

删除最大

无序数组

O(n)

O(1)

O(n)

有序数组

O(1)

O(n)

O(1)

BST

O(log n)

O(log n)

O(log n)

堆

O(1)

O(log n)

O(log n)

应用场景（重要）

  1. 优先队列：任务调度、事件驱动

  2. Top K问题：最大/最小的K个元素

  3. 堆排序：O(n log n)原地排序

  4. 中位数维护：双堆结构

  5. 定时器：最小堆管理定时任务

🔺 最大堆操作

上浮（Swim/Heapify Up）

插入新元素后，从底向上调整
如果子节点 > 父节点，交换
重复直到满足堆性质

下沉（Sink/Heapify Down）

删除堆顶后，将末尾元素放到堆顶
从上向下调整
与较大的子节点交换
重复直到满足堆性质

🏗️ 建堆

方法1：逐个插入

# 时间复杂度：O(n log n)
for element in array:
    heap.insert(element)

方法2：自底向上（推荐）

# 时间复杂度：O(n)
# 从最后一个非叶子节点开始下沉
for i in range((len(array) - 2) // 2, -1, -1):
    heapify_down(array, i)

为什么O(n)：

  • 叶子节点占一半，不需要调整

  • 倒数第二层最多下沉1次

  • 倒数第三层最多下沉2次

  • 总和：n/2×0 + n/4×1 + n/8×2 + … = O(n)

🎯 堆排序

算法步骤

  1. 建立最大堆：O(n)

  2. 交换堆顶和末尾：O(1)

  3. 减小堆大小，下沉新堆顶：O(log n)

  4. 重复步骤2-3：n次

总时间复杂度：O(n log n) 空间复杂度：O(1)（原地排序）

def heap_sort(arr):
    # 建堆
    for i in range((len(arr) - 2) // 2, -1, -1):
        heapify_down(arr, i, len(arr))
    
    # 排序
    for i in range(len(arr) - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify_down(arr, 0, i)

💡 Top K问题

最大的K个元素

# 使用最小堆，维护K个元素
import heapq

def top_k_largest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)  # 最小堆
    
    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)
    
    return heap

最小的K个元素

# 使用最大堆
def top_k_smallest(nums, k):
    # Python heapq是最小堆，取负数实现最大堆
    heap = [-x for x in nums[:k]]
    heapq.heapify(heap)
    
    for num in nums[k:]:
        if num < -heap[0]:
            heapq.heapreplace(heap, -num)
    
    return [-x for x in heap]

📚 LeetCode练习

💻 完整代码实现

Python 实现

  1"""
  2最大堆和最小堆实现
  3"""
  4
  5class MaxHeap:
  6    """最大堆实现"""
  7    
  8    def __init__(self):
  9        self.heap = []
 10    
 11    def _parent(self, i):
 12        """父节点索引"""
 13        return (i - 1) // 2
 14    
 15    def _left_child(self, i):
 16        """左子节点索引"""
 17        return 2 * i + 1
 18    
 19    def _right_child(self, i):
 20        """右子节点索引"""
 21        return 2 * i + 2
 22    
 23    def _swap(self, i, j):
 24        """交换两个元素"""
 25        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
 26    
 27    def _swim(self, i):
 28        """上浮"""
 29        while i > 0 and self.heap[i] > self.heap[self._parent(i)]:
 30            self._swap(i, self._parent(i))
 31            i = self._parent(i)
 32    
 33    def _sink(self, i):
 34        """下沉"""
 35        max_index = i
 36        left = self._left_child(i)
 37        right = self._right_child(i)
 38        
 39        # 找出最大值的索引
 40        if left < len(self.heap) and self.heap[left] > self.heap[max_index]:
 41            max_index = left
 42        if right < len(self.heap) and self.heap[right] > self.heap[max_index]:
 43            max_index = right
 44        
 45        # 如果最大值不是当前节点，交换并继续下沉
 46        if max_index != i:
 47            self._swap(i, max_index)
 48            self._sink(max_index)
 49    
 50    def insert(self, val):
 51        """插入元素"""
 52        self.heap.append(val)
 53        self._swim(len(self.heap) - 1)
 54    
 55    def extract_max(self):
 56        """删除并返回最大值"""
 57        if not self.heap:
 58            raise IndexError('extract from empty heap')
 59        
 60        if len(self.heap) == 1:
 61            return self.heap.pop()
 62        
 63        # 交换堆顶和末尾
 64        max_val = self.heap[0]
 65        self.heap[0] = self.heap.pop()
 66        self._sink(0)
 67        return max_val
 68    
 69    def peek(self):
 70        """查看最大值"""
 71        if not self.heap:
 72            raise IndexError('peek from empty heap')
 73        return self.heap[0]
 74    
 75    def size(self):
 76        """堆大小"""
 77        return len(self.heap)
 78    
 79    def is_empty(self):
 80        """是否为空"""
 81        return len(self.heap) == 0
 82    
 83    @staticmethod
 84    def heapify(arr):
 85        """建堆（O(n)）"""
 86        heap = MaxHeap()
 87        heap.heap = arr[:]
 88        
 89        # 从最后一个非叶子节点开始下沉
 90        for i in range((len(arr) - 2) // 2, -1, -1):
 91            heap._sink(i)
 92        
 93        return heap
 94    
 95    def __str__(self):
 96        return str(self.heap)
 97
 98
 99class MinHeap:
100    """最小堆（只修改比较符号）"""
101    
102    def __init__(self):
103        self.heap = []
104    
105    def _parent(self, i):
106        return (i - 1) // 2
107    
108    def _left_child(self, i):
109        return 2 * i + 1
110    
111    def _right_child(self, i):
112        return 2 * i + 2
113    
114    def _swap(self, i, j):
115        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
116    
117    def _swim(self, i):
118        while i > 0 and self.heap[i] < self.heap[self._parent(i)]:
119            self._swap(i, self._parent(i))
120            i = self._parent(i)
121    
122    def _sink(self, i):
123        min_index = i
124        left = self._left_child(i)
125        right = self._right_child(i)
126        
127        if left < len(self.heap) and self.heap[left] < self.heap[min_index]:
128            min_index = left
129        if right < len(self.heap) and self.heap[right] < self.heap[min_index]:
130            min_index = right
131        
132        if min_index != i:
133            self._swap(i, min_index)
134            self._sink(min_index)
135    
136    def insert(self, val):
137        self.heap.append(val)
138        self._swim(len(self.heap) - 1)
139    
140    def extract_min(self):
141        if not self.heap:
142            raise IndexError('extract from empty heap')
143        
144        if len(self.heap) == 1:
145            return self.heap.pop()
146        
147        min_val = self.heap[0]
148        self.heap[0] = self.heap.pop()
149        self._sink(0)
150        return min_val
151    
152    def peek(self):
153        if not self.heap:
154            raise IndexError('peek from empty heap')
155        return self.heap[0]
156
157
158def heap_sort(arr):
159    """堆排序"""
160    # 建立最大堆
161    heap = MaxHeap.heapify(arr)
162    
163    # 依次取出最大值
164    result = []
165    while not heap.is_empty():
166        result.append(heap.extract_max())
167    
168    return result[::-1]  # 反转得到升序
169
170
171def top_k_largest(nums, k):
172    """最大的K个元素（使用最小堆）"""
173    if k >= len(nums):
174        return nums
175    
176    heap = MinHeap()
177    
178    # 先放入K个元素
179    for i in range(k):
180        heap.insert(nums[i])
181    
182    # 遍历剩余元素
183    for i in range(k, len(nums)):
184        if nums[i] > heap.peek():
185            heap.extract_min()
186            heap.insert(nums[i])
187    
188    return heap.heap
189
190
191def demo():
192    """演示堆操作"""
193    print("=== 最大堆演示 ===\n")
194    
195    heap = MaxHeap()
196    
197    # 插入
198    values = [3, 1, 6, 5, 2, 4]
199    print(f"插入: {values}")
200    for val in values:
201        heap.insert(val)
202        print(f"插入 {val}: {heap}")
203    
204    print(f"\n堆顶（最大值）: {heap.peek()}")
205    
206    # 删除
207    print("\n依次删除最大值:")
208    while not heap.is_empty():
209        print(f"删除: {heap.extract_max()}, 堆: {heap}")
210    
211    print("\n=== 建堆演示 ===\n")
212    arr = [3, 1, 6, 5, 2, 4]
213    print(f"原数组: {arr}")
214    heap2 = MaxHeap.heapify(arr)
215    print(f"建堆后: {heap2}")
216    
217    print("\n=== 堆排序演示 ===\n")
218    arr = [3, 1, 6, 5, 2, 4]
219    print(f"原数组: {arr}")
220    sorted_arr = heap_sort(arr)
221    print(f"排序后: {sorted_arr}")
222    
223    print("\n=== Top K问题 ===\n")
224    nums = [3, 2, 1, 5, 6, 4]
225    k = 3
226    print(f"数组: {nums}")
227    print(f"最大的{k}个元素: {top_k_largest(nums, k)}")
228
229
230if __name__ == '__main__':
231    demo()
232

C++ 实现

  1/**
  2 * 最大堆实现
  3 */
  4
  5#include <iostream>
  6#include <vector>
  7#include <stdexcept>
  8
  9class MaxHeap {
 10private:
 11    std::vector<int> heap;
 12    
 13    int parent(int i) {
 14        return (i - 1) / 2;
 15    }
 16    
 17    int leftChild(int i) {
 18        return 2 * i + 1;
 19    }
 20    
 21    int rightChild(int i) {
 22        return 2 * i + 2;
 23    }
 24    
 25    void swim(int i) {
 26        while (i > 0 && heap[i] > heap[parent(i)]) {
 27            std::swap(heap[i], heap[parent(i)]);
 28            i = parent(i);
 29        }
 30    }
 31    
 32    void sink(int i) {
 33        int maxIndex = i;
 34        int left = leftChild(i);
 35        int right = rightChild(i);
 36        
 37        if (left < heap.size() && heap[left] > heap[maxIndex]) {
 38            maxIndex = left;
 39        }
 40        if (right < heap.size() && heap[right] > heap[maxIndex]) {
 41            maxIndex = right;
 42        }
 43        
 44        if (maxIndex != i) {
 45            std::swap(heap[i], heap[maxIndex]);
 46            sink(maxIndex);
 47        }
 48    }
 49
 50public:
 51    void insert(int val) {
 52        heap.push_back(val);
 53        swim(heap.size() - 1);
 54    }
 55    
 56    int extractMax() {
 57        if (heap.empty()) {
 58            throw std::runtime_error("Extract from empty heap");
 59        }
 60        
 61        if (heap.size() == 1) {
 62            int val = heap.back();
 63            heap.pop_back();
 64            return val;
 65        }
 66        
 67        int maxVal = heap[0];
 68        heap[0] = heap.back();
 69        heap.pop_back();
 70        sink(0);
 71        return maxVal;
 72    }
 73    
 74    int peek() const {
 75        if (heap.empty()) {
 76            throw std::runtime_error("Peek from empty heap");
 77        }
 78        return heap[0];
 79    }
 80    
 81    int size() const {
 82        return heap.size();
 83    }
 84    
 85    bool isEmpty() const {
 86        return heap.empty();
 87    }
 88    
 89    static MaxHeap heapify(const std::vector<int>& arr) {
 90        MaxHeap h;
 91        h.heap = arr;
 92        
 93        for (int i = (arr.size() - 2) / 2; i >= 0; i--) {
 94            h.sink(i);
 95        }
 96        
 97        return h;
 98    }
 99    
100    void print() const {
101        std::cout << "[";
102        for (size_t i = 0; i < heap.size(); i++) {
103            std::cout << heap[i];
104            if (i < heap.size() - 1) std::cout << ", ";
105        }
106        std::cout << "]" << std::endl;
107    }
108};
109
110
111// 堆排序
112std::vector<int> heapSort(std::vector<int> arr) {
113    MaxHeap heap = MaxHeap::heapify(arr);
114    std::vector<int> result;
115    
116    while (!heap.isEmpty()) {
117        result.push_back(heap.extractMax());
118    }
119    
120    std::reverse(result.begin(), result.end());
121    return result;
122}
123
124
125int main() {
126    std::cout << "=== 最大堆演示 ===" << std::endl << std::endl;
127    
128    MaxHeap heap;
129    
130    std::vector<int> values = {3, 1, 6, 5, 2, 4};
131    std::cout << "插入: ";
132    for (int val : values) {
133        std::cout << val << " ";
134    }
135    std::cout << std::endl;
136    
137    for (int val : values) {
138        heap.insert(val);
139        std::cout << "插入 " << val << ": ";
140        heap.print();
141    }
142    
143    std::cout << "\n堆顶（最大值）: " << heap.peek() << std::endl;
144    
145    std::cout << "\n依次删除最大值:" << std::endl;
146    while (!heap.isEmpty()) {
147        std::cout << "删除: " << heap.extractMax() << ", 堆: ";
148        heap.print();
149    }
150    
151    std::cout << "\n=== 建堆演示 ===" << std::endl << std::endl;
152    std::vector<int> arr = {3, 1, 6, 5, 2, 4};
153    std::cout << "原数组: ";
154    for (int val : arr) std::cout << val << " ";
155    std::cout << std::endl;
156    
157    MaxHeap heap2 = MaxHeap::heapify(arr);
158    std::cout << "建堆后: ";
159    heap2.print();
160    
161    std::cout << "\n=== 堆排序演示 ===" << std::endl << std::endl;
162    std::vector<int> sorted = heapSort(arr);
163    std::cout << "排序后: ";
164    for (int val : sorted) std::cout << val << " ";
165    std::cout << std::endl;
166    
167    return 0;
168}