Skew binomial heap
Skew binomial heap | |||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Type | heap | ||||||||||||||||||||||||||
Invented | 1996 | ||||||||||||||||||||||||||
Invented by | Gerth Stølting Brodal and Chris Okasaki | ||||||||||||||||||||||||||
|
In computer science, a skew binomial heap (or skew binomial queue) is a data structure for priority queue operations. It is a variant of the binomial heap that supports constant-time insertion operations in the worst case, rather than amortized time.
Motivation
[edit]Just as binomial heaps are based on the binary number system, skew binary heaps are based on the skew binary number system.[1] Ordinary binomial heaps suffer from worst case logarithmic complexity for insertion, because a carry operation may cascade, analagous to binary addition. Skew binomial heaps are based on the skew binary number system, where the th digit (zero-indexed) represents , instead of . Digits are either 0 or 1, except the lowest non-zero digit, which may be 2. An advantage of this system is that at most one carry operation is needed. For example, 60 is represented as 11200 in skew binary (31 + 15 + 7 + 7), and adding 1 produces 12000 (31 + 15 + 15). Since the next higher digit is guaranteed not to be 2, a carry is performed at most once. This analogy is applied to the insertion operation by introducing ternary (skew) links, which link 3 trees together. This allows the insertion operation to execute in constant time.
Structure
[edit]![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Skew_binomial_heap.svg/440px-Skew_binomial_heap.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/80/Skew_binomial_heap_links.svg/440px-Skew_binomial_heap_links.svg.png)
A skew binomial heap is a forest of skew binomial trees, which are defined inductively:
- A skew binomial tree of rank 0 is a singleton node.
- A skew binomial tree of rank can be constructed in three ways:
- a simple link links two rank trees, making one the leftmost child of the other;
- a type A skew link links three trees. Two rank trees become the children of a rank 0 tree;
- a type B skew link links three trees. A rank 0 tree and rank tree become the leftmost children of another rank tree.
When performing any link, the tree with the smallest key always becomes the root. Additionally, we impose the invariant that there may be only one tree of each rank, except the lowest rank which may have up to two.
The following OCaml code demonstrates the linking operations:
type 'a heap = 'a tree list and 'a tree = Tree of 'a * int * 'a tree list let rank (Tree (_, r, _)) = r let simple_link (Tree (k1, r, c1) as t1) (Tree (k2, r, c2) as t2) = if k1 <= k2 then Tree (k1, r + 1, t2 :: c1) else Tree (k2, r + 1, t1 :: c2) let skew_link k1 (Tree (k2, r, c2) as t2) (Tree (k3, r, c3) as t3) = if k1 <= k2 && k1 <= k3 then (* type A *) Tree (k1, r + 1, [t2; t3]) else (* type B *) let t1 = Tree (k1, 0, []) in if k2 <= k3 then Tree (k2, r + 1, t1 :: t3 :: c2) else Tree (k3, r + 1, t1 :: t2 :: c3)
From these properties, it can be deduced that the root of a rank skew binomial tree has up to children. The number of nodes in a skew binomial tree of rank is also bounded by . Since trees of the same rank may have different numbers of nodes, there may be more than one way to distribute the ranks in the heap.
These constructions may be seen as a generalisation of binary trees and binomial trees. A skew binomial tree constructed using only simple links is an ordinary binomial tree, and using only type A skew links results in a perfectly balanced binary tree.
Operations
[edit]Find-min
[edit]Search the list of roots to find the node containing the minimum key. This takes time.
In an imperative setting, one can maintain a pointer to the root containing the minimum key, allowing access in time. This pointer must be updated after every operation, adding only a constant overhead in time complexity.
In a functional setting without random access to nodes, one can instead represent the heap as a single tree with skew binomial trees as its children. The root of this tree is the minimum of the heap, allowing access. Note that this tree will not necessarily be a skew binomial tree itself. The other operations must be modified to deal with this single tree. This concept of a global root is used in the optimizations described below, albeit slightly differently.
Merge
[edit]To merge two skew binomial heaps together, first eliminate any duplicate rank trees in each heap by performing simple links. Then, merge the heaps in the same fashion as ordinary binomial heaps, which is similar to binary addition. Trees with the same ranks are linked with a simple link, and a 'carry' tree is passed upwards if necessary. Because the rank of trees in each heap is now unique, at most three trees of the same rank are considered, which is sufficient to establish a bound.
let rec unique = function | t1 :: t2 :: ts when rank t1 = rank t2 -> unique (simple_link t1 t2 :: ts) | ts -> ts let rec merge_uniq h1 h2 = match h1, h2 with | h1, [] -> h1 | [], h2 -> h2 | t1 :: ts1, t2 :: ts2 -> if rank t1 < rank t2 then t1 :: merge_uniq ts1 h2 else if rank t1 > rank t2 then t2 :: merge_uniq h1 ts2 else unique (simple_link t1 t2 :: merge_uniq ts1 ts2) let merge h1 h2 = merge_uniq (unique h1) (unique h2)
Insert
[edit]Create a skew binomial tree of rank 0 (a singleton node), containing the key to be inserted. The smallest two trees in the heap are then considered:
- If they are both of rank , then perform a skew link with these two trees and the singleton node. The resulting tree is of rank . Since there can only have been at most one rank tree in the original heap, the invariant is preserved.
- If they are of different ranks, simply add the rank 0 tree to the front of the list of roots. Since the list of roots did not have duplicate rank trees before, the invariant is not violated, as there will be at most two rank 0 trees after.
As up to one link is performed, this operation executes in worst case time, improving on the binomial heap which relies on amortized analysis for its bound, with a worst case of .
let insert k = function | t2 :: t3 :: ts when rank t2 = rank t3 -> skew_link k t2 t3 :: ts | ts -> Tree (k, 0, []) :: ts
Delete-min
[edit]Find and discard the node containing the minimum key. This node must be the root of a tree. Divide its children into two groups, those with rank 0, and those with rank > 0. Note that there may be more than two children with rank 0, due to skew links. The children whose rank > 0 form a valid skew binomial heap, as they are already ordered, and have no duplicates. Merging these children into the heap takes time. Afterwards, reinsert each of the rank 0 children into the heap at a cost of each. The total time required is .
Decrease-key
[edit]This operation is unchanged from binomial heaps. Decreasing the key of a node may cause it to be smaller than its parent. Repeatedly exchange it with its parent until the minimum-heap property is satisfied, at a cost of time complexity. This operation requires a pointer to the node containing the key in question, and is easiest done in an imperative setting.
Optimizations
[edit]Brodal and Okasaki showed how the time complexity of the merge operation can be reduced to , by applying the 'bootstrapping' technique of Buchsbaum and Tarjan.[2]
Let the type of a primitive skew binomial heap containing elements of type be . Instead of the forest of trees representation described above, we mainintain a single tree with a global root as its minimum.
Let the type of a rooted skew binomial heap be
- ,
that is, a pair containing an element of type and a primitive heap of rooted heaps.
Finally, we define the type of a bootstrapped heap by enclosing rooted heaps in an option type:
which permits the empty heap.
The operations on this bootstrapped heap are redefined accordingly. In the following OCaml code, the prime symbol '
denotes operations for bootstrapped heaps.
type 'a bootstrapped = | Empty | Root of 'a rooted let find_min' (Root (k, h)) = k let merge' bh1 bh2 = match bh1, bh2 with | _, Empty -> bh1 | Empty, _ -> bh2 | Root (k1, h1), Root (k2, h2) -> if k1 <= k2 then Root (k1, insert bh2 h1) else Root (k2, insert bh1 h2) let insert' k h = merge' (Root(k, [])) h let delete_min' (Root (x, h)) = let Root (y, h1) = find_min h in let h2 = delete_min h in Root (y, merge h1 h2)
The new merge operation uses only insert operations on primitive heaps. Thus, it executes in time. This technique can be applied to any priority queue with constant time insertion, and logarithmic merging.
Summary of running times
[edit]Here are time complexities[3] 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[3] | Θ(1) | Θ(log n) | Θ(log n) | Θ(log n) | Θ(n) | Θ(n) |
Skew[4] | Θ(1) | O(log n) am. | O(log n) am. | O(log n) am. | O(log n) am. | Θ(n) am. |
Leftist[5] | Θ(1) | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) | Θ(n) |
Binomial[3][7] | Θ(1) | Θ(log n) | Θ(log n) | Θ(1) am. | Θ(log n)[b] | Θ(n) |
Skew binomial[8] | Θ(1) | Θ(log n) | Θ(log n) | Θ(1) | Θ(log n)[b] | Θ(n) |
2–3 heap[10] | Θ(1) | O(log n) am. | Θ(1) | Θ(1) am. | O(log n)[b] | Θ(n) |
Bottom-up skew[4] | Θ(1) | O(log n) am. | O(log n) am. | Θ(1) am. | Θ(1) am. | Θ(n) am. |
Pairing[11] | Θ(1) | O(log n) am. | o(log n) am.[c] | Θ(1) | Θ(1) | Θ(n) |
Rank-pairing[14] | Θ(1) | O(log n) am. | Θ(1) am. | Θ(1) | Θ(1) | Θ(n) |
Fibonacci[3][15] | Θ(1) | O(log n) am. | Θ(1) am. | Θ(1) | Θ(1) | Θ(n) |
Strict Fibonacci[16][d] | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(n) |
Brodal[17][d] | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(n)[18] |
- ^ make-heap is the operation of building a heap from a sequence of n unsorted elements. It can be done in Θ(n) time whenever meld runs in O(log n) time (where both complexities can be amortized).[4][5] Another algorithm achieves Θ(n) for binary heaps.[6]
- ^ a b c 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.[9] 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.[8]
- ^ Lower bound of [12] upper bound of [13]
- ^ a b 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.
References
[edit]- ^ Brodal, Gerth Stølting; Okasaki, Chris (November 1996), "Optimal purely functional priority queues", Journal of Functional Programming, 6 (6): 839–857, doi:10.1017/s095679680000201x
- ^ Buchsbaum, A.L.; Tarjan, R.E. (May 1995). "Confluently Persistent Deques via Data-Structural Bootstrapping". Journal of Algorithms. 18 (3): 513–547. doi:10.1006/jagm.1995.1020. ISSN 0196-6774.
- ^ a b c d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
- ^ a b c Sleator, Daniel Dominic; Tarjan, Robert Endre (February 1986). "Self-Adjusting Heaps". SIAM Journal on Computing. 15 (1): 52–69. CiteSeerX 10.1.1.93.6678. doi:10.1137/0215004. ISSN 0097-5397.
- ^ a b Tarjan, Robert (1983). "3.3. Leftist heaps". Data Structures and Network Algorithms. pp. 38–42. doi:10.1137/1.9781611970265. ISBN 978-0-89871-187-5.
- ^ Hayward, Ryan; McDiarmid, Colin (1991). "Average Case Analysis of Heap Building by Repeated Insertion" (PDF). J. Algorithms. 12: 126–153. CiteSeerX 10.1.1.353.7888. doi:10.1016/0196-6774(91)90027-v. Archived from the original (PDF) on 2016-02-05. Retrieved 2016-01-28.
- ^ "Binomial Heap | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-09-30.
- ^ a b Brodal, Gerth Stølting; Okasaki, Chris (November 1996), "Optimal purely functional priority queues", Journal of Functional Programming, 6 (6): 839–857, doi:10.1017/s095679680000201x
- ^ Okasaki, Chris (1998). "10.2. Structural Abstraction". Purely Functional Data Structures (1st ed.). pp. 158–162. ISBN 9780521631242.
- ^ Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12
- ^ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77, arXiv:1110.4428, CiteSeerX 10.1.1.748.7812, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2
- ^ Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery. 46 (4): 473–501. doi:10.1145/320211.320214.
- ^ Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX 10.1.1.549.471. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.
- ^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
- ^ Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. CiteSeerX 10.1.1.309.8927. doi:10.1145/28869.28874.
- ^ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. CiteSeerX 10.1.1.233.1740. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.
- ^ Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
- ^ Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN 0-471-46983-1.