二叉树是最简单、常用的堆,是一颗符合堆性质的完全二叉树
它可以在O(logn)地插入或删除某个值,在O(1)地查询最大(最小值)

关于节点存储:
作为一棵完全二叉树,二叉堆完全可以用一个1-index的数组来存储,
对于节点p,p2即为左儿子,p2+1即为右节点。
同时,用size记录当前二叉堆中节点的个数。

以大根堆为例:
图片说明
在数组中存储方式:
图片说明

关于堆的操作:
现在我们考虑如何保证二叉堆的性质不被破坏。实际上,对于一个破坏堆性质的节点,我们可以使其上浮或下沉,因为最差也不过是上浮到顶或是下沉到底,所以只需要O(logn)的时间就可以使其不再破坏性质。

上浮操作
不断与父节点比较,如果比父节点大(以大根堆为例,下同)就与之交换,直到不大于父节点或成为根节点为止。
def up(n):
    i = n
    while i>1 and array[i]>array[i//2]:
        swap(array[i],array[i//2])
               i = i//2
下沉操作
不断与较大的子节点比较,如果比它小就与之交换,直到不小于任何子节点或成为叶子节点为止。之所以要与较大的子节点比较,是为了保证交换上来的节点比两个子节点都大。
def down(n):
    i = n
    if n*2 < size(array) and array[i] < array[n*2]: i = n*2
    if n*2+1 < size(array) and array[i] < array[n*2+1]: i = n*2+1
    if i != n:
        swap(array[i],array[n])
        down(i)
插入操作
直接在尾部插入值,然后上浮即可。
def insert(num):
    array.append(num)
    up(len(array)-1)
删除操作
可以将根节点与最后一个节点交换,使size减1,然后再下沉。
def delete():
    swap(array[1],array[-1])
    array.pop()
    down(1)
查询操作
def top():
    return array[1]
建堆操作
可以从一个数组O(n)地建立堆,只需复制过来然后从底部到顶部依次下沉即可。实际上因为叶子节点不需要下沉,所以可以从n/2 处开始遍历。
def build(n):
    for i in range(n//2,0,-1):
        down(i)