二叉堆是一组能够用堆有序的完全二叉树排序的元素，一般用数组来存储。

大顶堆， 每个结点的值都大于或等于其左右孩子结点的值，其顶部为最大值。

小顶堆，每个结点的值都小于或等于其左右孩子结点的值，其顶部为最小值。

二叉堆

性质

• 根节点在数组中的位置是 1
  • 左边子节点 2i
  • 右子节点 2i+1
  • 父节点 i / 2
  • 最后一个非叶子节点为 len / 2
• 根节点在数组中的位置是 0
• 左子节点 2i + 1
• 右边子节点 2i+ 2
• 父节点的下标是 (i − 1) / 2
• 最后一个非叶子节点为 len / 2 - 1

实现

构造二叉堆

• 找到最后一个非叶子节点 ( len / 2 或者 len / 2 - 1）
• 从最后一个非叶子节点下标索引开始递减，逐个下沉

插入节点

• 在数组的最末尾插入新节点
• 将最后一个节点上浮，时间复杂度为O(log n)
  • 比较当前节点与父节点
  • 不满足 堆性质* *则交换