堆排序
堆排序(Heapsort)是指利用[堆]这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
堆节点的访问
通常堆是通过一维数组来实现的。在数组起始位置为0的情形中:
- 父节点i的左子节点位置(2i+1);
- 父节点i的右子节点位置(2i+2);
- 子节点i的父节点在位置floor((i-1)/2);
堆的操作
在堆的数据结构中,堆中最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作:
- 最大堆调整(Max_Heapify): 将堆末端的子节点做调整,使得子节点永远小于父节点
- 创建最大堆(Build_Max_Heap): 将堆中所有数据重新排序
- 堆排序(HeapSort):移除在第一个数据的根节点,并做最大堆调整(递归运算)
实现示例
JAVA
1 | import java.util.Arrays; |
说明
摘自 https://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F#Java
用做笔记