Python Heap 堆 数据结构

Question

优先队列（Priority Queue）：一种特殊的队列，取出元素的顺序是按照元素的优先级大小，而不是进入队列的先后顺序（在优先级相同的情况下是FIFO）。可以用堆来实现

堆（Heap）/二叉堆（Binary Heap）：用数组表示的完全二叉树。性质：从根到任一结点的路径是有序的。

• 最大堆（MaxHeap）：也叫大顶堆，任一结点的值是其子树所有结点的最大值（大于等于）；
• 最小堆（MinHeap）：也叫小顶堆，任一结点的值是其子树所有结点的最小值（小于等于）

堆最主要的两个操作是插入和删除，以最大堆为例：

• 插入：先判断堆是否已满。新插入的结点放在完全二叉树最后的位置，然后和父结点比较，如果比父结点大，则交换两者位置，继续向上比较，直到不比父结点大或成为根结点。时间复杂度是树的高度 O(log n)
• 删除：删除操作指的是删除根结点。先判空，用完全二叉树中的最后一个结点代替根节点，然后不断和子结点比较，和较大的那个子结点交换位置。时间复杂度 O(log n)

堆的建立：从一个序列中建立一个堆，如果每个元素分别插入，时间复杂度是O(nlog n)，因此选取另一种方法，先将序列放入数组，再从倒数第二层开始，从左到右/从右到左依次向下调整为堆，直到调整到树根，时间复杂度为 O(n)。

和二叉搜索树相比，堆的内存占用更小（使用数组实现）；BST必须平衡的情况下才能达到 O(log n) 的复杂度，但是堆的复杂度始终是 O(log n)；对于搜索元素，BST更快，堆不是用来搜索元素的，堆的主要操作是快速插入、删除元素，在堆中搜索元素等同于在数组中搜索元素

那优先队列有什么用呢？

为什么不直接把元素排序然后再将这个有序数组作为优先队列呢？一个原因是在某些应用中，总数据量太大，无法进行排序，比如一个10亿规模的数据，而我们只想从中找出最大的10个数，有了优先队列，我们只需要一个存储10个数的队列即可

既然使用数组实现，那就不像二叉树那样有指向子结点的指针，所以在堆中如何进行定位呢？

实现堆时，规定下标从1开始，那么对于一个下标为i的结点，有：

parent = floor(i / 2)
left = 2*i
right = 2*i + 1

实现

实现一个最大堆：

class MaxHeap:
  def __init__(self):
    self.data = [None]

is_empty() —— 判断堆是否为空

get_size() —— 获取堆中的元素个数

peek_max() —— 返回堆顶元素，但不删除

insert(value) —— 向堆中插入元素

def insert(self, value):
  self.data.append(value)
  index = self.get_size()
  # 如果比父结点大并且不是根结点则向上调整
  while index > 1 and self.data[index] > self.data[index//2]:
    self.data[index], self.data[index//2] = self.data[index//2],self.data[index]
    index = index // 2

remove() —— 删除堆顶元素

# 用于删除和创建堆的函数。从当前结点开始向下调整，保证结点往下是一个堆
def sift_down(self, index):
  while 2*index <= self.get_size():
    # 左子结点的索引
    child = 2 * index
    # 如果右子结点存在且比左子结点大，则应与右子结点交换
    if 2*index + 1 <= self.get_size() and self.data[2*index+1] > self.data[2*index]:
      child += 1  # 右子结点的索引
    # 如果当前结点的值小于子结点中的较大者，则应继续向下交换，否则结束
    if self.data[index] < self.data[child]:
      self.data[index], self.data[child] = self.data[child], self.data[index]
      index = child
    else:
      break
# 删除堆顶元素（最大值）
def remove(self):
  if self.is_empty():
    raise RemoveError("Unable to remove from an empty heap.")
  # 用堆的最后一个元素替代堆顶元素，然后删除最后一个元素
  self.data[1], self.data[self.get_size()] = self.data[self.get_size()], self.data[1]
  self.data.pop()
  # 从堆顶向下调整
  self.sift_down(1)

build_heap(array) —— 从一个序列创建堆

def build_heap(self, array):
  self.data = [None] + array
  index = self.get_size() // 2
  # 从倒数第二层开始，从右到左，逐层向上调整。每次调整只需sift_down
  while index > 0:
    self.sift_down(index)
    index -= 1