堆排序 heapsort 数据结构堆排序

1. 介绍 1）什么是堆？
堆是一棵顺序存储的完全二叉树。
每个结点的关键字都小于或等于其所有子结点的关键字，这样的堆称为小根堆。
每个结点的关键字都大于或等于其所有子结点的关键字，这样的堆称为大根堆。
2）什么是堆排序？
堆排序（Heapsort）是指利用堆这种数据结构来进行排序的选择排序算法。堆积是一个近似完全二叉树的结构，并同时满足子结点的值总是小于（或者大于）它的父节点。

小根堆在排序算法中用于升序排列；
大根堆在排序算法中用于降序排序；

3）注意：

堆排序只适用于顺序结构。
堆排序的平均时间复杂度是 O(nlongn)，最好和最坏的时间复杂度也是 O(nlongn)。空间复杂度是 O(n)
堆排序是先建堆，依此输出堆顶元素（把堆顶元素换到数组后面）后调整堆。

2. 算法步骤以大根堆为例，

创建一个大根堆
交换堆顶和最后一个元素，剩下的元素重新调整为大根堆

3. 完整代码堆排序的全部代码如下（代码使用 Java 编写）：

// 堆排序 public void heapsort(int[] list) { build(list, list.length - 1); // 每调整一次堆，在数组最后就会多一个已经排好序的数。堆中个数为1时，不处理 for (int i = list.length - 1; i > 0; i--) { swap(list, 0, i); // 排好序的数组中增加一个数 adjust(list, 0, i - 1); } }// 建堆，自下而上建堆。先保证下面的是堆，再把前面的数加入堆中，调整为堆。 public int[] build(int[] list, int end) { // 从最后一个父节点开始 for (int i = (end - 1) / 2; i >= 0; i--) { adjust(list, i, end); } return list; }// 调整堆，从上自下调整。调整堆时，除了堆顶元素，其余的都满足堆的性质，所以从上向下把较大的元素移到上面 public int[] adjust(int[] list, int start, int end) { int maxIndex, left, right; for (int i = start; i <= (end - 1) / 2; i++) { maxIndex = i; left = 2 * i + 1; right = 2 * i + 2; if (left <= end && list[left] > list[maxIndex]) maxIndex = left; if (right <= end && list[right] > list[maxIndex]) maxIndex = right; if (maxIndex != i) { int tmp = list[i]; list[i] = list[maxIndex]; list[maxIndex] = tmp; } } return list; }// 交换元素。 void swap(int[] list, int a, int b) { int tmp = list[a]; list[a] = list[b]; list[b] = tmp; }

4. 代码说明以无序序列 a = [1,3,4,5,2] 为例，经过堆排序得到的排好序的数组是 a = [1,2,3,4,5] （也可以降序排列）。从此可以看出，把堆排序看成一个处理过程，那堆排序的输入是一个无序数组（链表不可以），输出是一个有序数组。这里以大根堆为例
堆排序
一个无序序列 a = [1,3,4,5,2] ，看出完全二叉树的物理存储结构。先建成一个初始的大根堆，建堆完成之后，数组是一个大根堆 a = [5,3,4,1,2] 。建堆完成之后，就需要将大根堆依次调整为有序序列 a = [1,2,3,4,5] 。
4.1 建堆
建堆的过程，就是从最后一个父节点开始，把每一棵树调整为堆的过程。

int[] build(int[] list, int end) { // 从最后一个父节点开始 for (int i = (end - 1)/2; i >= 0; i--) { adjust(list, i, end); } return list; }

首先来看一下，如果将一个无序序列建成大根堆。 a = [1,3,4,5,2] 画成完全二叉树之后，最后一个父节点是 [3] 。从二叉树的最后一个父节点 [3] 开始，依次向前遍历每一个父节点，直到根节点 [1] 为止。
从最后一个父节点开始要做什么事情呢？？
以当前父节点为根节点的二叉树，也就是 [3,5,2] ，将其调整为大根堆。
最后一个父节点的下标怎么计算？？
节点下标是节点在数组中的位置，所以是从 0 到 array.length - 1 。
如果一个节点下标是 i ，那么它的左子叶节点下标是 2*i+1 ，右子叶节点下标是 2*i+2。
所以，如果数组中最后一个父节点下标为 i ，最后一个元素下标是 end ，那么，最后一个元素一定是最后一个父节点的子节点。所以，就有 2*i+1 <= end 和 2*i+2 <= end ，所以可以得到最后一个父节点的下标是 (end-1)/2 。
建堆为什么是从最后一个父节点 (array.length-1)/2 开始向前遍历，而不是从 array.length-1 开始？
因为要保证调整堆时的参数是有意义的，没有越界产生。调整堆的代码中并没有判断下标是否合法。
建堆的顺序是按层次遍历的顺序遍历的，数组按从 (array.length-1)/2 到 0 访问，是按层次遍历的方式向前遍历的。
4.2 调整堆
调整堆的过程，就是把堆顶元素放在合适的位置。

// 调整堆的起始、终止位置要是有效的 int[] adjust(int[] list, int start, int end) { int maxIndex, left, right; for (int i = start; i <= (end - 1) / 2; i++) { maxIndex = i; left = 2 * i + 1; right = 2 * i + 2; if (left <= end && list[left] > list[maxIndex]) maxIndex = left; if (right <= end && list[right] > list[maxIndex]) maxIndex = right; if (maxIndex != i) { int tmp = list[i]; list[i] = list[maxIndex]; list[maxIndex] = tmp; } } return list; }

将哪个区间内的元素调整为堆？？
[start, end] ，包含左右两个下标的元素。因为调整堆的代码中并没有判断数组下标的合法性，所以传入的参数要是合法的。
怎么调整？？
首先，调整的前提是，这个树满足堆的性质，除了堆顶元素。
1）找出左右子节点中的最大值，然后和堆顶元素比较。