目前這個系列的文章都挑着非常經典的，讓人眼前一亮的算法，今天的堆排序算法就是其中一個。 首先理解什麼是堆，這裡面堆（Heap）並不是程序中內存區域，而是一種完全二叉樹表示的數據結構。 堆具有以下特點

• 是一個完全二叉樹
• 堆的每個節點的值必須大於等於左右樹節點（大頂堆），或小於等於左右樹節點（小頂堆）。

簡單說明下，完全二叉樹是除了最後一層葉子節點外，其他的節點都有兩個子樹，而葉子節點可以沒有子樹，或者只有左子樹。 如下圖就是個大頂堆：

小頂堆

堆存儲

堆因為是完全二叉樹，非常適合用數組存儲，上圖為大頂堆的存儲情況，其中a[0]不用， a[1]為大頂堆的頂點，也就是最大的數據，a[12]= 7 為左子樹頂點，a[12+1]= 6為右子樹的頂點，其他節點情況依次類推。

堆的兩種操作

向堆插入元素

用圖來表示如下：

向堆插入元素，先插入到最後一個數組元素位置，然後和自己的父節點6比較，由於比6大不滿足大頂堆的條件，所以9和6交換，然後9再和堆頂元素8比較，又不滿足大頂堆條件，繼續交換，最後形成一個大頂堆，這個步驟叫堆化。

刪除堆頂元素

對於大頂堆來說，堆頂的元素為最大值，依次刪除堆頂元素並輸出，那麼就是將數字從大向小排列了。

這裡面又個技巧，就是刪除堆頂元素的時候，不能直接刪除，要用堆頂元素和最後一個元素做交換，然後根據堆的特點調整堆，直到滿足條件。

完整代碼如下：

package com.dianneng.lms;

public class TestHeap {
    private int [] a;
    private int n;
    private int count;

    public TestHeap(int cap) {
        a = new int[cap+1];
        n = cap;
        count = 0;
    }

    public void swap(int i,int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
        return;
    }

    public void print(){
        for (int i = 0; i <= count;i++) {
            System.out.print(a[i]+"t");
        }
    }

    public int insert( int v) {
        if (count == n) {
            System.out.println("Heap is full!");
            return -1;
        }else {
            a[++count] = v;
            int i = count;
            while (i/2 >0 && a[i] > a[i/2]) {
                swap(i,i/2);
                i = i/2;
            }
        }
        return 0;
    }

    public int  removeMax() {
        if (count == 0)  {
            return -1;
        }
        System.out.print(a[1]+"t");
        a[1] = a[count];
        --count;
        heapify(count,1);
        return 0;
    }

    private void heapify(int n, int i) {
        while(true) {
            int maxPos = i;
            //通過左右子樹頂點比較獲得最大數節點
            if (i*2 <= n && a[i] <a[i*2] ){
                maxPos = i*2;
            }
            if (i*2+1 <= n && a[maxPos] < a[i*2+1]) {
                maxPos = i*2+1;
            }
            //已經是最大的不用交換了
            if  (maxPos == i) {
                break;
            }
            //需要交換
            swap(i,maxPos);
            //i指向待交換的
            i = maxPos;
        }
    }

    public  static void main(String [] args) {
        TestHeap th = new TestHeap(18);
        th.insert(8);
        th.insert(7);
        th.insert(6);
        th.insert(5);
        th.insert(4);
        th.insert(3);
        th.print();
        System.out.println();
        while(th.removeMax() == 0) {

        }
    }
}

可以利用大頂堆的特性，對要排序的數組進行先堆化排序，然後依次交換堆頂元素和最後一個元素，交換後堆化，將堆的大小減一，最終這樣輸出的就是從小到大排序的數組。 借用老師的一個圖表示：