一、大根树、小根树

• 大根树：其中每个节点的值都大于或等于其子节点的值
• 小根树：其中每个节点的值都小于或等于其子节点的值

图例

二、大根堆、小根堆

• 大根堆：属于大根树的一种，但是必须是完全二叉树
• 小根堆：属于小根树的一种，但是必须是完全二叉树

图例

• 下面是两个大根堆，因为每个节点的值都大于其子节点的值，并且是完全二叉树

• 下面不是大根堆，因为其不是完全二叉树

• 下面是两个小根堆，因为每个节点的值都小于其子节点的值，并且是完全二叉树

• 下面不是小根堆，因为其不是完全二叉树

堆的数组表示

• 因为堆是完全二叉树，所以用一维数组表示最为有效（详情可以见文章：https://blog.****.net/qq_41453285/article/details/103561197）
• 如果数组的第一个位置不保存元素。且一个元素的索引为i（1<=i<=n），则有如下的规则：
  • 1.如果i=0，则该节点为根节点，无父节点。否则其父节点下标为i/2
  • 2.如果2*i>n，则该节点没有左子树；否则其左子树的下标为2*i
  • 3.如果(2*i)+1>n，则该节点没有右子树；否则其右子树的下标为2*i+1
  • 4.左子树的下标为奇数，右子树的下标为偶数
• 特征：
  • 堆是完全二叉树，具有n个元素的堆高度(height)为
  • 据上，插入和删除操作的时间为O(height)，复杂度为O()

三、大根堆的插入、删除、初始化

大根堆的插入

插入步骤如下：

• 1.将新节点插入到尾部
• 2.如果其有父节点，检查其值是否比父节点值大，如果比父节点值小，则结束本次插入操作；如果比父节点的值大，那么就将自己与父节点进行互换
• 3.如果互换之后还有父节点，那么重复步骤2直到插入操作结束

演示案例：

• 如果一个大根堆的初始化如下：

• 此时插入一个新节点5，步骤如下：
  • 1.先插入到2的节点的左子树处（如果左图所示）
  • 2.检查到新节点比2节点值大，于是就将新节点5和父节点2进行互换（如果右图所示）
  • 3.互换之后，节点5继续与父节点20比较，发现比父节点20值小，于是就结束本次插入操作，最终的大根堆如下右图所示

复杂度：

• 每一层需耗时Θ(1)，因此，实现这种插入策略的时间复杂度为

大根堆的删除

插入步骤如下：

• 1.删除根节点
• 2.将最后一个节点设置为根节点作为新根节点
• 3.如果有子节点，将新根节点与左右子树比较，如果比左右子树的值都大，则停止本次删除操作；如果比左（或右）子树的值小，那么就将自己与左（或右）子树互换；如果比左右子树都小，那么就与左右子树中较大的那个节点互换
• 4.互换之后如果还有左右子树，那么就继续执行步骤3，直到删除操作结束

演示案例：

• 如果一个大根堆的初始化如下：

• 此时删除大根堆（删除根节点），步骤如下：
  • 1.删除根节点21
  • 2.将最后一个节点2设置为新根节点（如下做图所示）
  • 3.新根结点2与左右子树进行比较，发现比左子树15、右子树20都小，因此需要进行交换操作
  • 4.但是右子树20比左子树15大，因此其与右子树20交换（如下右图所示）
  • 5.交换完成之后，其没有子树了，所以就结束删除操作了（如下右图所示）

复杂度：

• 每一层需耗时Θ(1)，因此，实现这种删除策略的时间复杂度为

大根堆的初始化