什么是堆？

“堆”是一種常用的數(shù)據(jù)結(jié)構(gòu)，也是一種特殊的樹。我們來看看，到底什么樣的樹才是堆。堆有如下兩點要求，滿足這兩點要求的，就是一個堆。

1.堆是一個完全二叉樹
2.堆中的每個節(jié)點值都必須大于等于（或小于等于）其子樹每個節(jié)點的值。

第一點，堆是完全二叉樹。那就意味除了樹的最后一層，其他層節(jié)點個數(shù)都是滿的，最后一層的節(jié)點都靠左排列。
第二點，換種說法就是，堆中的每個節(jié)點都大于等于（或小于等于）其左右節(jié)點的值。

對于每個節(jié)點值都大于等于子樹每個節(jié)點的值的堆，稱之為“大頂堆”。對于每個節(jié)點值都小于等于子樹中每個節(jié)點值的堆，稱之為“小頂堆”。“大頂堆”的第一個元素為最大值，“小頂堆”的第一個元素為最小值。

堆有哪些操作？

完全二叉樹比較適合用數(shù)組來存儲，這樣比較節(jié)省存儲空間。因為不需要存儲左右子節(jié)點的指針，只要通過數(shù)組的下標(biāo)，就可以很方便的找到一個節(jié)點的左右子節(jié)點和父節(jié)點。

下面是一個大頂堆的例子,數(shù)組下標(biāo)從1開始。

從圖中可以看出，對于任意一個下標(biāo)為i的節(jié)點，這個節(jié)點的左子節(jié)點是下標(biāo)為 i*2 的節(jié)點，右子節(jié)點是下標(biāo)為 i * 2 + 1的節(jié)點，父節(jié)點是 i / 2 的節(jié)點。

知道了如何存儲一個堆后，接著看看堆有哪些操作。堆有兩個非常核心的操作：往堆中插入一個元素、刪除堆頂元素。

1.往堆中插入一個元素
往堆中插入一個元素后，堆結(jié)構(gòu)需要繼續(xù)滿足堆的兩個特性。將新元素放到堆最后，如果不符合堆的特性，那就需要進(jìn)行調(diào)整重新滿足堆的特性，這個調(diào)整的過程叫做“堆化”。

堆化有兩種，“從上往下”和“從下往上”。下面使用“從下往上”的方式來實現(xiàn)往堆中插入元素。

“從下往上”這種堆化方式非常簡單，新插入的節(jié)點與父節(jié)點比較大小。如果不滿足子節(jié)點小于等于父節(jié)點，那么就互換兩個節(jié)點。重復(fù)這個過程，直到父子節(jié)點之間滿足這種關(guān)系為止。

根據(jù)上面的思路，插入元素的代碼可以結(jié)合著圖示一起看。

  public class Heap{
    private int[] arr;  //二叉樹數(shù)組
    private int count;  //堆中已經(jīng)存儲的數(shù)據(jù)個數(shù)
    public Heap(int capacity){
      arr = new int[capacity + 1];
      n = capacity;
      count = 0;
    }

  public void insert(int data){
       if(count + 1 >= arr.length){
            throw new IllegalArgumentException();
       }
       count++;
       arr[count] = data;
       int pos = count;
       while (pos / 2 > 0 && arr[pos / 2] < arr[pos]){
            swap(pos,pos / 2);
            pos = pos / 2;
       }
   }
}

2.刪除堆頂元素
刪除堆頂元素后，同樣也需要保證堆能夠滿足那兩個特性。刪除堆頂元素后，我們可以把堆中最后一個元素放到堆頂。然后利用父子節(jié)點對比方法，對于不滿足父子節(jié)點大小關(guān)系的節(jié)點，互換兩個節(jié)點，重復(fù)進(jìn)行這個過程，直到父子節(jié)點之間滿足二叉堆的特性為止。這里使用的是“從上往下”的方法進(jìn)行堆化。

根據(jù)上面的思路，刪除堆頂元素的代碼可以結(jié)合著圖示一起看。

