Java代碼為例講授堆的性質和根本操作和排序辦法

Java代碼為例講授堆的性質和根本操作和排序辦法。本站提示廣大學習愛好者：（Java代碼為例講授堆的性質和根本操作和排序辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是Java代碼為例講授堆的性質和根本操作和排序辦法正文

堆的性質
堆是一棵完整二叉樹，現實中可以經由過程一個數組來完成，它最主要的一特性質是：隨意率性節點都小於（年夜於）等於其子節點。將根節點最小的堆稱為最小堆，根節點最年夜的堆稱為最年夜堆。下圖給出了一個最年夜堆的示例及其數組表現，可以直不雅地看出每一個節點都比它的孩子們都要年夜。

在上圖中可以看到，完整二叉樹的節點可以從根節點編號為1開端按次序分列，對應數組A中的索引（留意此處下標是從1開端的）。給定一個節點i，我們很輕易可以獲得它的左孩子是2i，右孩子是2i+1，父節點是i/2

堆的根本操作
堆有兩種根本操作（上面以最小堆為例）：
拔出元素k：直接將k添加到數組最初，然後向上冒泡（bubble-up）調劑堆。向上冒泡操作：將要調劑的元素與其父節點比擬，假如年夜於其父節點則交流，直到恢復堆的性質。
提取最值：最值即根元素。然後將其刪除，令根元素=最初的葉子結點元素，然後從根元素開端向下冒泡（bubble-down）調劑堆。向下冒泡操作：每次應當從要調劑節點，其閣下孩子一共三個節點當選擇最小的子節點來交流（假如最小就是其自己就不消交流），直到恢復堆的性質。
現實中常常須要將一個包括n個元素無序數組樹立成堆，上面的Heap類中的結構辦法將展現若何經由過程_bubbleDown向下冒泡調劑來建堆。堆本質上是一棵完整二叉樹，樹高總為lognlog⁡n，每種根本操作的耗時操作都在於冒泡調劑以知足堆的性質，是以它們的時光龐雜度都是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;
  }
}

堆排序完成道理
分為兩步：
1.把數組排成二叉堆的次序
2.更換根節點和最初一個節點的地位，然後對根節點停止下沉操作。

完成：
能夠我的代碼和下面的動畫略有收支，不外根本道理差不多。

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