本篇笔记以小根堆为例。

数据结构

(近似)完全二叉树,存放在树组中,树组角标从1开始,以1为根。

规定父节点值<子节点值,相邻节点没有大小要求,相邻子树中没有大小要求。

效果:确保树根节点值为全树最小值。

节点i的左子节点为2i,右子节点为2i+1

节点i的父节点为(int)(i/2)

我们额外维护一个length变量用于判断数组中的元素是否在树中为有效节点。

push

在树组末尾加入要添加的数x

此时我们需要将x向上冒泡,冒到它该存在的位置。

(过程同冒泡排序中的冒泡)

get_min

由于小根堆特性,heap[1]即为堆中最小值。

pop_min

将根节点置为0,将末尾元素(叶子节点)放在根中,然后使新根节点下沉,下沉到它该存在的位置。

下沉过程中,每一步都将 当前节点、左子、右子 中的最小值向上冒(与当前节点交换)。

当前步骤中三个节点的最小值已经是当前节点时,堆的维护便完成了。

最后修改:2022 年 03 月 26 日 02 : 32 PM
如果觉得这篇文章对你有用,请随意赞赏~