根據妳需要java的要求, 寫了壹個實現。
這個是壹個整數最小優先的堆,只實現了加入功能。
應該還有刪除,清空等功能,但並不是必須的。
妳可以自己嘗試實現。
測試為生成壹組隨機數,加入隊列,每次加入後都察看壹下堆的最優先元素是多少。
如果還有疑問 ,
至郵件:tazerkinq@163.com
*/
public class Heap {
int[] heap; //堆的儲存空間
int size; //當前的元素的數量
Heap() {
size = 0; //初始化數量為0
heap = new int[1024]; //預留空間1024,為了操作方便,0位置被棄用
}
void add(int e){ //加入新的元素,也是維護堆的主要地方之壹
int i = ++size; //數量增加壹, 並用臨時變量記錄此位置
while(( 1<i ) && ( e<heap[i/2] )){ //判斷e是否小於父節點的元素, 如否,則停止
heap[i] = heap[i/2]; //如是, 則移動父節點元素當i記錄位置
i/=2; //i繼續向上叠代,指向剛才父節點的位置
}
heap[i] = e; //該位置即為元素最終位置
}
int peek(){ //返回堆頭的元素
return heap[1]; //數組下標1的元素即是
} //當然如果當前元素為空的話,返回的則是初始值
int size(){ //返回當前元素數目
return size;
}
public static void main(String[] args) {
Heap h = new Heap();
for(int i=0;i<100;i++){
int k=(int)(10000*Math.random()); //隨機生成壹個整數
h.add(k); //加入到堆中
System.out.printf(
"Currently adding number is %5d.\t"+
"Currently priority number is %5d.%n",k,h.peek()); //輸出生成的隨機數,並且輸出該堆的優先元素
}
}
}