堆積是一棵二元樹,其樹根大於子樹,且不管左右大小為何,這是與二元搜尋樹最大的差異。
將二元樹轉為堆積的方式有兩種,第一種是由上而下整理,這種整理方式有兩種:
1.由樹根開始,與其左右節點比較,若樹根較大,則不必交換,反之則要交換
2.由樹根開始,先找出下一個階層最大的節點,再與樹根比較,若樹根較大則不必交換,反之要交換。這種方法優點是只需要交換一次。
我們利用兩種方法取得了不同的heap,同筆資料的heap不是只有一種,只要符合根大於子即可。
另外一種方法則是由下往上,先取得整棵樹的節點數,假設n,取其n/2,從節點n/2開始至樹根相比。
舉例,先將一棵二元樹依序由上向下編號:
此棵樹共有5個節點,(int)5/2=2,由第2節點開始,取其最大的子節點第4節點30與第2節點比較,因30>29則需交換,以此類推。
heap的加入十分容易,先依照完整二元樹的方式加入節點(即每個階層滿了才能往下一個階層加入,如在陣列中則是一直向下新增),如我們要新增50:
加入在最後一個之後,由於50>10不符合heap,需要調整。我們在這裡採用由下往上整理(因為插入在最末端),過程不再贅述,請參考下圖:
public void insert() {
if (last >= max - 1) {
System.out.println("Heap array is full!");
} else {
System.out.println("input data:");
heapt[++last] = input.nextInt();
adsjustup(heapt, last);
}
}
public void adsjustup(int ads[], int index) {
while (index > 1) {
if (ads[index] <= ads[index / 2])//當父節點已經大於子結點就不再調整
{
break;
} else {//否則交換
exchange(ads, index);
index /= 2;
}
}
}
heap的刪除是以最後一個節點來代替要被刪除的節點,並由上往下整理(因為通常會向上替代,除非刪除的是最後一個節點),如圖要刪除30:
先將10換到30的位置,再由上往下檢查,50與10比較不必互換,29與10比較則須互換。
public void del(){
if(last<=0)
System.out.println("Heap is null!");
else{
System.out.println("Input del data :");
int deldata=input.nextInt();
int delindex=search(deldata);
if(delindex==0)
System.out.println("Data not Find!");
else{
heapt[delindex]=heapt[last];
heapt[last]=0;
last--;
adsjustdown(heapt, 1);
}
}
}
public void adsjustdown(int arr[],int index){
int data=arr[index];//儲存該點資料
int index_temp=index*2;//取得下一個階層
while(index_temp<=last){
if((index_temp<last)&&arr[index_temp]<arr[index_temp+1]) //取得該階層最大的點
index_temp++;
if(arr[index_temp]<=arr[index_temp/2])//如果取得的最大值比上階層小,則略過不交換
break;
else{
arr[index_temp/2]=arr[index_temp];
index_temp*=2;//繼續比較下面的子結點
}
}
arr[index_temp/2]=data;
}
這裡沒有採用由下而上是因為當刪除較前的節點,該由下而上檢查的方法是一旦發現其中一個父節點已經大於子節點,就停止檢查,故可能有所遺漏。
這裡我使用的方法是每次刪除,就由第一個向下檢查,這樣當然相對沒有效率。實際上可以比對替代後的節點大小,採取不同的調整方式。
import java.util.Scanner;
class heapA {
final int max = 50;
int[] heapt = new int[max];
int last = 0;
Scanner input = new Scanner(System.in);
public void insert() {
if (last >= max - 1) {
System.out.println("Heap array is full!");
} else {
System.out.println("input data:");
heapt[++last] = input.nextInt();
adsjustup(heapt, last);
}
}
//如果父節點(上)比較大,則由上往下調整
//若比較小則由下往上調整
public void adsjustup(int ads[], int index) {
while (index > 1) {
if (ads[index] <= ads[index / 2])//當父節點已經大於子結點就不再調整
{
break;
} else {//否則交換
exchange(ads, index);
index /= 2;
}
}
}
public void del(){
if(last<=0)
System.out.println("Heap is null!");
else{
System.out.println("Input del data :");
int deldata=input.nextInt();
int delindex=search(deldata);
if(delindex==0)
System.out.println("Data not Find!");
else{
heapt[delindex]=heapt[last];
heapt[last]=0;
last--;
adsjustdown(heapt, 1);
//adsjustup(heapt, delindex);
}
}
}
public void adsjustdown(int arr[],int index){
int data=arr[index];//儲存該點資料
int index_temp=index*2;//取得下一個階層
while(index_temp<=last){
if((index_temp<last)&&arr[index_temp]<arr[index_temp+1]) //取得該階層最大的點
index_temp++;
if(arr[index_temp]<=arr[index_temp/2])//如果取得的最大值比上階層小,則略過不交換
break;
else{
arr[index_temp/2]=arr[index_temp];
index_temp*=2;//繼續比較下面的子結點
}
}
arr[index_temp/2]=data;
}
public int search(int data){
int delindex =1 ;
for(delindex=1;delindex<=last;delindex++){
if(heapt[delindex]==data)
return delindex;
}
return 0;
}
public void exchange(int temp[], int index) {
int extemp = temp[index];
temp[index] = temp[index / 2];
temp[index / 2] = extemp;
System.out.printf("L:%d,EX:%d", last, index);
}
public void show(){
for (int c_index =1;c_index<=last;c_index++)
System.out.printf(" %d",heapt[c_index]);
}
}
public class heapArray {
public static void main(String[] args) {
heapA obj = new heapA();
Scanner input = new Scanner(System.in);
System.out.println("1");
while (true) {
int doing = input.nextInt();
switch (doing) {
case 1:
obj.insert();
break;
case 2:
obj.show();
break;
case 3:
obj.del();
break;
}
}
}
}
最小堆積則與上面的範例MAX HEAP相反,將最小的資料至於最上端,實際上就只是整樹的條件顛倒,故不再贅述。
關於作者
粉絲專頁
文章分類