阅读量:0
堆顶的删除
一.堆顶出列的原理
还记得我们刚开始说的嘛,如果我想要拿出最大的,那么下一个最大的会花落谁家.
那么就需要用到堆顶出列的原理了.
然后我们再对顶节点,进行向下调整就可以了.
二.堆顶出列的实现
1.覆盖最大元素并出列
先将顶节点拿出,然后用最后一个元素来赋值,再对整个长度减1,那么现在最大节点(堆顶)就出列了.
2.向下调整成为堆
出列后的数组,肯定不是一个最大堆,因为最后一个值上来了,我们需要进行调整,因为其他地方都没有变,只有我们的堆顶变了,所以我们只需要考虑堆顶向下调整,也就是下标为1的地方.
三.堆排序
最大堆每次都是最大的元素出列,那么就形成了一种排序的效果.
这是一种复杂度为log n的方法,效率很高.
同时,这种比较如果用在优先级里面,效率也很高,那么优先级队列用堆来实现也不错.
四,总结
删除堆的操作可以分为两个步骤：删除根节点和调整堆。
1.删除根节点：
- 将根节点与最后一个节点进行交换；
- 删除最后一个节点；
- 更新堆的大小。
2.调整堆：
- 从根节点开始，与其子节点比较，找到较大（小）的子节点；
- 如果根节点小于（大于）子节点，则交换两者的值；
- 重复上述步骤，直到节点没有子节点或满足堆的性质。
删除堆的操作时间复杂度为O(log n)，其中n是堆的大小。
