在數據結構中，普通的隊列是先進先出，但有時我們可能並不想有這麽固定的規矩，我們希望能有壹個帶優先級的隊列。考慮在現實生活中，壹些服務排隊窗口會寫著“軍人依法優先”；送進醫院的患者，即便是按順序到達的，生病更加嚴重的往往優先級也會更高；還有操作系統中的作業調度也和優先級有關......
於是我們能不能改進隊列？使得隊列是有壹定優先級的，這樣能讓壹些事物和任務的處理變的更加靈活。當然是可以的，最基本的我們可以基於線性結構來實現，考慮基於線性結構的時間復雜度：
1、隊列是壹種FIFO（First-In-First-Out）先進先出的數據結構，對應於生活中的排隊的場景，排在前面的人總是先通過，依次進行。
2、優先隊列是特殊的隊列，從“優先”壹詞，可看出有“插隊現象”。比如在火車站排隊進站時，就會有些比較急的人來插隊，他們就在前面先通過驗票。優先隊列至少含有兩種操作的數據結構：insert（插入），即將元素插入到優先隊列中（入隊）；以及deleteMin（刪除最小者），它的作用是找出、刪除優先隊列中的最小的元素（出隊）。
結構\操作 入隊 出隊
普通線性結構 O(1) O(n)
順序線性結構 O(n) O(1)
普通線性結構實現的優先隊列出隊時間復雜度是O(n)，因為出隊要拿出最優先的元素，也就是相對最大的元素（註意：大小是相對的，我們可以指定比較規則），從而要掃描壹遍整個數組選出最大的取出才行。而對於順序線性結構的入隊操作，入隊後可能破壞了原來的有序性，從而要調整當前順序。
可以看到使用線性結構總有時間復雜度是O(n)的操作，還有沒有更好的實現方式呢，當然是有的，這就要來聊壹聊堆Heap。
堆嚴格意義上來說又叫二叉堆（Binary Heap），因為它的結構是壹顆完全二叉樹，堆壹般分為最大堆和最小堆。
堆性質：
結構性：堆是壹顆除底層外被完全填滿的二叉樹，底層的節點從左到右填入，這樣的樹叫做完全二叉樹。即缺失結點的部分壹定再樹的右下側。
堆序性：由於我們想很快找出最小元，則最小元應該在根上，任意節點都小於它的後裔，這就是小頂堆（Min-Heap）；如果是查找最大元，則最大元應該在根上，任意節點都要大於它的後裔，這就是大頂堆(Max-heap)。
最大堆：父親節點的值大於孩子節點的值
最小堆：父親節點的值小於孩子節點的值
由於是完全二叉樹，節點的索引之間有著壹定的關系，故我們可以使用數組來存儲二叉堆，具體如下：
如果從索引為0開始存儲，則父親和孩子節點的索引關系如下：
當我們需要向壹個最大堆添加壹條新的數據時，此時我們的堆變成了這樣。
此時，由於新數據的加入已經不符合最大堆的定義了。所以我們需要對新加入的數據進行shift up操作，將它放到它應該在的位置。shift up操作時我們將新加入的數據與它的父節點進行比較。如果比它的父節點大，則交換二者。
此時我們就完成了 對新加入元素的shift up操作。
當我們從堆中(也就是優先隊列中)取出壹個元素時。我們是將堆頂的元素彈出。(只能從堆頂取出)
此時這個堆沒有頂了，那麽該怎麽辦呢？我們只需要把這個堆最後壹個元素放到堆頂就可以了。
此時我們就完成了彈出壹個元素之後的shift down操作。
replace:去除最大元素後，放入壹個新元素
實現：可以先extractMax,再add，兩次longn操作。
實現:將堆頂的元素替換以後sift down，壹次O(logn)操作
將n個元素逐個插入到壹個空堆中,算法復雜度是O(nlogn),heapify的過程，算法的復雜度為O(n).
heapify:將任意數組整理成堆的形狀。
首先將壹個數組抽象成壹個堆。這個過程，我們稱之為heapify。
之後我們找到這個堆中第壹個非葉子節點，這個節點的位置始終是數組的數量除以2，也就是索引5位置的27，從這個節點開始，對每壹個非葉子的節點,，進行shift down操作。
27比它的子節點51要小，所以交換二者。
接下來我們看索引2位置的20。首先呢，我們需要將20與它兩個子節點中較大的51交換。
每個節點堆化的時間復雜度是O(logn)，那 個節點的堆化的總時間復雜度是O(nlogn)。
推導過程
堆化節點從倒數第二層開始。堆化過程中，需要比較和交換的節點個數與這個節點的高度k成正比。
所以 heapify() 時間復雜度是 O(n).
建堆後，數組中的數據是大頂堆。把堆頂元素，即最大元素，跟最後壹個元素交換，那最大元素就放到了下標為n的位置。
這個過程有點類似上面的“刪除堆頂元素”的操作，當堆頂元素移除之後，把下標n的元素放堆頂，然後再通過堆化的方法，將剩下的n-1個元素重新構建成堆。壹直重復這個過程，直到最後堆中只剩下下標為1的元素，排序就完成了。
topk和selectk問題既可以使用快排思想解決，也可以使用優先隊列解決。
快排:O(n) 空間O(1)
優先隊列:O(nlogk) 空間O(k)
優先隊列的有i是，不需要壹次性知道所有數據,數據流的方式處理。