本篇笔记以小根堆为例。
数据结构
(近似)完全二叉树,存放在树组中,树组角标从1开始,以1为根。
规定:父节点值<子节点值
,相邻节点没有大小要求,相邻子树中没有大小要求。
效果:确保树根节点值为全树最小值。
节点i
的左子节点为2i
,右子节点为2i+1
。
节点i
的父节点为(int)(i/2)
。
我们额外维护一个length
变量用于判断数组中的元素是否在树中为有效节点。
push
在树组末尾加入要添加的数x
。
此时我们需要将x
向上冒泡,冒到它该存在的位置。
(过程同冒泡排序中的冒泡)
get_min
由于小根堆特性,heap[1]
即为堆中最小值。
pop_min
将根节点置为0,将末尾元素(叶子节点)放在根中,然后使新根节点下沉,下沉到它该存在的位置。
下沉过程中,每一步都将 当前节点、左子、右子 中的最小值向上冒(与当前节点交换)。
当前步骤中三个节点的最小值已经是当前节点时,堆的维护便完成了。