堆

基本概念

堆（Heap）：一种特殊的完全二叉树，具有以下性质之一：

  • 大顶堆（Max Heap）：任意节点值 ≥ 其子节点值
  • 小顶堆（Min Heap）：任意节点值 ≤ 其子节点值

数据结构的三要素

  • 逻辑结构
    • 树形结构
  • 存储结构
    • 顺序存储
      • 父节点索引：(i - 1) // 2
      • 左子节点：2*i + 1
      • 右子节点：2*i + 2
  • 数据的运算

费曼理解

堆就像是一个按优先级排队的队伍，队首总是优先级最高（最大或最小）的元素，你随时可以拿走它，也可以插入新人，队伍会自动调整顺序。

内部实现：

python

创建空堆

1
2
3
class MaxHeap:
	def _int_(self):
		self.max_heap=[]

访问堆顶元素

1
2
3
4
def peek(self)-> int:
	if not self.max_heap:
		return None
	return self.max_heap[0]

向堆种插入元素

向堆中插入元素需要两个步骤：

  1. 添加元素：将新元素添加到堆的末尾，保持完全二叉树的结构
  2. 上移调整：从新元素开始向上调整，直到满足堆的性质

上移调整（Shift Up）过程：

  • 将新插入的节点与其父节点比较
  • 如果新节点值大于父节点值，则交换它们
  • 重复此过程，直到新节点不再大于其父节点或到达根节点
1
2
3
4
5
6
7
def push(self,val:int):
	self.max_heap.append(val)
	self.__shift_up(len(self.max_heap)-1)
def __shift_up(self,i:int):
	while (i - 1) // 2 >= 0 and self.max_heap[i] > self.max_heap[(i - 1) // 2]: 
		self.max_heap[i], self.max_heap[(i - 1) // 2] = self.max_heap[(i - 1) // 2], self.max_heap[i] 
		i = (i - 1) // 2

删除堆顶元素

删除堆顶元素需要三个步骤：

  1. 交换元素：将堆顶元素与末尾元素交换
  2. 删除元素：移除末尾元素（原堆顶元素）
  3. 下移调整：从新的堆顶开始向下调整，直到满足堆的性质

下移调整（Shift Down）过程：

  • 将新的堆顶元素与其较大的子节点比较
  • 如果堆顶元素小于较大子节点，则交换它们
  • 重复此过程，直到堆顶元素不再小于其子节点或到达叶子节点

这个过程称为「下移调整」，因为新的堆顶元素会逐步向堆的下方移动，直到找到合适的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def pop(self) -> int:
    if not self.max_heap:
        raise IndexError("堆为空")
    size = len(self.max_heap)
    self.max_heap[0], self.max_heap[size - 1] = self.max_heap[size - 1], self.max_heap[0]
    val = self.max_heap.pop()
    if self.max_heap:
        self.__shift_down(0, len(self.max_heap))
    return val

def __shift_down(self, i: int, n: int):
    while 2 * i + 1 < n:
        left, right = 2 * i + 1, 2 * i + 2
        larger = left
        if right < n and self.max_heap[right] > self.max_heap[left]:
            larger = right
        if self.max_heap[i] < self.max_heap[larger]:
            self.max_heap[i], self.max_heap[larger] = self.max_heap[larger], self.max_heap[i]
            i = larger
        else:
            break

复杂度分析

操作 平均时间复杂度 最坏时间复杂度 空间复杂度
插入元素 O(log n) O(log n) O(1)
删除堆顶元素 O(log n) O(log n) O(1)
构建堆 O(n) O(n) O(n)
获取堆顶元素 O(1) O(1) O(1)
堆排序 O(n log n) O(n log n) O(1)

应用场景：