堆排序
堆排序（heapsort）兼有插入排序和合并排序的特点。类似于合并排序：它的运行时间是O(nlgn)；类似于插入排序，它是一种原地排序算法：在任何时候，数组中只有常数个元素存储在输入数组意外。堆排序将插入排序和合并排序的优点结合起来。
堆
堆数据结构是一种数组对象，可以被视为一棵完全二叉树。数的每一层都是填满的，最后一层可能除外。
表示堆的数组A是一个具有两个属性的对象：length[A]是数组中的元素个数，heap-size[A]是存放在A中的堆的元素个数。即A[heap-size[A]]之后的元素都不属于相应的堆，此处heap-size[A]<=length[A]。
数的根为A[1],给定某个节点下标i，父节点和左右儿子的关系为：
PARENT(i) = floor(i/2);
LEFT(i) = 2i;
RIGHT(i) = 2i + 1;
二叉堆有两种，最大堆：堆中某个结点的值之多和其父节点一样大；最小堆：堆中某个结点的值一定不小于父节点。堆排序算法中使用最大堆，最小堆通常在构造优先队列时使用。
堆结构上的基本操作和运行时间：
MAX-HEAPIFY:O(lgn)，保持最大堆性质
BUILD-MAX-HEAP:以线性时间运行，在无序的输入数组基础上构造出最大堆
HEAPSORT:运行时间为O(nlgn),对一个数组进行原地排序
保持堆的性质MAX-HEAPIFY
对输入数组A和下标i，假定LEFT[i]和RIGHT[i]为根的两颗子树都是最大堆，但A[i]可能小于其子女，违反了最大堆性质。MAX-HEAPIFY用于调整A[i]的位置，使以i为根的子树成为最大堆。
MAX-HEAPIFY的基本方法是，从A[i],A[Left[i]]和A[Right[i]]中找出最大的，如果A[i]最大，则堆已经是最大堆；否则将i结点值和最大的子节点值交换，再对交换过的结点为根的子树递归调用MAX-HEAPIFY。
MAX-HEAPIFY的时间复杂度是O(lgn)，即对一个高度为h的结点所需的运行时间为O(h)。
建堆BUILD-MAX_HEAP
建堆过程：自底向上地将一个数组A[1..n]变成一个最大堆。
子数组A[(floor(n/2)..n]都是叶子节点，BUILD-MAX_HEAP过程对堆中的非叶子节点有调用一次MAX-HEAPIFY。
BUILD-MAX_HEAP的时间复杂度是O(n)。
堆排序算法HEAPSORT
堆排序算法的过程：
1.用BUILD-MAX_HEAP将数组A[1..n]构造成一个最大堆；
2.交换数组中最大元素A[1]和A[n]，并将堆中结点n去掉（减小heap-size[A])；
3.对A[1..n-1]调用MAX-HEAPIFY使其恢复为最大堆；
4.重复2-3步骤（此时n将为n-1)。
HEAPSORT过程的时间代价是O(nlgn)。
完整的java版堆排序代码如下：
[code lang=”java”]public class HeapSort{
private static int[] A = {3, 2, 6, 1, 9, 7, 8, 5, 4};
public static int left(int i){
//数组下标从0开始，此处有调整
return 2 * i + 1;
}
public static int right(int i){
//数组下标从0开始，此处有调整
return 2 * i + 2;
}
public static int parent(int i){
return (int)Math.floor(i / 2 );
}
public static void maxHeapify(int i, int heapSize){
int l = left(i);
int r = right(i);
int largest = 0;
if(l < heapSize && A[l] > A[i]){
largest = l;
}else{
largest = i;
}
if(r < heapSize && A[r] > A[largest]){
largest = r;
}
if(largest != i){
int temp = A[largest];
A[largest] = A[i];
A[i] = temp;
maxHeapify(largest, heapSize);
}else{
return;
}
}
public static void buildMaxHeap(){
int heapSize = A.length;
for(int i = (int)Math.floor(heapSize / 2) - 1; i >= 0; i--){
maxHeapify(i, heapSize);
}
}
public static void heapSort(){
buildMaxHeap();
int heapSize = A.length;
for(int i = A.length - 1; i >0; i--){
int temp = A[i];
A[i] = A[0];
A[0] = temp;
heapSize--;
maxHeapify(0, heapSize);
}
}
public static void main(String[] args){
for(int i : A){
System.out.print(i + ",");
}
System.out.print("\n");
heapSort();
for(int i : A){
System.out.print(i + ",");
}
} }[/code]
