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