堆簡介
堆是一棵樹，其每個節點都有一個鍵值，且每個節點的鍵值都大於等於/小於等於其父親的鍵值。
每個節點的鍵值都大於等於其父親鍵值的堆叫做小根堆，否則叫做大根堆。STL 中的 priority_queue 其實就是一個大根堆。
（小根）堆主要支持的操作有：插入一個數、查詢最小值、刪除最小值、合併兩個堆、減小一個元素的值。
一些功能強大的堆（可並堆）還能（高效地）支持 merge 等操作。
一些功能更強大的堆還支持可持久化，也就是對任意歷史版本進行查詢或者操作，產生新的版本。
堆的分類
操作 \ 數據結構4 |
配對堆 | 二叉堆 | 左偏樹 | 二項堆 | 斐波那契堆 |
|---|---|---|---|---|---|
| 插入（insert） | \(O(1)\) | \(O(\log n)\) | \(O(\log n)\) | \(O(\log n)\)1 | \(O(1)\) |
| 查詢最小值（find-min） | \(O(1)\) | \(O(1)\) | \(O(1)\) | \(O(1)\)23 | \(O(1)\) |
| 刪除最小值（delete-min） | \(O(\log n)\)3 | \(O(\log n)\) | \(O(\log n)\) | \(O(\log n)\) | \(O(\log n)\)3 |
| 合併 (merge) | \(O(1)\) | \(O(n)\) | \(O(\log n)\) | \(O(\log n)\) | \(O(1)\) |
| 減小一個元素的值 (decrease-key) | \(o(\log n)\)（下界 \(\Omega(\log \log n)\)，上界 \(O(2^{2\sqrt{\log \log n}})\)）3 | \(O(\log n)\) | \(O(\log n)\) | \(O(\log n)\) | \(O(1)\)3 |
| 是否支持可持久化 | \(\times\) | \(\checkmark\) | \(\checkmark\) | \(\checkmark\) | \(\times\) |
習慣上，不加限定提到「堆」時往往都指二叉堆。
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：ouuan, HeRaNO
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用