1. 什么是堆数据结构？

堆(Heap)是一种特殊的完全二叉树数据结构，它满足堆属性：

• 最小堆：每个父节点的值都小于或等于其子节点
• 最大堆：每个父节点的值都大于或等于其子节点

堆的主要特点：

• 根节点总是堆中最小（最小堆）或最大（最大堆）的元素
• 插入和删除操作的时间复杂度为O(log n)
• 获取最小/最大值的时间复杂度为O(1)
• 常用于实现优先队列、堆排序和解决Top K问题

2. Python中的heapq模块

Python通过内置的heapq模块提供堆操作功能，该模块提供了：

• 将列表转换为堆的函数
• 添加和删除元素的函数
• 堆排序功能

导入heapq模块：

import heapq

heapq模块核心函数：

3. 创建和操作最小堆

最小堆是Python heapq模块的默认堆类型。以下是创建和操作最小堆的完整示例：

3.1 创建最小堆

import heapq

# 创建一个列表
data = [3, 1, 4, 1, 5, 9, 2, 6, 5]

# 使用heapify将列表转换为最小堆
heapq.heapify(data)
print("堆化后的列表:", data)  # 输出: [1, 1, 2, 3, 5, 9, 4, 6, 5]

3.2 添加元素到堆

# 添加新元素到堆
heapq.heappush(data, 0)
print("添加0后的堆:", data)  # 输出: [0, 1, 1, 3, 5, 2, 4, 6, 5, 9]

3.3 从堆中弹出最小元素

# 弹出最小元素
min_element = heapq.heappop(data)
print("弹出的最小元素:", min_element)  # 输出: 0
print("弹出后的堆:", data)  # 输出: [1, 3, 1, 5, 5, 2, 4, 6, 9]

3.4 访问堆顶元素

# 访问最小元素而不弹出
min_value = data[0]
print("当前最小元素:", min_value)  # 输出: 1

3.5 同时添加和弹出元素

# 先添加新元素再弹出最小元素
result = heapq.heappushpop(data, 2)
print("弹出的元素:", result)  # 输出: 1
print("操作后的堆:", data)  # 输出: [1, 3, 2, 5, 5, 2, 4, 6, 9]

4. 实现最大堆的技巧

Python的heapq模块只提供最小堆实现，但我们可以通过以下技巧实现最大堆：

4.1 使用负数技巧

将元素取负后存入最小堆，取出时再取负恢复原值：

import heapq

# 创建最大堆
max_heap = []
data = [3, 1, 4, 1, 5, 9, 2, 6, 5]

# 将元素取负后加入堆
for num in data:
    heapq.heappush(max_heap, -num)

print("最大堆结构:", max_heap)  # 输出: [-9, -6, -5, -4, -5, -3, -2, -1, -1]

# 弹出最大元素
max_element = -heapq.heappop(max_heap)
print("最大元素:", max_element)  # 输出: 9
print("弹出后堆顶:", -max_heap[0])  # 输出: 6

4.2 使用自定义类实现最大堆

import heapq

class MaxHeapObj:
    def __init__(self, val):
        self.val = val
        
    def __lt__(self, other):
        return self.val > other.val  # 反转比较实现最大堆
    
    def __eq__(self, other):
        return self.val == other.val
        
    def __str__(self):
        return str(self.val)

# 创建最大堆
max_heap = []
data = [3, 1, 4, 1, 5, 9, 2, 6, 5]

# 将元素包装为MaxHeapObj对象
for num in data:
    heapq.heappush(max_heap, MaxHeapObj(num))

# 弹出最大元素
max_element = heapq.heappop(max_heap).val
print("最大元素:", max_element)  # 输出: 9

5. 堆排序算法

堆排序是一种高效的排序算法，时间复杂度为O(n log n)：

5.1 使用堆实现升序排序

import heapq

def heap_sort_ascending(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for _ in range(len(h))]

