二叉树是最简单、常用的堆,是一颗符合堆性质的完全二叉树
它可以在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)