堆的應用-優先級隊列(隊列的實作)

堆得概念：

1. 堆邏輯上是一棵完全二叉樹
2. 堆實體上是儲存在數組中
3. 滿足任意結點的值都大于其子樹中結點的值，叫做大堆，或者大根堆，或者最大堆
4. 反之，則是小堆，或者小根堆，或者最小堆
5. 堆的基本作用是，快速找集合中的最值

   

   優先級隊列概念：

   在很多應用中，我們通常需要按照優先級情況對待處理對象進行處理，比如首先處理優先級最高的對象，然後處理次高的對象。最簡單的一個例子就是，在手機上玩遊戲的時候，如果有來電，那麼系統應該優先處理打進來的電話。

   在這種情況下，我們的資料結構應該提供兩個最基本的操作，一個是傳回最高優先級對象，一個是添加新的對象。

   這種資料結構就是優先級隊列(Priority Queue)。

   下面是關于隊列的一些操作。

public class MyPriorityQueue {
    private int[] array = new int[100]; // 暫時不考慮擴容
    private int size = 0;   // [0, size) 表示有效元素區間.

    public void offer(int x) {
        // 1. 先把 x 放到數組元素的末尾.
        array[size] = x;
        size++;
        // 2. 把 x 進行向上調整即可
        // 第一個參數表示用來承載堆的數組
        // 第二個參數表示數組中有效元素的個數.
        // 第三個參數表示從哪個位置進行向上調整.
        shiftUp(array, size, size - 1);
    }

    private void shiftUp(int[] array, int size, int index) {
        int child = index;
        int parent = (child - 1) / 2;
        // 如果 child 為 0, 說明 child 已經是根節點了. 根節點就沒有父節點.
        // 調整到這裡已經就到頂了.
        while (child > 0) {
            // 比較目前 child 和 parent 之間的大小關系, 看看是否符合大堆.
            if (array[parent] < array[child]) {
                // 交換父子元素的内容
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;
            } else {
                break;
            }
            child = parent;
            parent = (child - 1) / 2;
        }
    }

    public Integer poll() {
        if (size <= 0) {
            return null;
        }
        int ret = array[0];

        // 如何删除隊首元素(根節點) 呢?
        // 把未知問題轉換成已知問題.
        // 1. 把最後一個元素的值填入到 0 号元素上.
        array[0] = array[size - 1];
        // 2. 删除最後一個元素
        size--;
        // 3. 從 0 下标開始進行向下調整
        shiftDown(array, size, 0);
        return ret;
    }

    private void shiftDown(int[] array, int size, int index) {
        int parent = index;
        int child = 2 * parent + 1;
        while (child < size) {
            if (child + 1 < size && array[child + 1] > array[child]) {
                child = child + 1;
            }
            if (array[child] > array[parent]) {
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
            } else {
                break;
            }
            parent = child;
            child = 2 * parent + 1;
        }
    }

    public Integer peek() {
        if (size == 0) {
            return null;
        }
        return array[0];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public static void main(String[] args) {

        MyPriorityQueue queue = new MyPriorityQueue();
        queue.offer(9);
        queue.offer(5);
        queue.offer(2);
        queue.offer(7);
        queue.offer(3);
        queue.offer(6);
        queue.offer(8);
        while (!queue.isEmpty()) {
            Integer cur = queue.poll();
            System.out.println(cur);
        }
    }
}