算法 标签

二叉堆与堆排序 有更新!

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

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

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

二叉堆

性质

  • 根节点在数组中的位置是 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)
    • 比较当前节点与父节点
    • 不满足 堆性质* *则交换
阅读全文 »