Introduction to Heaps
A heap is a tree where each node has a key value, and the key value of each node is greater than or equal to / less than or equal to that of its parent.
A heap where each node's key value is greater than or equal to its parent's key value is called a min-heap; otherwise, it is called a max-heap. The priority_queue in the STL is essentially a max-heap.
The main operations supported by a (min-)heap are: inserting a number, querying the minimum value, deleting the minimum value, merging two heaps, and decreasing the value of an element.
Some powerful heaps (mergeable heaps) can also (efficiently) support operations like merge.
Some even more powerful heaps support persistence, meaning they can query or operate on any historical version, producing new versions.
Classification of Heaps
| Operation Data Structure1 | Pairing Heap | Binary Heap | Leftist Tree | Binomial Heap | Fibonacci Heap |
|---|---|---|---|---|---|
| Insert (insert) | \(O(1)\) | \(O(\log n)\) | \(O(\log n)\) | \(O(\log n)\)2 | \(O(1)\) |
| Find Minimum (find-min) | \(O(1)\) | \(O(1)\) | \(O(1)\) | \(O(1)\)34 | \(O(1)\) |
| Delete Minimum (delete-min) | \(O(\log n)\)4 | \(O(\log n)\) | \(O(\log n)\) | \(O(\log n)\) | \(O(\log n)\)4 |
| Merge (merge) | \(O(1)\) | \(O(n)\) | \(O(\log n)\) | \(O(\log n)\) | \(O(1)\) |
| Decrease Key (decrease-key) | \(o(\log n)\) (lower bound \(\Omega(\log \log n)\), upper bound \(O(2^{2\sqrt{\log \log n}})\))4 | \(O(\log n)\) | \(O(\log n)\) | \(O(\log n)\) | \(O(1)\)4 |
| Supports Persistence | \(\times\) | \(\checkmark\) | \(\checkmark\) | \(\checkmark\) | \(\times\) |
By convention, when referring to a "heap" without qualification, it usually means a binary heap.
-
The complexity for a single insertion is \(O(\log n)\), but when there are \(k\) consecutive insertions, a binomial heap containing only the elements to be inserted can be created and then merged with the original binomial heap, resulting in an amortized complexity of \(O(1)\). ↩
-
A pointer to the minimum element can be maintained and updated during other operations, allowing queries in \(O(1)\) time. ↩
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用