User:IntGrah/Rank-pairing heap
Data structure for priority queue operations
From Wikipedia, the free encyclopedia
In computer science, a rank-pairing heap is a data structure for priority queue operations. Rank-pairing heaps were designed to match the amortized running times of Fibonacci heaps whilst maintaining the simplicity of pairing heaps. Rank-pairing heaps were invented in 2011 by Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan.[1]
| Rank-pairing heap | |||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | heap | ||||||||||||||||||||||||||||||||||||
| Invented | 2011 | ||||||||||||||||||||||||||||||||||||
| Invented by | Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan | ||||||||||||||||||||||||||||||||||||
| Complexities in big O notation | |||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||
Structure
A rank-pairing heap is a list of heap-ordered trees represented in the left-child right-sibling binary tree format. This means that each node has one pointer to its left-most child, and another pointer to its right sibling. Additionally, each node maintains a pointer to its parent.
Operations
Merge
Insert
Find-min
We maintain a pointer to the node containing the minimum key. This will always be a root within the list of trees. The minimum key can thus be found at a constant cost, with only a minor overhead in the other operations.
Delete-min
Decrease-key
To decrease the key of a node , reduce its key, and update the minimum key pointer, if it is the new minimum. Then, the subtree rooted at is detached; in the left-child right-sibling representation, this is equivalent to replacing with its right child . The detached subtree is added to the list of trees, and the ranks are recalculated: the rank of is set to be one greater than its left child, and the ancestors of have their ranks reduced.
Summary of running times
Here are time complexities[2] of various heap data structures. The abbreviation am. indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names of operations assume a min-heap.
| Operation | find-min | delete-min | decrease-key | insert | meld | make-heap[a] |
|---|---|---|---|---|---|---|
| Binary[2] | Θ(1) | Θ(log n) | Θ(log n) | Θ(log n) | Θ(n) | Θ(n) |
| Skew[3] | Θ(1) | O(log n) am. | O(log n) am. | O(log n) am. | O(log n) am. | Θ(n) am. |
| Leftist[4] | Θ(1) | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) | Θ(n) |
| Binomial[2][6] | Θ(1) | Θ(log n) | Θ(log n) | Θ(1) am. | Θ(log n)[b] | Θ(n) |
| Skew binomial[7] | Θ(1) | Θ(log n) | Θ(log n) | Θ(1) | Θ(log n)[b] | Θ(n) |
| 2–3 heap[9] | Θ(1) | O(log n) am. | Θ(1) | Θ(1) am. | O(log n)[b] | Θ(n) |
| Bottom-up skew[3] | Θ(1) | O(log n) am. | O(log n) am. | Θ(1) am. | Θ(1) am. | Θ(n) am. |
| Pairing[10] | Θ(1) | O(log n) am. | o(log n) am.[c] | Θ(1) | Θ(1) | Θ(n) |
| Rank-pairing[13] | Θ(1) | O(log n) am. | Θ(1) am. | Θ(1) | Θ(1) | Θ(n) |
| Fibonacci[2][14] | Θ(1) | O(log n) am. | Θ(1) am. | Θ(1) | Θ(1) | Θ(n) |
| Strict Fibonacci[15][d] | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(n) |
| Brodal[16][d] | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(n)[17] |
- For persistent heaps (not supporting decrease-key), a generic transformation reduces the cost of meld to that of insert, while the new cost of delete-min is the sum of the old costs of delete-min and meld.[8] Here, it makes meld run in Θ(1) time (amortized, if the cost of insert is) while delete-min still runs in O(log n). Applied to skew binomial heaps, it yields Brodal-Okasaki queues, persistent heaps with optimal worst-case complexities.[7]
- Brodal queues and strict Fibonacci heaps achieve optimal worst-case complexities for heaps. They were first described as imperative data structures. The Brodal-Okasaki queue is a persistent data structure achieving the same optimum, except that decrease-key is not supported.
