【数据结构与算法】用 Python 实现堆

堆 (heap)

又被为优先队列 (priority queue)。尽管名为优先队列，但堆并不是队列。回忆一下，在队列中，我们可以进行的限定操作是 dequeue 和 enqueue。

dequeue 是按照进入队列的先后顺序来取出元素。而在堆中，我们不是按照元素进入队列的先后顺序取出元素的，而是按照元素的优先级取出元素。

性质

堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。这种数据结构具有以下性质。

• 任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。
• 堆总是一棵完全二叉树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。

python 内置方法 heapq 创建堆

heaqp 模块提供了堆队列算法的实现，也称为优先级队列算法。
要创建堆，请使用初始化为 [] 的列表，或者可以通过函数 heapify（）将填充列表转换为堆。
提供以下功能：
heapq.heappush（堆，项目）
将值项推入堆中，保持堆不变。
heapq.heapify（x）
在线性时间内将列表 x 转换为堆。
heapq.heappop（堆）
弹出并返回堆中的最小项，保持堆不变。如果堆是空的，则引发 IndexError。

import heapq

# 1 heappush生成堆+ heappop把堆从小到大pop出来 
heap = []
data = [1,3,5,7,9,2,4,6,8,0]
for i in data:
    heapq.heappush(heap,i)
print(heap)

lis = []
while heap:
    lis.append(heapq.heappop(heap))
print(lis)

#2 heapify生成堆+ heappop把堆从小到大pop出来 
data2 = [1,5,3,2,9,5]
heapq.heapify(data2)
print(data2)

lis2 = []
while data2:
    lis2.append(heapq.heappop(data2))
print(lis2)

#输出结果
[0, 1, 2, 6, 3, 5, 4, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 5, 9, 5]
[1, 2, 3, 5, 5, 9]

heapq 实现的是最小堆，下面我们自己实现一个最大堆

• 堆的主要操作是插入元素和删除最大元素
• 在插入或者删除操作之后，我们必须保持该堆本来的性质: 1. 完全二叉树 2. 每个节点值都大于或等于它的子节点

上浮（Promotion）

情境: 子节点的值比父节点的值大，比如在末尾添加一个较大的子节点

消除这种违反项： 

• 交换子节点和父节点的值
• 重复这个过程直到堆的顺序恢复正常

def _upheap(heap, node)：
    item = heap[node]
    while node > 0:
        parent_node = (node - 1) >> 1
        parent = heap[parent_node]
        if item > parent:
            heap[node] = parent
            node = parent_node
            continue
        break
    heap[node] = item

下沉（Demotion）

情境: 父节点的值比子节点的值小，比如删除根节点后拿较小的节点替换

消除这种违反项： 

• 交换父节点和比它大的子节点的值
• 重复这个过程直到堆的顺序恢复正常

def _downheap(heap, node):
    item = heap[node]
    left_child_node = 2 * node + 1