快捷導(dǎo)航

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

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

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

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

201668115430035.jpg (815×272)

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

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

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

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);
    }
  }
}

您可能感興趣的文章: