數據結構之優先級隊列、堆及堆排序

優先級隊列是一個抽象數據類型，它提供刪除插入、最大(最小)關鍵字值數據項的方法，其主要目的是對極值提供便利的訪問。
優先級隊列可以用有序數組來實現，也可以用隊列來實現。

堆，是一種樹，由其實現優先級隊列的插入刪除操作的時間復雜度都是O(logN)。
堆是有如下特點的二叉樹：
1.是完全二叉樹。即，除了樹的最後一層節點不是滿的，其他的每一層都必須是滿的。
2.堆中的每一個節點都滿足堆的條件，即每一個節點的關鍵字的值都大於或等於其子節點的關鍵字的值，而小於父節點關鍵字的值。
3.最大數據項總是在根位置上。
4.一般用數組實現。
5.堆不能有序地遍歷所有數據，不能找到特定關鍵字數據項的位置，也不能移除特定關鍵字的數據項。
6.要插入的數據項總是先放在數組中的第一個空的位置上，然後再向上篩選它至適當的位置。
7.當從根移除一個數據項時，用數組中的最後一個數據項代替他的位置，然後再向下篩選這個節點到適當的位置。
8.可以更改任意數據項的優先級。首先，更改其關鍵字，如果增加，則向上篩選，減少，則向下篩選。

堆排序，是一種高效的排序過程，其時間復雜度為O(N*logN).將一個待排序數組依次寫入到堆中，寫入完畢之後，依次去除根元素(最大元素)寫入到數組中，即完成了排序。可以使用同一個數組來存放初始無序的數據、正在排序的數據以及排好序的數據，因此，堆排序不需要額外的空間。(N次插入,N次移除)。
也可以對無序數組的N/2個數據項進行trickDown()操作，而不作N次插入，可使堆排序運行速度更快。

下面是用數組實現的堆以及堆排序：

package test;
public class Heap {
    Node2[] heapArray;
    int arraySize;// 數組大小
    int currentSize;// 數組中實有數據的大小
    public Heap(int size) {
        arraySize = size;
        currentSize = 0;
        heapArray = new Node2[arraySize];
    }
    public boolean isEmpty() {
        return currentSize == 0;
    }
    // 插入
    public boolean insert(int key) {
        if (currentSize == arraySize)
            return false;
        Node2 node = new Node2(key);// 創建新節點
        heapArray[currentSize] = node;// 將新節點放在數組末尾
        trickUp(currentSize++);// 將其向上篩選，同時計數加1
        return true;
    }
    /**
     * 節點初始時插入到數組中的空的位置，即最後的位置， 但是如果新插入的節點大於它得到的父節點時，會把堆破壞，
     * 因此，需要向上篩選新節點，直到它在一個大於它的父節點之下，在一個小於它的子節點之上。
     */
    public void trickUp(int index) {
        int parent = (index - 1) / 2;// 父節點的下標
        Node2 bottom = heapArray[index];
        while (index > 0 && heapArray[parent].idata < bottom.idata) {
            heapArray[index] = heapArray[parent];// 向下移動父節點
            index = parent;// 將index上移
            parent = (parent - 1) / 2;// 父節點的下標給予其父節點
        }
        heapArray[index] = bottom;
    }
    // 刪除根節點
    public Node2 remove() {
        Node2 root = heapArray[0];
        heapArray[0] = heapArray[--currentSize];
        trickDown(0);// 向下篩選
        return root;
    }
    /**
     * 將根節點刪除之後，需要找到一個適合的節點來替換之
     */
    public void trickDown(int index) {
        int largerChild;
        Node2 top = heapArray[index];
        while (index < currentSize / 2) {
            int leftChild = index * 2 + 1;
            int rightChild = leftChild + 1;
            if (rightChild < currentSize
                    && heapArray[leftChild].idata < heapArray[rightChild].idata)
                largerChild = rightChild;
            else
                largerChild = leftChild;
            if (top.idata >= heapArray[largerChild].idata)
                break;
            heapArray[index] = heapArray[largerChild];
            index = largerChild;
        }
        heapArray[index] = top;
    }
    public void show() {
        for (int i = 0; i < currentSize; i++) {
            if (heapArray[i] != null)
                System.out.println(heapArray[i].idata + " ");
            else
                System.out.println("* ");
        }
    }
    public static void main(String[] args) {
        Heap heap = new Heap(6);
        heap.insert(12);
        heap.insert(23);
        heap.insert(4);
        heap.insert(2);
        heap.insert(8);
        heap.show();
        Node2 node = heap.remove();
        System.out.println("the remove node = " + node.idata);
        heap.show();
        // 堆排序
        Item[] item = { new Item(3), new Item(1), new Item(5), new Item(2),
                new Item(7) };
        for (int i = 0; i < item.length; i++)
            heap.insert(item[i].idata);
        for (int i = 0; i < item.length; i++) {
            n = heap.remove();
            item[i].idata = n.idata;
        }
        //打印數組
        for (int i = 0; i < item.length; i++)
            System.out.print(item[i].idata + " . ");
    }
}
class Node2 {
    int idata;
    public Node2(int idata) {
        this.idata = idata;
    }
}