定义

堆的表示

• 为了插入和删除的方便，我们将堆设计成一种特殊的二叉树：

  

• 在每一棵子树中，根结点最大。比如说我们每次要删的都是最大值，如果根结点不是最大，而是右结点最大，那么删除几次之后树都斜到左边了，这个树的高度就不是log2 n了。而根结点最大的话就能保持树一直是完全二叉树。

  堆的操作

• 创建堆

  

• 这里是存放在数组中的

• 哨兵的作用后面再说

• 插入元素

  

• 首先插入最后一个位置，然后将其与根结点比较，若比根结点大则和根结点交换，再接着将其和更上一级根结点比较，还大的话再调换，知道不比根结点大为止。

  

• 进入循环之前，用i记录待插入元素，然后将其与根结点比较，若根结点小，则根结点会被挪到最后，再跟上上一级根结点比，根结点还是小，则会被挪到下一级根结点的位置上；若待插入元素比所有根结点大，则会放到哨兵的位置上。

• 算法实例：第五讲->5.1第2小节

• 删除元素

  

• 把5号赋给1号，然后删除5号

  

• 1号再跟它的子结点比较，小的话就和它交换位置，交换完了再和子结点比较，直到不小为止。

  

• 算法实例：第五讲->5.1第3小节

• 堆的创建

  

• 主要研究第二种方法

  

• 根据堆的删除算法，我们是先将根结点替换为最后一个结点，然后一个一个比较交换位置。这种算法的前提是，根结点的左右子树已经是堆了。利用这种算法来创建堆。
• 从底层第一个有儿子的结点87开始，它的左右必定已经是堆，然后利用堆的删除算法将其包括子树调整成堆；接着对前一个同级结点30也这么做。
• 时间复杂度是O(n).