最大堆与最小堆
最大堆与最小堆[编辑 | 编辑源代码]
最大堆(Max Heap)和最小堆(Min Heap)是两种特殊的二叉树结构,属于优先队列的常见实现方式。它们满足堆性质(Heap Property),即父节点与子节点之间存在特定的大小关系。最大堆中,父节点的值总是大于或等于其子节点的值;最小堆中,父节点的值总是小于或等于其子节点的值。堆结构常用于高效地获取、插入和删除极值元素(最大值或最小值)。
堆的性质[编辑 | 编辑源代码]
堆是一种完全二叉树(Complete Binary Tree),即除了最后一层外,其他层都被完全填满,且最后一层的节点尽可能靠左排列。堆的主要性质如下:
- 最大堆性质:对于任意节点 ,其值 且 (如果子节点存在)。
- 最小堆性质:对于任意节点 ,其值 且 (如果子节点存在)。
堆通常用数组实现,其中:
- 根节点存储在索引 (或 ,取决于实现)。
- 对于节点 ,其左子节点为 ,右子节点为 ,父节点为 。
堆的操作[编辑 | 编辑源代码]
插入元素(Heapify Up)[编辑 | 编辑源代码]
新元素插入到堆的末尾,然后通过与其父节点比较并交换(如果需要),逐步向上调整,直到满足堆性质。
删除极值元素(Heapify Down)[编辑 | 编辑源代码]
删除堆顶元素(最大值或最小值),将最后一个元素移到堆顶,然后通过与其子节点比较并交换(如果需要),逐步向下调整,直到满足堆性质。
构建堆[编辑 | 编辑源代码]
从最后一个非叶子节点开始,依次对每个节点执行向下调整(Heapify Down),最终构建一个合法的堆。
代码示例[编辑 | 编辑源代码]
以下是用 Python 实现最大堆和最小堆的代码示例:
最大堆实现[编辑 | 编辑源代码]
class MaxHeap:
def __init__(self):
self.heap = []
def parent(self, i):
return (i - 1) // 2
def left_child(self, i):
return 2 * i + 1
def right_child(self, i):
return 2 * i + 2
def insert(self, key):
self.heap.append(key)
i = len(self.heap) - 1
while i > 0 and self.heap[i] > self.heap[self.parent(i)]:
self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
i = self.parent(i)
def extract_max(self):
if not self.heap:
return None
max_val = self.heap[0]
self.heap[0] = self.heap[-1]
self.heap.pop()
self.heapify_down(0)
return max_val
def heapify_down(self, i):
left = self.left_child(i)
right = self.right_child(i)
largest = i
if left < len(self.heap) and self.heap[left] > self.heap[largest]:
largest = left
if right < len(self.heap) and self.heap[right] > self.heap[largest]:
largest = right
if largest != i:
self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
self.heapify_down(largest)
# 示例用法
max_heap = MaxHeap()
max_heap.insert(10)
max_heap.insert(5)
max_heap.insert(20)
max_heap.insert(1)
print("Max heap elements extracted in order:")
print(max_heap.extract_max()) # 输出 20
print(max_heap.extract_max()) # 输出 10
print(max_heap.extract_max()) # 输出 5
print(max_heap.extract_max()) # 输出 1
最小堆实现[编辑 | 编辑源代码]
class MinHeap:
def __init__(self):
self.heap = []
def parent(self, i):
return (i - 1) // 2
def left_child(self, i):
return 2 * i + 1
def right_child(self, i):
return 2 * i + 2
def insert(self, key):
self.heap.append(key)
i = len(self.heap) - 1
while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
i = self.parent(i)
def extract_min(self):
if not self.heap:
return None
min_val = self.heap[0]
self.heap[0] = self.heap[-1]
self.heap.pop()
self.heapify_down(0)
return min_val
def heapify_down(self, i):
left = self.left_child(i)
right = self.right_child(i)
smallest = i
if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
smallest = left
if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
smallest = right
if smallest != i:
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
self.heapify_down(smallest)
# 示例用法
min_heap = MinHeap()
min_heap.insert(10)
min_heap.insert(5)
min_heap.insert(20)
min_heap.insert(1)
print("Min heap elements extracted in order:")
print(min_heap.extract_min()) # 输出 1
print(min_heap.extract_min()) # 输出 5
print(min_heap.extract_min()) # 输出 10
print(min_heap.extract_min()) # 输出 20
堆的可视化[编辑 | 编辑源代码]
以下是一个最大堆的示例(使用 Mermaid 绘制):
- 根节点 20 是最大值。
- 每个父节点的值都大于或等于其子节点的值。
实际应用场景[编辑 | 编辑源代码]
堆在以下场景中非常有用:
1. 优先队列:堆是优先队列的高效实现方式,例如任务调度系统(总是执行优先级最高的任务)。 2. 堆排序:利用最大堆或最小堆进行排序,时间复杂度为 。 3. Dijkstra 算法:在图的最短路径算法中,最小堆用于高效获取当前距离最小的节点。 4. Top-K 问题:例如从海量数据中找出前 K 个最大或最小的元素。
时间复杂度分析[编辑 | 编辑源代码]
堆的主要操作时间复杂度如下:
- 插入元素(Insert):
- 删除极值元素(Extract-Max/Min):
- 获取极值(Peek):
- 构建堆(Heapify):
总结[编辑 | 编辑源代码]
最大堆和最小堆是高效管理动态数据极值的重要数据结构。它们的核心思想是通过维护堆性质,使得插入、删除和获取极值操作的时间复杂度保持在 。理解堆的实现和应用场景,对于解决优先队列相关问题和优化算法性能非常有帮助。