登入
首頁 所有文章 資料結構 Heap結構的基本介紹與範例
長也   2018-03-11 19:17:00(1年前)    922點閱   1喜歡  0收藏
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相反,將最小的資料至於最上端,實際上就只是整樹的條件顛倒,故不再贅述。

本文作者:長也

糾結與想不開的資管系學生,之前常碰PHP,現在常碰到的是Python,閒暇之餘就記錄一些筆記。

             

如要發表回覆,請先 登入

  0則回覆