堆#

发布于2020-12-28

上次编辑2021-04-19

堆 ¹

（二叉）堆 是一个数组，它可以被看成是一个近似的完全二叉树（类似广搜过程），树上的每一个结点对应数组中的一个元素。²

如果是 大根堆 (max heap)，有 \(\texttt{heap}[i]\ge\texttt{heap}[2i+1]\) 和 \(\texttt{heap}[i]\ge\texttt{heap}[2i+2]\)，即父结点的值大于等于子结点的值。

如果是 小根堆 (min heap)，有 \(\texttt{heap}[i]\le\texttt{heap}[2i+1]\) 和 \(\texttt{heap}[i]\le\texttt{heap}[2i+2]\)，即父结点的值小于等于子结点的值。

堆常用于重复删除优先级最高的对象，根结点存储了这个优先级最高的对象。在大根堆中，最大的元素的优先级最高，在小根堆中，最小的元素优先级最高。

优先队列是一种抽象数据类型，使用堆这种数据结构实现。

例题#