堆
-
一個完全二叉樹
-
堆中每個節點的值都必須大于等于（或小于等于）其子樹中每個節點的值
-
插入O(logn)
- 將新的元素放到堆的最后
- 堆化O(logn)：順著節點所在路徑，向上逐個對比，然后交換
-
洗掉堆頂元素O(logn)
-
洗掉堆頂元素
-
將最后一個節點放到堆頂
-
從上到下堆化（左子樹優先）
-
堆排序
-
原地
-
不穩定
-
O(nlogn)
-
步驟
-
建堆O(nlogn)[實際是O(n)]
-
將陣列下標為1的元素看作初始的堆，然后將剩余元素從下往上逐個對比，加入堆中
-
完全二叉樹的n/2+1到n個節點是葉子節點（根節點下標設為1，方便實作），所以將從n到1的節點逐個從上往下堆化
-
-
排序O(nlogn)：不斷洗掉堆頂元素并堆化，直到堆空
-
優先佇列
優先佇列的概念和堆的特性十分契合，往優先佇列中插入一個元素就相當于往堆中插入一個元素；從優先佇列中取出優先級最高的元素，就相當于取出堆頂元素
-
合并小檔案：假設有100個有序的小檔案，希望將它們合并成一個有序的大檔案，就可以使用大小為100的優先佇列，從100個檔案中取首字符放入優先佇列，每次將堆頂元素放入大檔案并再從對應小檔案中取出一個字符
-
高性能定時器：假設我們有一個定時器，定時器中維護了很多定時任務，每個任務都設定了一個要觸發執行的時間點，定時器每過一個很小的單位時間（比如 1 秒），就掃描一遍任務，看是否有任務到達設定的執行時間，如果到達了，就拿出來執行，使用優先佇列得出最先要執行的任務P，將定時器時間設為P執行時間，就不必輪詢了
-
求TOP K
-
靜態資料：從堆頂洗掉K個元素
-
動態資料：維護一個一個大小為K的小頂堆，每當有資料要插入時先于堆頂元素比較，若大于堆頂元素則洗掉堆頂元素并且將這個資料插入堆中；如果小于堆頂元素小則不做處理，這樣無論任何時候需要查詢當前K大元素，都能立即回傳
-
-
求動態資料集合中的n%分位數（以求50%分位數，即中位數為例）
-
維護一個大頂堆存盤前半部分資料，一個小頂堆存盤后半部分資料
-
偶數情況n/2個存大頂堆，n/2存小頂堆；奇數情況n/2+1個存大頂堆，n/2個存小頂堆
-
如果新加入資料小于等于大頂堆堆頂元素，那么將其加入大頂堆，否則加入小頂堆
-
資料加入后可能出現兩邊資料與約定數量不符的情況，這時可以將資料互相移動，將數量滿足約定
-
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/24748.html
標籤：其他
上一篇：YOLO在ARM的速度優化方案