Heap結構的基本介紹與範例

Heap - 堆積

堆積是一棵二元樹，其樹根大於子樹，且不管左右大小為何，這是與二元搜尋樹最大的差異。

將二元樹調整為堆積

將二元樹轉為堆積的方式有兩種，第一種是由上而下整理，這種整理方式有兩種：

1.由樹根開始，與其左右節點比較，若樹根較大，則不必交換，反之則要交換

2.由樹根開始，先找出下一個階層最大的節點，再與樹根比較，若樹根較大則不必交換，反之要交換。這種方法優點是只需要交換一次。

我們利用兩種方法取得了不同的heap，同筆資料的heap不是只有一種，只要符合根大於子即可。

另外一種方法則是由下往上，先取得整棵樹的節點數，假設n，取其n/2，從節點n/2開始至樹根相比。

舉例，先將一棵二元樹依序由上向下編號：

此棵樹共有5個節點，(int)5/2=2，由第2節點開始，取其最大的子節點第4節點30與第2節點比較，因30>29則需交換，以此類推。

實作範例(MAX-HEAP)

heap的加入

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的刪除

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;

            }
        }
    }

}

Min Heap

最小堆積則與上面的範例MAX HEAP相反，將最小的資料至於最上端，實際上就只是整樹的條件顛倒，故不再贅述。