漫画：什么是堆排序？

漫画：什么是二元堆？ （修订版）

那么，如何使用这个二叉堆呢？我们将在本期详细讲一下。

我们回顾一下二叉堆和最大堆的特点：

1.二叉堆本质上是一棵完全二叉树

2.最大堆的顶部是整个堆中最大的元素

当我们删除一个最大堆的顶部（不是完全删除，而是最后替换）时，经过自我调整，第二大元素会被交换，成为新的最大堆顶部。

如上图所示，当我们删除值为10的堆顶节点时，经过调整，一个值为9的新节点将取代它；当我们删除值为9的堆顶节点时，经过调整，将会替换一个值为8的新节点。该节点将被替换.

由于二叉堆的这个特性，每次我们删除旧堆顶时，调整后的新堆顶都会是一个大小仅次于旧堆顶的节点。那么我们只需要反复删除堆顶，反复调整二叉堆，得到的集合就会成为有序集合。流程如下：

删除节点9，节点8 成为新的堆顶：

删除节点8，节点7 成为新的堆顶：

删除节点7，节点6 成为新的堆顶：

删除节点6，节点5 成为新的堆顶：

删除节点5，节点4 成为新的堆顶：

删除节点4，节点3 成为新的堆顶：

删除节点3，节点2 成为新的堆顶：

至此，我们原来的最大堆就变成了从小到大的有序集合。前面说过，二叉堆实际上是存储在数组中的。数组中的元素排列如下：

由此，我们可以总结出堆排序算法的步骤：

1、将无序数组构造成二叉堆。

2、循环删除堆顶元素，移动到集合末尾，并调整堆生成新的顶元素。

公共类堆排序{

/**

*水槽调整

* @param要调整的数组堆

* @paramparentIndex 要下沉的父节点

* @paramparentIndex 堆的有效大小

*/

公共静态无效downAdjust（int []数组，intparentIndex，int长度）{

//temp保存父节点值以供最终赋值

int temp=数组[父索引];

int 子索引=2 * 父索引+ 1;

while (childIndex 长度) {

//如果有右孩子且右孩子大于左孩子的值，则定位右孩子

if (childIndex + 1 长度数组[childIndex + 1] 数组[childIndex]) {

子索引++；

}

//如果父节点小于任意子节点的值，则直接跳出

if (temp=数组[子索引])

休息；

//不需要实际交换，只是单向赋值

数组[父索引]=数组[子索引];

父级索引=子级索引；

子索引=2 * 子索引+ 1;

}

数组[父索引]=临时；

}

/**

* 堆排序

* @param要调整的数组堆

*/

公共静态无效heapSort（int []数组）{

//1. 将无序数组构造成二叉堆。

for (int i=(array.length-2)/

2；我=0;我- ） {

downAdjust(array, i, array.length);

}

System.out.println(Arrays.toString(array));

//2、循环删除堆顶元素，移动到集合末尾，并调整堆生成新的堆顶。

for (int i=array.length - 1; i 0; i--) {

//将最后一个元素与第一个元素交换

int temp=数组[i];

数组[i]=数组[0]；

数组[0]=温度；

//调整下沉的最大堆

向下调整（数组，0，i）；

}

}

公共静态无效主（字符串[] args）{

int[] arr=new int[] {1,3,2,6,5,7,8,9,10,0};

堆排序（arr）；

System.out.println(Arrays.toString(arr));

}

}

二叉堆的节点下沉调整（downAdjust方法）是堆排序算法的基础。这个调整操作本身的时间复杂度是多少？

假设二叉堆一共有n个元素，那么下沉调整最坏情况的时间复杂度等于二叉堆的高度，即O(logn)。

我们回顾一下堆排序算法的步骤：

1、将无序数组构造成二叉堆。

2、循环删除堆顶元素，移动到集合末尾，并调整堆生成新的顶元素。

第一步是将无序数组构建成二叉堆，这需要n/2 次循环。 downAdjust方法每个循环都会调用一次，因此第一步的计算规模为n/2 * logn，时间复杂度为O(nlogn)。

第二步，需要n-1个循环。 downAdjust方法每个循环都会调用一次，因此第二步的计算规模为(n-1) * logn，时间复杂度为O(nlogn)。

两个步骤是并行的，因此总体时间复杂度也是O(nlogn)。