前言
堆排序是一种动态排序，它基于堆这种数据结构。堆的实质是一棵二叉树，只不过使用的是连续存储。堆分为小根堆和大根堆。小根堆的特点是根结点最小，其每一个子堆也满足这个特点。相反，大根堆的特点是根结点最大，且其每一个子堆也满足这一个特点。
算法
堆排序的实质是堆顶元素出堆，而后再维护堆的特点进行调整，继续出堆直至堆为空，排序完成。可按如下步骤进行：
1. 初始建堆。根据序列构造完全二叉树，并进行调整，以满足堆的特点，由于是升序排序，所以建立小根堆。因为每一个子堆也必须满足小根堆的特点，所以需要对结点自底向上进行调整。叶子结点显然已满足，所以直接从最后一个叶子结点的父节点开始调整，也就是从序号为n/2的位置开始调整到根结点位置（位置为1）结束。
对于每一个子堆的调整，其实质是可能存在孩子结点小于根结点，因而需要作向下调整。调整的方法是先保存根结点，再取其孩子结点（如果存在两个孩子结点则取其最小的一个），若这个结点值大于根结点值，则没有调整的必要，调整结束。否则，将这个结点值赋值给根结点，位置也赋值给根结点的位置，继续向下一层的孩子结点进行比较，直到调整到叶结点或者已经满足特性。
2. 堆顶元素出堆。出堆的过程是将堆顶元素和堆底元素交换，并且堆长度减1。由于交换后，堆特性可能已经被破坏，因此需要从新调整根结点的位置，重新向下调整。出堆操作不断进行下去，直至堆为空，排序结束。输出出堆的元素，即为升序序列。
例子
仍然以序列4,3,1,2,5为例：
1.初始建堆，堆长为5
初始二叉树
结点3向下调整。由于下层孩子结点2小于3，故2和3交换：
结点3调整
调整后序号2为根结点的子堆已满足小根堆特点。
结点4向下调整
可见此时已完全满足小根堆特点。
-
堆顶元素出堆。
首先输出1，且将堆顶堆底交换，即1和5交换。堆长为4：
1出堆
结点5向下调整后变为：
5向下调整
再输出2，将2和5交换，堆长为3。再将结点5向下调整后为：
2出堆
再输出3，将3和5交换，堆长为2。再将结点5向下调整后为：
3出堆
再输出4，将4和5交换，堆长为1。无须调整：
4出堆
再输出5，堆长为0，堆为空，排序结束：
5出堆
排序后序列为1,2,3,4,5。排序成功。
Codes
package com.fairy.InnerSort;
import java.util.Scanner;
/**
* 定义堆数据结构
* @author Fairy2016
*
*/
class Heap {
int data[];//元素
int length;//堆长
int max = 100;//堆空间大小，如不够每次再加
//初始建堆
void InitBuildHeap(int a[], int n) {
int i;
data = new int[n+1];
length = n;
for(i = 1; i <= n; i++) {
data[i] = a[i];
}
//从最后一个结点的父节点开始调整
for(i = n/2; i > 0; i--) {
AdjustDown(i);
}
}
//向下调整，以保持堆的特性以及子堆的特性
void AdjustDown(int k) {
data[0] = data[k];
for(int i = 2*k; i <= length; i*=2) {
if(i < length && data[i] > data[i+1])
i++;//由于一个结点的子节点可能有两个，还需比较大小
if(data[0] < data[i]) {
break;//如果其子节点都比它大，那么无须调整
} else {
data[k] = data[i];
k = i;//向上赋值，更新结点位置
}
}
data[k] = data[0];//赋值到调整后确定的位置
}
//向上调整，用于新入堆元素后保持堆的特性
void AdjustUp(int k) {
data[0] = data[k];
for(int i = k/2; i > 0; i /= 2) {
if(data[0] > data[i]) {
break;//如果父结点都比它小，那么无须调整
} else {
data[k] = data[i];
k = i;//向下赋值，更新结点位置
}
}
data[k] = data[0];
}
//元素出堆
int PopupHeap() {
int e = data[1];
//交换堆顶和堆底元素
data[1] = data[length];
data[length] = e;
//堆长度减1
length--;
//需要调整以满足堆特性
AdjustDown(1);
return e;
}
//判断堆是否已空
boolean IsEmpty() {
if(length >= 1) {
return false;
}
return true;
}
//元素入堆
void PushHeap(int e) {
//如果空间不够，需从新分配
if(length == data.length-1) {
int capa = max;
while(capa <= length+1) {
capa += max;
}
int help[] = new int[length];
for(int i = 1; i <= length; i++) {
help[i-1] = data[i];
}
data = new int[capa];
for(int i = 1; i <= length; i++) {
data[i] = help[i-1];
}
data[++length] = e;//新元素加入到堆底
} else {
data[++length] = e;//新元素加入到堆底
}
AdjustUp(length);
}
}
/**
* 堆排序
* @author Fairy2016
*
*/
public class HeapSort {
public static void sort(int a[], int n) {
Heap heap = new Heap();
heap.InitBuildHeap(a, n);
while(!heap.IsEmpty()) {
System.out.print(heap.PopupHeap()+" ");
}
}
public static void main(String args[]) {
int n;
int a[];
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()) {
n = scanner.nextInt();
if(n > 0) {
a = new int[n+1];
for(int i=1; i <= n; i++) {
a[i] = scanner.nextInt();
}
sort(a, n);
}
}
scanner.close();
}
}
后记
堆排序的时间复杂度由出堆操作和调整维护堆特性操作嵌套决定，出堆操作o(n)，调整操作o(log2(n))。所以时间复杂度为o(n*log2(n))。时间复杂度还算可以，但由于其用到了堆这个数据结构，空间复杂度为o(n)，相对来说不如快速排序。
堆的应用远远不止堆排序，而是作为一种重要的数据结构（优先队列）应用在实际开发中。本文虽然是简单的堆排序，但代码中对于堆这种数据结构还是进行了封装，包括其插入元素操作。其实无论是入堆还是出堆，元素操作之后还是要维护堆的特性不变，即大根堆仍然是大根堆，小根堆仍然是小根堆。更多关于堆的相关应用，在后面的贪心算法和分支限界算法文章会继续提到。
网友评论