data = [3, 1, 4, 1, 5, 9, 2, 6, 5]
sorted_data = heap_sort_ascending(data)
print("升序排序结果:", sorted_data)  # 输出: [1, 1, 2, 3, 4, 5, 5, 6, 9]

5.2 使用堆实现降序排序

import heapq

def heap_sort_descending(iterable):
    # 使用最大堆实现降序排序
    h = []
    for value in iterable:
        heapq.heappush(h, -value)
    return [-heapq.heappop(h) for _ in range(len(h))]

data = [3, 1, 4, 1, 5, 9, 2, 6, 5]
sorted_data = heap_sort_descending(data)
print("降序排序结果:", sorted_data)  # 输出: [9, 6, 5, 5, 4, 3, 2, 1, 1]

5.3 使用heapify原地排序

import heapq

def heap_sort_inplace(iterable):
    # 原地堆排序
    heapq.heapify(iterable)
    return [heapq.heappop(iterable) for _ in range(len(iterable))]

data = [3, 1, 4, 1, 5, 9, 2, 6, 5]
sorted_data = heap_sort_inplace(data)
print("原地堆排序结果:", sorted_data)  # 输出: [1, 1, 2, 3, 4, 5, 5, 6, 9]

6. 实际应用场景

6.1 解决Top K问题

查找最大/最小的K个元素：

import heapq

def top_k_smallest(nums, k):
    # 使用最大堆获取最小的k个元素
    heap = []
    for num in nums:
        heapq.heappush(heap, -num)
        if len(heap) > k:
            heapq.heappop(heap)
    return [-x for x in heap]

def top_k_largest(nums, k):
    # 使用最小堆获取最大的k个元素
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap

data = [3, 1, 4, 1, 5, 9, 2, 6, 5]
print("最小的3个元素:", top_k_smallest(data, 3))  # 输出: [1, 1, 2]
print("最大的3个元素:", top_k_largest(data, 3))   # 输出: [6, 5, 9]

6.2 合并多个有序序列

import heapq

def merge_sorted_arrays(arrays):
    heap = []
    # 初始化堆，添加每个数组的第一个元素
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))
    
    result = []
    while heap:
        val, arr_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        if elem_idx + 1 < len(arrays[arr_idx]):
            next_elem = arrays[arr_idx][elem_idx + 1]
            heapq.heappush(heap, (next_elem, arr_idx, elem_idx + 1))
            
    return result

arr1 = [1, 4, 7]
arr2 = [2, 5, 8]
arr3 = [3, 6, 9]
merged = merge_sorted_arrays([arr1, arr2, arr3])
print("合并后的有序序列:", merged)  # 输出: [1, 2, 3, 4, 5, 6, 7, 8, 9]

6.3 实现优先队列

import heapq

class PriorityQueue:
    def __init__(self):
        self._heap = []
        self._index = 0  # 用于处理相同优先级的情况
        
    def push(self, item, priority):
        heapq.heappush(self._heap, (priority, self._index, item))
        self._index += 1
        
    def pop(self):
        return heapq.heappop(self._heap)[-1]
    
    def is_empty(self):
        return len(self._heap) == 0

# 使用优先队列
pq = PriorityQueue()
pq.push("Task 1", 3)
pq.push("Task 2", 1)
pq.push("Task 3", 2)

print("执行顺序:")
while not pq.is_empty():
    print(pq.pop())  # 输出: Task 2, Task 3, Task 1

7. 堆操作的时间复杂度

堆操作的时间复杂度是其高效性的关键：

8. 总结与最佳实践

堆是一种强大的数据结构，特别适合需要频繁访问最小或最大元素的场景。以下是Python堆操作的关键点：

何时使用堆数据结构？

• 需要快速访问最大或最小元素
• 实现优先队列
• 解决Top K问题
• 合并多个有序序列
• 需要高效的插入和删除操作
• 实现堆排序算法

通过掌握Python中的堆操作，你可以高效解决许多涉及优先级、排序和选择的问题。heapq模块提供了简洁而强大的API，结合本文介绍的最佳实践，你将能够在实际项目中充分发挥堆数据结构的优势。