快捷導(dǎo)航

Java代碼為例講解堆的性質(zhì)和基本操作以及排序方法

更新時間：2016年06月08日 12:01:34 作者：林壽山

堆數(shù)據(jù)結(jié)構(gòu)可以看作一顆完全二叉樹,因而又被成為二叉堆,這里我們以Java代碼為例講解堆的性質(zhì)和基本操作以及排序方法,需要的朋友可以參考下

堆的性質(zhì)
堆是一棵完全二叉樹，實際中可以通過一個數(shù)組來實現(xiàn)，它最重要的一個性質(zhì)是：任意節(jié)點都小于（大于）等于其子節(jié)點。將根節(jié)點最小的堆稱為最小堆，根節(jié)點最大的堆稱為最大堆。下圖給出了一個最大堆的示例及其數(shù)組表示，可以直觀地看出每個節(jié)點都比它的孩子們都要大。

201668115430035.jpg (815×272)

在上圖中可以看到，完全二叉樹的節(jié)點可以從根節(jié)點編號為1開始按順序排列，對應(yīng)數(shù)組A中的索引（注意此處下標(biāo)是從1開始的）。給定一個節(jié)點i，我們很容易可以得到它的左孩子是2i，右孩子是2i+1，父節(jié)點是i/2

堆的基本操作
堆有兩種基本操作（下面以最小堆為例）：
插入元素k：直接將k添加到數(shù)組最后，然后向上冒泡（bubble-up）調(diào)整堆。向上冒泡操作：將要調(diào)整的元素與其父節(jié)點比較，如果大于其父節(jié)點則交換，直到恢復(fù)堆的性質(zhì)。
提取最值：最值即根元素。然后將其刪除，令根元素=最后的葉子結(jié)點元素，然后從根元素開始向下冒泡（bubble-down）調(diào)整堆。向下冒泡操作：每次應(yīng)該從要調(diào)整節(jié)點，其左右孩子一共三個節(jié)點中選擇最小的子節(jié)點來交換（如果最小就是其本身就不用交換），直到恢復(fù)堆的性質(zhì)。
實際中經(jīng)常需要將一個包含n個元素?zé)o序數(shù)組建立成堆，下面的Heap類中的構(gòu)造方法將展示如何通過_bubbleDown向下冒泡調(diào)整來建堆。堆實質(zhì)上是一棵完全二叉樹，樹高總為lognlog⁡n，每種基本操作的耗時操作都在于冒泡調(diào)整以滿足堆的性質(zhì)，因此它們的時間復(fù)雜度都是O(nlogn)O(nlog⁡n)。
Java示例：

//上浮
public void swim(int k){
  while(k/2>=1 && less(pq[k/2],pq[k])){
    exch(pq,k/2,k);
    k=k/2;
  }
}
//下沉
private void sink() {
  int k=1;
  while(2*k<N){
    int j=2*k;
    if(less(pq[j],pq[j+1])) j++;
    if(less(pq[k],pq[j])) exch(pq,k,j);
    else break;
    k = j;
  }
}

堆排序?qū)崿F(xiàn)原理
分為兩步：
1.把數(shù)組排成二叉堆的順序
2.調(diào)換根節(jié)點和最后一個節(jié)點的位置，然后對根節(jié)點進行下沉操作。

實現(xiàn)：
可能我的代碼和上面的動畫略有出入，不過基本原理差不多。

public class HeapSort extends BaseSort {

  private int N;
  @Override
  public void sort(Comparable[] a) {
    N =a.length-1;
    int k = N/2;
    while(k>=1){
      sink(a,k);
      k--;
    }
    k = 1;
    while(k<=N){
      exch(a,k,N--);
      sink(a,k);
    }
  }
}

您可能感興趣的文章: