本文最先發布在我的個人博客
http://www.lovestblog.cn
文字轉載自
http://jaskell.blogbus.com/logs/3272503.html，代碼是自己寫的一個測試類。
今天來了解一下堆排序的問題，“堆”是個很有趣的結構。通常“堆”是通過數組來實現的，這樣可以利用數組的特點快速定位指定索引的元素。而對“堆”的操作中定位某個元素簡直就是家常便飯。為什么這么說呢，我們來看看“堆”的定義：
在起始索引為 0 的“堆”中：
1) 堆的根節點將存放在位置 0
2) 節點 i 的左子節點在位置 2 * i + 1
3) 節點 i 的右子節點在位置 2 * i + 2
4) 節點 i 的父節點在位置 floor( (i - 1) / 2 ) : 注 floor 表示“取整”操作
在起始索引為 1 的“堆”中：
1) 堆的根節點將存放在位置 1
2) 節點 i 的左子節點在位置 2 * i
3) 節點 i 的右子節點在位置 2 * i + 1
4) 節點 i 的父節點在位置 floor( i / 2 ) : 注 floor 表示“取整”操作
以下是一個“堆”的圖例：
因此，當我們得知某個節點的索引為 i 時，可以通過以下“堆”的定義很容易地定位到它的子節點和父節點。
不僅如此，“堆”還有個特性：每個節點的鍵值一定總是大于（或小于）它的父節點。如果我們修改了某個節點的鍵值，這樣就會破壞“堆”的這個特性，因此這時我們就要根據該節點的新鍵值與它的父節點和子節點的鍵值進行比較，對該節點進行“上移”或者“下移”操作，使之能夠重新放置到合適位置。
這里我們了解一下“堆”的這兩個很重要的操作：“上移”和“下移”。
這里我們假設這是一個“最大堆”，即“堆”的根節點保存的是鍵值最大的節點。即“堆”中每個節點的鍵值都總是大于它的子節點。
當某節點的鍵值大于它的父節點時，這時我們就要進行“上移”操作，即我們把該節點移動到它的父節點的位置，而讓它的父節點到它的位置上，然后我們繼續判斷該節點，直到該節點不再大于它的父節點為止才停止“上移”。
現在我們再來了解一下“下移”操作。當我們把某節點的鍵值改小了之后，我們就要對其進行“下移”操作。首先，我們要取該節點的兩個左右子節點中鍵值較大的一個，與該節點進行比較，如果該節點小于它的這個子節點，就把該節點移動到它的子節點的位置，而讓它原來的子節點升到它的位置上。然后我們繼續判斷該節點，直到該節點不再小于它的左右子節點為止才停止“下移”。
現在我們再來看看如何把一個無序的序列建立成為一個“堆”？
根據“堆”的特性，我們可以從無序序列的最后一個節點的父節點開始，對其進行“下移”操作，直到序列的第一個節點為止。這樣就可以保證每個節點都在合適的位置上，也就建立起了一個“堆”。
但是“堆”并不是一個完全排序的序列，因為“堆”只保證了父節點與子節點的位置關系，但并不保證左右子節點的位置關系。那么我們如何進行“堆排序”呢？
由于一個“堆”的根節點必然是整個序列中最大的元素，因此對于一個排序的序列而言，每個“堆”中我們只能得到一個有效的元素。如果我們拿掉根節點，再對剩下的序列重新排列組成一個“堆”，反復如此，我們就可以依次得到一個完整的排序序列了。
當然，為了簡化操作，每次我們只需要把根節點與最后一個位置的節點交換，然后把最后一個位置排除之外，對根節點進行“下移”操作即可。
下面展示一段代碼簡單實現了堆排序，因為我覺得他說得比清楚了，我只是附上自己寫的一段代碼，這樣看我代碼會更容易理解了，希望能更加清晰理解堆排序：
package org.rjb.Heap;
/** *//**
* 通過不斷建大頂堆進行排序
* @author ljp
*
*/
public class HeapTest 
{
public static void main(String args[]){
//待排序的數組
int num[]={3,1,5,7,8,2,0,9};
//創建堆，并排好序
createHeap(num);
for(int j=0;j<num.length;j++){
System.out.print(num[j]+" ");
}System.out.println();
}
/** *//**
* 創建大頂堆
* @param num
*/
public static void createHeap(int[] num){
//從最后一個節點開始，對第i個節點，其父節點的位置為(int)Math.floor((i-1)/2)
for(int i=num.length-1;i>0;i--){
//如果當前節點比其父節點大的話就把當前節點上慮，既和父節點交換位置
if(num[i]>num[(int)Math.floor((i-1)/2)]){
siftUp(num,(int)Math.floor(i/2-1),i);
}
}
}
/** *//**
* 上慮操作
* @param num 待排序的數組
* @param h 下慮元素所處的層數
* @param key 當前節點在數組中的位置
*/
public static void siftUp(int[] num,int h,int key){
//先交換父子節點的位置
int temp=num[key];
num[key]=num[(int)Math.floor((key-1)/2)];
num[(int)Math.floor((key-1)/2)]=temp;
//對交換之后的節點可能存在下慮，既如果比子節點的鍵值要小的話還要和子節點位置進行互換
siftDown(num,h,key);
}
/** *//**
* 下濾操作
* @param num
* @param h
* @param key
*/
public static void siftDown(int[] num,int h,int key){
//lastLayer表示的是最后那層所在的層數
int lastLayer=(int)Math.floor(num.length/2-1);
//下慮操作最多下慮到最后一層
while(h<lastLayer){
//maxChild記錄的是鍵值最大的子孩子
int maxChild=0;
//flag用來標識當前節點是否有子孩子
boolean flag=false;
//index用來表示子孩子中具有最大鍵值的那個所在數組中的位置
int index=0;
//當2*key+2<num.length時表示有兩個子孩子
if(2*key+2<num.length){
//當有兩個子孩子時就找出具有最大鍵值的子孩子
if(num[2*key+2]>num[2*key+1]){
maxChild=num[2*key+2];
index=2*key+2;
}else{
maxChild=num[2*key+1];
index=2*key+1;
}
flag=true;
}else if(2*key+1<num.length){//當2*key+1<num.length時表示有一個子孩子
maxChild=num[2*key+1];
index=2*key+1;
flag=true;
}
//如果有子孩子就判斷最大子孩子的值比當前節點值的大小
if(flag){
if(maxChild>num[key]){
int temp=num[key];
num[key]=num[index];
num[index]=temp;
key=index;
}else{
break;
}
}
//h++表示下移一層
h++;
}
}
}
代碼就只是一個簡單的測試類了，只有幾個方法實現上慮下慮操作，以前只是知道堆排序，從沒有實現過，今天硬是鼓起勇氣寫了這個，還是能寫出來的，所以如果有地方寫得不怎么好的，希望各位多多指點。
posted on 2009-05-28 22:14
你假笨 閱讀(1255)
評論(0) 編輯 收藏