堆
堆排序中用到的是二叉堆，它其实就是一棵近似于完全二叉树树按照层次遍历得到的数组。而堆排序中只要是利用最大(小)堆来完成的。最大(小)堆其实就是满足在父亲节点、左孩子、右孩子中父亲点是最大(小)值的堆。显然，根节点的左子树与右子树也可以看成最大(小)堆。而优先队列算是堆排序算法的一个典型应用，文章后面也会讲到。
排序过程
排序的算法如下:
HEAPSORT(A)
//将带排序的数组A构建成最大堆,A的起始下标为0
1.BUILD-MAX-HEAP(A)
//每次从堆中取出最大的元素，然后与堆最末尾的元素交换，并将此元素从堆中提出，再更新堆的状态维持
其最大堆的性质，知道堆的元素只有一个位置，排序就结束了。
2.for i=A.length-1 downto 1
3. exchangeA[1] with A[i]
4. A.heapsize=A.heapsize-1
5. UPDATEMAXHEAP(A,0)
BUILD-MAX-HEAP(A)
1. A.heapsize=A.length
2. for i=A.length/2 downto 1
3. UPDATEMAXHEAP(A,i)
UPDATEMAXHEAP(A,i)
1. left=2*i+1 //找到i的左孩子
2. right=2*i+2 //找到i的右孩子
//找到i,i的左孩子、右孩子三者中的最大值所在位置largest。
3. if left<=A.heapsize and A[left]>A[i]
4. largest=left
5. else lagerst=i;
6. if r<=A.heapsize and A[r]>A[largest]
7. largest=r
8.//最大值A[largest]放到父亲节点i的位置
8. if largest!=i //递归结束条件
9. exchange A[i]with A[largest]
10. UPDATEMAXHEAP(A,largest)
从这里可以总结出堆排序的最重要两个步骤就是：1.构建最大(小)堆。2.更新堆，保证最大(小)堆的性质
堆代码如下:
/**
* @author CoderGang
* 堆排序的实现
*/
public class HeapSort {
/**
* 根据数组对象构造最大堆
* @param arry，数组对象
*/
private void buildMaxHeap(int[] arry ){
for(int i= (arry.length>>1)-1;i>=0;i--){
//updateMaxHeapRecursive(arry,i,arry.length);
updateMaxHeapLoop(arry,i,arry.length);
}
}
/**
* 更新堆的状态，非递归版本
* @param heap 堆
* @param parent 父亲结点
* @param heapSize 堆的大小
*/
private void updateMaxHeapLoop(int[] heap,int parent,int heapSize){
int right = (parent << 1) + 2;
int left = (parent << 1) + 1;
int largest;
while (true){
if (left<heapSize && heap[left] > heap[parent]) {
largest = left;
} else {
largest = parent;
}
if (right<heapSize && heap[right] > heap[largest]) {
largest = right;
}
if (largest != parent) {
int tmp = heap[largest];
heap[largest] = heap[parent];
heap[parent] = tmp;
}else {
break;
}
right=(largest<<1)+2;
left=(largest<<1)+1;
parent=largest;
if(right>=heapSize && left>=heapSize) {
break;
}
}
}
/**
* 更新堆的状态，递归版本
* @param heap 堆
* @param parent 父亲结点
* @param heapSize 堆的大小
*/
private void updateMaxHeapRecursive(int[] heap,int parent,int heapSize) {
int right = (parent << 1) + 2;
int left = (parent << 1) + 1;
int largest;
if (left<heapSize && heap[left] > heap[parent]) {
largest = left;
} else {
largest = parent;
}
if (right<heapSize && heap[right] > heap[largest]) {
largest = right;
}
if (largest != parent) {
int tmp = heap[largest];
heap[largest] = heap[parent];
heap[parent] = tmp;
//updateMaxHeapRecursive(heap, largest,heapSize);
updateMaxHeapRecursive(heap, largest,heapSize);
}
}
/**
* 对数组进行排序
* @param arry，要排序的数组
*/
public void sort(int[] arry) {
buildMaxHeap(arry);
int heapSize=arry.length;
for(int i=arry.length-1;i>0;i--){
int tmp=arry[i];
arry[i]=arry[0];
arry[0]=tmp;
heapSize--;
//updateMaxHeapRecursive(arry,0,heapSize);
updateMaxHeapLoop(arry, 0,heapSize);
}
for (int i:arry) {
System.out.print(i+" ");
}
}
public static void main(String [] args) {
int []a=/*{1,2,3,4,5};*/{1,5,8,3,4,14,9,86,54,1654,15,45,6,13,45,16,4,78,9,1,3,4,8,4,64,748915};
new HeapSort().sort(a);
}
}
