#95 Priority Queue 是不是 Queue ?

 在日常生活的情況中，排隊是一件很常見的事．原因是提供資源的人少，而使用資源的人多．例如，一堆人到便利商站買東西，買完後要結帳，而櫃檯人員只有一個，所以結帳得一個一個來，因此買商品的人就得排隊．在此時，如果出現一個文化水準低落的人來插隊，想必你一定會很生氣去跟對方說．在便利商店的排隊結帳來說，插隊通常不是件好事，但日常生活裡，某些特殊情況下，插隊是需要的，比如在醫院的急診室，或是馬路上遇到救護車救火車之類的，這種特殊情況，不緊急的必須先讓給緊急的．

當我們撰寫程式碼時，一般情況下我們會使用 Queue 資料結構來達成 "排隊" 的目的，然後，因應需求，如同急診室或救護車的例子，我們必須提供一個方法讓 "插隊" 可以成真．試著想一下，如果我們要用 Queue 結構的概念來達成插隊這件事，該怎麼做呢 ? 

假設我們用 Linked list 來實現 Queue 結構,

 

source: https://en.wikipedia.org/wiki/Linked_list

上面的 List 一共有三個元素，當實做 Enqueue() 時，我們可以把最新的元素加到最後面，這個動作的時間複雜度是 O(n)，n 是元素數量，當實做 Dequeue() 時，我們把前最面的元素讀取出來，然後第二個元素將變成第一個元素，時間複雜度是 O(1)．當我們要實做 "插隊" 時，我們該怎麼插隊呢 ? 首先，我們需要了解如何定義優先順序．以 List 而言，它的 index 位置就是優先順序 (Priority)，因為排在越前面會越先被 dequeue．假設我希望有一個元素能插隊在第二個位置，這表示我們得走到第二個元素，然後做插入的動作．這樣子有一個小缺點，我們必須知道每個元素的優先順序才能正確給出位置．如果我們必須先知道優先順序，這表示我們需要了解每一個元素的內容，這樣才能幫助你決定正確插入的位置是什麼．這顯然有點缺點，因為我們還得寫更多的程式碼來記錄每一個元素的意義，然後來決定該元素是重要還是不重要．

另外一個方法，我們可以將元素的內容改成兩個東西，一個是元素值和另一個是優先順序值．

上面的數字代表優先順序值，下面的數字是原來的元素值．當我們需要 Enqueue() 時，優先順序值就必須先指定．執行時間一久之後，你就會發現這方法也是有問題，因為若我們要將新元素指定到最後面，優先順序值就必須不斷新增，總有一天，這個數字將會超過 integer 的範圍．因此，用這個方法並不好，原因就在於我們必須指定優先順序值．如果我們不要指定優先順序值，同時有這樣的效果，那豈不是更好嗎 ? 此時，你就該了解到用  Queue 結構來實做並不是個好方法．

在資料結構的世界裡，有那一個結構能做到 Queue 的行為並且能定義優先順序的能力呢 ? 有的，它的名字叫 Heap，其範例如下圖所示:

source: https://en.wikipedia.org/wiki/Heap_(data_structure)

Heap 是一種特別的 Tree結構，它有一個很重要的特性，任何一個節點的值都必須大於等於或小於等於該節點以下所有的節點值．以上圖為例，這是一個大於等於的例子，意思就是每一個節點值都會比在它之下所有的節點值還要大或一樣．我們稱它為 max heap，若是小於等於，稱為 min heap．

節點值就是優先順序，只要我們能將需求面的優先順序定義清楚，就能把每一個工作 (節點) 建立 (Enqueue)  max heap，而建立的時間複雜度是 O(lg n)，其中 n 是所有節點的數量，這樣效能就比前面說的 Linked list 要來的好．取資料時 (Dequeue)，就直接將 root 取出，因為當下 root 是最大值的節點，然後再從 root 的子節點中挑出一個較大的節點做為新的 root 即可，以上圖例子而言將是 36，取出的時間複雜度是 O(1)．

使用 max/min heap 來做為具有優先順序功能的 Queue，就稱它為 Priority queue．在主要的程式語言裡 C++/Java 等的 library 都有實作 priority queue，所以讓大家可以直接用，方便許多．所以，當你需要一個有插隊功能的 queue 時，別忘了 priority queue．