Loading... 本篇笔记以小根堆为例。 ## 数据结构 (近似)完全二叉树,存放在树组中,树组角标从1开始,以1为根。 <u>规定</u>:`父节点值<子节点值`,相邻节点没有大小要求,相邻子树中没有大小要求。 <u>效果</u>:确保树根节点值为全树最小值。 节点`i`的左子节点为`2i`,右子节点为`2i+1`。 节点`i`的父节点为`(int)(i/2)`。 我们额外维护一个`length`变量用于判断数组中的元素是否在树中为有效节点。 ## push 在树组末尾加入要添加的数`x`。 此时我们需要将`x`向上**冒泡**,冒到它该存在的位置。 (过程同冒泡排序中的冒泡) ## get_min 由于小根堆特性,`heap[1]`即为堆中最小值。 ## pop_min 将根节点置为0,将末尾元素(叶子节点)放在根中,然后使新根节点**下沉**,下沉到它该存在的位置。 下沉过程中,每一步都将 当前节点、左子、右子 中的**最小值**向上冒(与当前节点交换)。 当前步骤中三个节点的最小值已经是当前节点时,堆的维护便完成了。 最后修改:2022 年 03 月 26 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 0 如果觉得这篇文章对你有用,请随意赞赏~