算法导论（第三版） 第六章 堆排序

前言

本人是计算机专业学渣一枚，因前面算法课上课神游太虚，因此现在亡羊补牢，本文主要是本人对于学习过程的记录，说的不对的地方欢迎指正。

一、堆

书上用了两种形式来表示堆：数组和二叉树

java当中本身没有堆这个数据结构，如果想使用堆的话，可以通过优先队列来创建：

Queue<Integer> minheap =new PriorityQueue<Integer>();//最小堆
Queue<Integer> maxheap =new PriorityQueue<Integer>((n1, n2) -> n2-n1);//最大堆
这里创建最大堆时使用了lambda表达式，目前还没学过，后面会持续进行更新。

java中优先队列的源码是维护了一个object的数组来实现的，python当中有堆这个数据结构，看源码貌似是维护了一个列表来实现的堆。

个人感觉以二叉树的形式来表示堆会更加直观，但如果要实现一个堆的话，通过维护一个数组可能会更加简单一些

下面这张图是如何根据某个元素的索引，找到她的父节点和左右子节点的索引（根节点的索引是1，如果是0的话，把i换成i-1就可以了）

堆分为两种形式：最小堆的最大堆。顾名思义，最大堆的意思就是，最大的摆在堆顶，也就是说子节点的值不大于父节点的值即可（根节点除外）；最小堆的意思就是，最小的摆在堆顶，也就是说子节点的值不小于父节点的值即可（根节点除外）。

在堆排序当中，使用的是最大堆，最小堆一般用于创建优先队列。（不清楚为什么java会选择提供优先队列这个数据结构，而不提供堆这个数据结构，虽然感觉提供两者之一即可，毕竟它们是可以互相转化的）

二、堆排序算法

当然是先附上一段堆排序的算法：

public class heapSort extends sort{public static void main(String[] args){int[] array = {1,12,32,93,25,8,3,24,65,13};sort(array);output(array);//打印数组的函数，继承父类当中的函数}/**** heapsort的关键：* 1、需要理解堆这个数据结构，比较特殊的一点是，对每个节点而言，如果第一个索引是0，*    那么第i个元素的左子节点和右子节点分别是2n+1和2n+2，因此不一定需要引入真正的堆*    这个数据结构，数组本身就可以看作一个堆* 2、堆排序的思路是比较简单的，首先把一个数组初始化为一个最大堆，然后交换第一个和*    最后一个元素，再重新开始最大堆化新的堆（去除最后一个元素的新堆），这个去除元素*    的步骤是最为关键的* 3、相比来说，堆排序是比插排和merge相对容易理解和记住的** @param array 等待排序的数组*/private static void sort(int[] array){int max_index = array.length-1;buildMaxHeap(array);output(array);System.out.println();for(int i = array.length-1 ; i >0 ; i--){exchange(array,i,0);max_index--;maxHeap(array,0,max_index);}}private static void buildMaxHeap(int[] array){for(int i = array.length/2 -1 ; i >=0 ; i--){maxHeap(array,i,array.length-1);}}private static void maxHeap(int[] array,int i,int max_index){if(i <= max_index && i <= array.length/2-1){int left = 2*i+1;int right = 2*i+2;int max = Math.max(array[left],array[i])==array[left]? left:i;if(right<= max_index)max = Math.max(array[right],array[max])==array[right]? right:max;if(max > i && max <= max_index){exchange(array,max,i);maxHeap(array,max,max_index);//书上认为这里可以用一个while循环来代替递归，在某些情况下可能会有更好的效率}}}private static void exchange(int[] array,int i, int j){int temp = array[i];array[i] = array[j];array[j] = temp;}
}

堆排序主要分成几个过程：
1、创建最大堆
2、将堆顶的元素与最后一个元素交换
3、忽略最后一个元素，对剩余的元素进行最大堆的维护（因为此时剩余的部分已经不是一个最大堆了）
4、重复步骤2、3
因为每次会把最大的元素放到堆的最右边的叶子节点上，过程结束后，自然就是一个从小到大排好序的数组了（如果逆序排序，将第一步换成创建最小堆就可以了）

创建最大堆的过程并不复杂（我说的不清楚的话，可以直接参考上面的代码），关键是得弄清楚从哪个节点开始进行这个过程。创建最大堆其实就是循环调用维护最大堆，关键是得从最后一个非叶节点开始进行这个过程，如果根节点是1，那么就是从索引为heapsize/2的这个节点一直到根节点（如果根节点是0，那就是heapsize-1/2）。

堆排序当中的核心部分是对最大堆的维护，维护的时候，必须要求被维护的节点的左子树和右子树都是最大堆。这也是为什么前面创建最大堆的时候我们得自底向上进行维护，因为从最右下的非叶节点开始维护才能保证整个过程当中，都能满足被维护的节点的左子树和右子树都是最大堆。

至于具体的维护过程，相对就比较简单了，无非就是找到被维护节点和它的子节点的最大值，如果子节点有比它大的，那么交换这个子节点和本身，然后对被维护节点接着进行最大堆的维护，递归到叶子节点为止。所以其实堆排序本身并不复杂，还是相对比较好理解的。

说说时间复杂度的问题（尤其是面试时候面试官会比较感兴趣的内容），堆排序的时间复杂度是O（nlogn），我觉得也不是很难理解（我本人对时间复杂度掌握的不是太好），我感觉是因为需要对长度为n的堆进行n/2次维护最大堆，而每次维护最大堆的时间复杂度是O（logn）（因为以被维护节点为根节点的堆的高度都是logn，所以需要进行logn-1次的swap，而每次的swap操作都是常数时间内完成的，因此每次维护最大堆的时间复杂堆是O（logn）），自然堆排序的时间复杂度就是O（nlogn）了。

三、优先队列

优先队列也是有两种形式：最小优先队列和最大优先队列。

这里以最大优先队列为例，书上介绍了4个比较关键的函数：
maximum：返回优先队列当中关键字最大的元素
insert：把元素插入到优先队列当中
extract-max：去掉优先队列当中关键字最大的元素
increase-key：把某元素的关键字增加为某一具体值

书上介绍的是，通过堆来实现优先队列。过程就是先根据关键字构建一个最大堆。
maximum：返回堆顶的对象
insert：在堆底添加一个关键字大小为minimum的对象，然后调用increase-key过程（这里insert的时候需要提供被插入对象的关键字）
extract-max：把堆底的对象和堆顶的对象swap，然后删除堆底的对象，再对整个堆进行最大堆维护
increase-key：把对应对象的关键字改为某个更大的值，然后将它和它的父对象进行关键字比较，如果更大，则swap，递归进行下去。

最小优先队列也是同理，换成最小堆即可。

四、记录书上几个比较有意思的题目

1、高度为h的堆最多、最少有多少个元素。

最多：2^（h+1）-1
最少：2^h
堆的高度就是最长简单路径的边的数量

2、为什么在build-max-heap当中需要从length/2到1递减，而不是从1到length/2递增

因为max-heap时要求子堆是最大堆

3、对于一个升序排列的包含n个元素的有序数组A来说，堆排的时间复杂度是多少？降序呢？

升序：这里书上说只需要进行堆的构建即可，因此时间复杂度是O（n）。但是我感觉好像不对，比如说1，2，3，4。进行堆的构建后产生的应该是：4，2，3，1，这并不是一个排好序的数组。
降序：O（n）+（n-1）logn
这里完全不明白为什么升序和降序排列的数组进行堆排会是这个时间复杂度。

4、6.5-6、6.5-7、6.5-8、6.5-9需要学习