二叉堆与堆排序 有更新!
二叉堆是一组能够用堆有序的完全二叉树排序的元素,一般用数组来存储。
大顶堆, 每个结点的值都大于或等于其左右孩子结点的值,其顶部为最大值。
小顶堆,每个结点的值都小于或等于其左右孩子结点的值,其顶部为最小值。
二叉堆
性质
- 根节点在数组中的位置是 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)
- 比较当前节点与父节点
- 不满足 堆性质* *则交换