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