11-20 06:51 阅读 138

关注

数据结构与算法-最大堆/最小堆

定义

最大堆：对于任意节点，其子节点均不大于该节点
最小堆：对于任意节点，其子节点均不小于该节点

特性

最大堆：堆顶节点总是堆中最大的
最小堆：堆顶节点总是堆中最小的

图示（以最大堆为例）

图1.1 一个最大堆

插入新节点：
最大堆插入新节点时，比较其与父节点大小，若父节点不小于新节点，插入操作结束，否则交换其与父节点位置，再次比较其与父节点大小，直到父节点不小于新节点或新节点到达堆顶时操作结束。

图1.2 向最大堆插入新节点，新节点比其父节点大，需要交换位置

图1.3 新节点仍然比其父节点大，需再次交换位置

图1.4 此时新节点不大于其父节点，插入操作结束

图1.5 插入操作结束后的最大堆

取出堆顶节点：
先交换堆顶节点与堆中最后一个节点的位置，然后从堆中移除最后的节点，即需要取出的堆顶节点，比较新堆顶节点与其子节点的大小，若子节点均不大于堆顶节点，操作结束，否则交换其与较大子节点的位置，再次比较，直到子节点均不大于该节点或该节点为叶子节点时操作结束。

图1.6 交换堆顶节点与堆中最后一个节点，并移除需取出的堆顶节点，新堆顶节点小于其节点，需交换位置

图1.7 该节点与其较大子节点交换位置后，仍然小于其子节点，需继续交换位置

图1.8 此时子节点均不大于该节点，操作结束

图1.9 取出操作结束后，仍保持最大堆的特性

时间复杂度

插入新节点：$O({\log }_{2}n)$
取出堆顶节点：$O({\log }_{2}n)$

作者：Doggy
链接：https://juejin.cn/post/7032568424832663583