Heap結構的基本介紹與範例 - 筆記長也

Heap結構的基本介紹與範例. 2018-03-11 19:17:00 資料結構. Heap - 堆積. 堆積是一棵二元樹，其樹根大於子樹，且不管左右大小為何，這是與二元搜尋樹最大的差異。

Heap結構的基本介紹與範例-筆記長也 關於 搜尋 ReactJS Laravel PHP 資結 登入 首頁 所有文章 資料結構 Heap結構的基本介紹與範例 Heap結構的基本介紹與範例 2018-03-1119:17:00  資料結構 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，需要調整。

我們在這裡採用由下往上整理（因為插入在最末端），過程不再贅述，請參考下圖： publicvoidinsert(){ if(last>=max-1){ System.out.println("Heaparrayisfull!"); }else{ System.out.println("inputdata:"); heapt[++last]=input.nextInt(); adsjustup(heapt,last); } }   publicvoidadsjustup(intads[],intindex){ 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比較則須互換。

publicvoiddel(){ if(last<=0) System.out.println("Heapisnull!"); else{ System.out.println("Inputdeldata："); intdeldata=input.nextInt(); intdelindex=search(deldata); if(delindex==0) System.out.println("DatanotFind!"); else{ heapt[delindex]=heapt[last]; heapt[last]=0; last--; adsjustdown(heapt,1); } } }   publicvoidadsjustdown(intarr[],intindex){ intdata=arr[index];//儲存該點資料 intindex_temp=index*2;//取得下一個階層 while(index_temp<=last){ if((index_temp=max-1){ System.out.println("Heaparrayisfull!"); }else{ System.out.println("inputdata:"); heapt[++last]=input.nextInt(); adsjustup(heapt,last); } } //如果父節點(上)比較大，則由上往下調整 //若比較小則由下往上調整 publicvoidadsjustup(intads[],intindex){ while(index>1){ if(ads[index]<=ads[index/2])//當父節點已經大於子結點就不再調整 { break; }else{//否則交換 exchange(ads,index); index/=2; } } } publicvoiddel(){ if(last<=0) System.out.println("Heapisnull!"); else{ System.out.println("Inputdeldata："); intdeldata=input.nextInt(); intdelindex=search(deldata); if(delindex==0) System.out.println("DatanotFind!"); else{ heapt[delindex]=heapt[last]; heapt[last]=0; last--; adsjustdown(heapt,1); //adsjustup(heapt,delindex); } } } publicvoidadsjustdown(intarr[],intindex){ intdata=arr[index];//儲存該點資料 intindex_temp=index*2;//取得下一個階層 while(index_temp<=last){ if((index_temp