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

定义

最大堆：关于恣意节点，其子节点均不大于该节点
最小堆：关于恣意节点，其子节点均不小于该节点

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

图1.1 一个最大堆

刺进新节点：
最大堆刺进新节点时，比较其与父节点巨细，若父节点不小于新节点，刺进操作完毕，不然交流其与父节点方位，再次比较其与父节点巨细，直到父节点不小于新节点或新节点到达堆顶时操作完毕。

图1.2 向最大堆刺进新节点，新节点比其父节点大，需求交流方位

图1.3 新节点依然比其父节点大，需再次交流方位

图1.4 此时新节点不大于其父节点，刺进操作完毕

图1.5 刺进操作完毕后的最大堆

取出堆顶节点：
先交流堆顶节点与堆中最终一个节点的方位，然后从堆中移除最终的节点，即需求取出的堆顶节点，比较新堆顶节点与其子节点的巨细，若子节点均不大于堆顶节点，操作完毕，不然交流其与较大子节点的方位，再次比较，直到子节点均不大于该节点或该节点为叶子节点时操作完毕。

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

图1.7 该节点与其较大子节点交流方位后，依然小于其子节点，需持续交流方位

图1.8 此时子节点均不大于该节点，操作完毕

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

刺进新节点： $O(\log_2n)$
取出堆顶节点： $O(\log_2n)$