Transcript 5.5 - 5.6

CS 6310 Advanced Data
Structures/Algorithms
5.5 Skew Heaps
5.6Binomial Heaps
Yifu Rong
Skew Heaps
The skew heaps were introduced by Sleator
and Tarjan (1986) as an analog of the leftist
heaps, but without balancing information.
Leftist Heaps
Skew Heaps
• Without balancing information, one cannot
decide whether the rank on the left or on the
right is larger, so whether to exchange left and
right subtree to restore the leftist heap property.
In skew heaps, the strategy is just to exchange
always.
Skew Heaps
• Theorem:The skew heap structure supports the
operations find min in O(1) time and insert, merge, and
delete min in amortized O(log n) time on a heap with n
elements.
Binomial Heaps
• Binomial heaps can again be written as binary trees with keys and
objects in each node, but they are not heap-ordered trees, but only
half-ordered trees:
1. If node w is in the right subtree of node v, then v-> key < w -> key.
Keys get larger to the right, but on a left path keys might appear in any
order.
2. If v is a node on the path from the root to the left, then v -> right is
root of a complete binary tree. The height of these trees is strictly
decresing along the path from the root to the left.
• Binomail heaps is the collection of ordered binary trees.
• The complete binary tree of height h contains 2^(h+1) −1 nodes, so
together with the node on the leftmost path the block has 2^(h+1)
nodes.
• A binomial tree of order 0 is a single node
• A binomial tree of order k has a root node whose children are roots
of binomial trees of orders k−1, k−2, ..., 2, 1, 0
2
Two blocks of the same size 2^h into one block of size
2^(h+1)
Properties of binomial heap
• Each binomial tree in a heap obeys the minimum-heap property: the
key of a node is greater than or equal to the key of its parent.
• There can only be either one or zero binomial trees for each order,
including zero order.
• Example {12,77,12,23,23,24,33,53,5,21,17,99,9}
• 13 = (1101)
• Theorem: The binomial heap structure supports the operations
insert, merge, find min, and delete min in O(log n) time
Thanks