堆的概念

堆是满足一下性质的树：

  • 堆中某个节点的值总是不大于或不小于其父节点的值
  • 堆总是一棵完全二叉树

堆的分类

根据堆的节点大小关系，分为大根堆和小根堆。大根堆中每个节点都比它的子节点大，小根堆则是每个节点都比它的两个子节点小

大根堆示意图

小根堆示意图

在数组中储存的下标特征

在储存堆的时候，一个节点如果下标是 那么它的父节点的下标是 。左子节点的下标是 ，右子节点的下标是 。

堆的操作

以下操作均以大根堆为例

堆的插入

  1. 每次把一个节点放到数组的最后
  2. 依次比较它和其父节点的值，如果父节点更小，那么使用 shift up 操作，把当前节点和父节点交换，然后向上递归
  3. 如果父节点已经比此时调整的调整节点大了，调整结束
    时间复杂度是 级别的。

堆的删除

堆只支持删除堆顶端的元素

  1. 找到最后一个插入的元素
  2. 将最后一个元素和顶部的元素互换
  3. 向下递归调整进行 shift down

相关文章

[[Leftist heap]]