public void removeTop(){
    if(count == 0 ){
        retun;
    }
    a[1] = arr[count];
    count--;
    int  pos = 1;
    int maxPos = 1;
    while(true){
        if(pos * 2 <= count && arr[pos * 2] > arr[pos]){
            maxPos = pos * 2;
        }
        if(pos * 2 + 1 <= count && arr[pos * 2 + 1] > arr[pos]){
            maxPos = pos * 2 + 1;
        }
        if(maxPos == pos){
            break;
        }
        swap(arr,pos,maxPos);
        pos = maxPos;
    }
}

一顆包含n個節(jié)點的完全二叉樹，樹的高度不會超過。堆化的過程是順著節(jié)點的路徑進(jìn)行比較交換，所以堆化的時間復(fù)雜度跟樹的高度成正比，也就是O(log n)。因為插入和刪除都是做的堆化操作，所以他們的時間復(fù)雜度都是O(log n)。

堆排序怎么實現(xiàn)？

我們可以借助堆這種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的排序算法，就叫堆排序。這種排序算法的時間復(fù)雜度很長穩(wěn)定，是O(n log n)。堆排序的過程可以分為兩個步驟，構(gòu)建堆和排序。

1.構(gòu)建堆
將待排序的數(shù)據(jù)構(gòu)建成堆，構(gòu)建堆有兩種思路。

第一種就是借助前面說的，在堆中插入一個元素。我們可以假設(shè)最開始堆中只包含一個下標(biāo)為1的數(shù)據(jù)。然后我們調(diào)用插入操作，將下標(biāo)從2到n的數(shù)據(jù)依次插入到堆中。這樣我們就將包含n個數(shù)據(jù)的數(shù)組，組織成了堆。

第二種實現(xiàn)，和第一種思路相反。第一種建堆處理過程是從前往后處理數(shù)組數(shù)據(jù)，每個數(shù)據(jù)插入堆中，都是從下往上堆化。而第二種實現(xiàn)思路是從后往前處理數(shù)組，并且每個數(shù)據(jù)都是從上往下堆化。

可以參照下面的例子，葉子節(jié)點堆化只能和自己比較，所以我們直接從第一個非葉子節(jié)點開始，依次堆化就可以。

對照著圖示，將建堆的過程翻譯成代碼。

    /**
     * 構(gòu)造堆
     */
    private void buildHeap(){
        for(int i = count / 2; i>0; i--){
            downAdjust(i,count);
        }
    }

    /**
     * "從上往下"調(diào)整
     * @param pos:下沉節(jié)點下標(biāo)
     * @param n：堆有效大小
     */
    private void downAdjust(int pos,int n){
        int maxPos = pos;
        while (true){
            if(pos * 2 <= n && arr[pos * 2] > arr[pos]){
                maxPos = pos * 2;
            }
            if(pos * 2 + 1 <= n && arr[pos * 2 + 1] > arr[maxPos]){
                maxPos = pos * 2 + 1;
            }

            if(maxPos == pos){
                break;
            }
            swap(pos,maxPos);
            pos = maxPos;
        }
    }

2.排序
經(jīng)過建堆這個步驟后，數(shù)組就是一個標(biāo)準(zhǔn)的大頂堆了。數(shù)組中第一個元素是堆頂，也是數(shù)組中最大的元素。我們把它和最后一個元素交換，那么最大元素就放到下標(biāo)為count的位置了。

這個過程類似于“刪除堆頂元素”，當(dāng)堆頂元素刪除之后，我們把最后一個元素放到堆頂，然后通過“從上往下”方式堆化，將剩下count - 1個元素重新構(gòu)建成堆。堆化完成后，再取堆頂元素放到下標(biāo)是 count - 1位置，一直重復(fù)這個過程，直到堆中只剩下下標(biāo)為1的一個元素，完成排序。

將上面的排序過程，翻譯成排序代碼。

    /**
     * 堆排序
     */
    public void sort(){
        int n = count;
        for (int i = count; i > 1 ; i--){
            swap(1,i);
            downAdjust(1,--n);
        }
    }

時間復(fù)雜度分析

在整個堆排序的過程中，需要極少的臨時存儲空間。堆排序包括建堆和排序兩個操作，構(gòu)建堆過程的時間復(fù)雜度是O(n)，排序過程的時間復(fù)雜度是O(n log n)，所以堆排序整體的時間復(fù)雜度是O(n log n)。

GitHub 代碼地址： 二叉堆