Lecture Note 04 EECS 4101/5101 Instructor: Andy Mirzaian
LEFTIST HEAPS
Leftist heaps are a data structure for representing priority queues. They were discovered by Clark A. Crane [1971] (also described in Knuth, Art of Computer Programming, vol. 3, 1973, pp. 151-152) and have the following nice properties:
• INSERT and DELETEMIN operations can be performed in O(log n) time in the worst case — as with standard heaps.
• In addition, the UNION operation joins two leftist heaps with n and m nodes, respectively, into a single leftist heap in O(log (max(m, n))) time in the worst case. The two old heaps are distroyed as a result. (Other names used in the literature for UNION are meld, join, merge.)
• The rearrangement of nodes following an INSERT, DELETEMIN or UNION opera- tion involves changing pointers, not moving records. In contrast, in the array repre- sentation of standard heaps, upheap and downheap involves exchanging contents of array elements. The difference could be significant if the elements in the priority queue are sizeable objects (e.g. themselves arrays), in which case we can no longer assume that exchanging two array entries takes constant time.†
Definition 1: The distance of a node m in a tree, denoted dist[m], is the length of the shortest path from m down to a descendant node that has at most one child.
Definition 2: A leftist heap is a binary tree such that for every node m,
(a) key[m] ≤ key[lchild[m]] and key(m) ≤ key[rchild[m]], and
(b) dist[lchild[m]] ≥ dist[rchild[m]].
In the above definition, key[m] is the key stored at node m. We assume that there is a total ordering among the keys. We also assume that key[nil] = ∞ and dist[nil] = −1.
Definition 3: The right path of a tree is the path m1, m2, …, mk where m1 is the root of the tree, mi+1 = rchild[mi] for 1 ≤ i < k, and rchild[mk] = nil.
Figure 1 below shows two examples of leftist heaps.
Here are a few simple results about leftist heaps that you should be able to prove easily: Fact 1: The left and right subtrees of a leftist heap are leftist heaps.
Fact 2: The distance of a leftist heap’s root is equal to the length of the tree’s right path.
Fact 3: For any node m of a leftist heap, dist[m] = dist[rchild[m]] +1 (where, as usual, we take dist[nil]=−1).
† Note, however, that in this case we could still use the array representation for heaps, now storing in its entries pointers to the heap’s nodes rather than the (large) nodes themselves. Then upheap and downheap can be done by exchanging pointers, while leaving the nodes themselves fixed.
-2-
T
11 21
2
T
0
3
0 2
5
113
9 46
8 0004
0
0 12 0
1 15
5 13 0
00 20
0
6 0
Figure 1. In each node we record its key at the top half and its distance at the bottom half. The right path of T1 is 1, 5, 8 while the right path of T2 is 1.
In the examples above, T2 illustrates the fact that leftist heaps can be unbalanced. How- ever, in INSERT, DELETEMIN and UNION, all activity takes place along the right path which, the following theorem shows, is short.
Theorem: If the length of the right path in a leftist tree T is k then T has at least 2k+1 −1 nodes.
Proof: By induction on the height h of T .
Basis (h=0): Then T consists of a single node and its right path has length k=0. Indeed, T
has 1 ≥ 21 −1 nodes, as wanted.
Inductive Step (h>0): Suppose the theorem holds for all leftist heaps that have height < h and let T be a leftist heap of height h. Further, let k be the length of T ’s right path and n be the number of nodes in T . Consider two cases:
Case 1: k=0 (i.e. T has no right subtree). But then clearly n ≥1 = 21 −1, as wanted.
Case 2: k>0. Let TL, TR be the left and right subtrees of T; nL, nR be the number of
nodes in TL and TR; and kL, kR be the lengths of the right paths in TL and TR respec-
tively. By Fact 1, TR and TL are both leftist heaps. By Facts 2 and 3, kR = k −1, and by
definition of leftist tree kL ≥ kR. Since TL, TR have height < h we get, by induction
hypothesis, n≥2k−1 and n≥2k−1. But n=n+n+1 and thus, RLLR
n≥2k −1+2k −1+1=2k+1 −1. Therefore n≥2k+1 −1, as wanted.
From this we immediately get
Corollary: The right path of a leftist heap with n nodes has length ≤ log(n + 1) − 1.
Now let’s examine the algorithm for joining two leftist heaps. The idea is simple: if one of the two trees is empty we’re done; otherwise we want to join two non-empty trees T1 and T2 and we can assume, without loss of generality, that the key in the root of T1 is ≤ the key in the root of T2. Recursively we join T2 with the right subtree of T1 and we make the resulting leftist heap into the right subtree of T1. If this has made the distance of the right subtree’s root longer than the distance of the left subtree’s root, we simply inter- change the left and right children of T1’s root (thereby making what used to be the right
-3-
subtree of T1 into its left subtree and vice-versa). Finally, we update the distance of T1’s root. The following pseudo-code gives more details.
We assume that each node of the leftist heap is represented as a record with the following format
where the fields have the obvious meanings. A leftist heap is specified by giving a pointer to its root.
/* The following algorithm joins two leftist heaps whose roots are pointed at by r1 and r2, and returns a pointer to
the root of the resulting leftist heap. */
function UNION (r1 , r2)
if r1 = nil then return r2
else if r2 = nil then return r1 else
if key[r1] > key[r2] then r1 ←→ r2 rchild[r1] ← UNION ( rchild[r1] , r2 ) if d(rchild[r1]) > d(lchild[r1])
then rchild[r1] ←→ lchild[r1] dist[r1]←d(rchild[r1])+1
return r1
end {UNION}
function d(x) /*returnsdist(x)*/ if x = nil then return −1
else return dist[x] end {d}
What is the complexity of this algorithm? First, observe that there is a constant number of steps that must be executed before and after each recursive call to UNION. Thus the com- plexity of the algorithm is proportional to the number of recursive calls to UNION. It is easy to see that, in the worst case, this will be equal to p1 + p2 where p1 (respectively p2) is 1 plus the length of the right path of the leftist heap whose root is pointed at by r1 (respectively r2). Let the number of nodes in these trees be n1, n2. By the above Corol- lary we have p1 ≤ log (n1 +1) , p2 ≤ log (n2 +1) . Thus p1 + p2 ≤ log n1 + log n2 + 2. Let n=max(n1,n2). Then p1+p2≤ 2logn+2. Therefore, UNION is called at most 2 log n + 2 times and the complexity of the algorithm is O(log (max(n1, n2))) in the worst case.
Figure 2 below shows an example of the UNION operation.
Armed with the UNION algorithm we can easily write algorithms for INSERT and DELETEMIN:
lchild
key
dist
rchild
-4-
11 1
14 2
35 1
15 0
22 1
16 1
24 000000
39 37 31
26 20
18 0
35 1
UNION
14
28 0
11 2
2
22 15 39 37
1100
24
26
16
31 0
01 0
28 0
20 18 00
Figure 2. The UNION oparation.
INSERT(e, r) {e is an element, r is pointer to root of tree} 1. Let r ́ be a pointer to the leftist heap containing only e 2. return UNION (r ́ , r).
DELETEMIN(r )
1. min ← element stored at r (root of leftist heap)
2. r ← UNION(lchild[r] , rchild[r])
3. return min.
By our analysis of the worst case time complexity of UNION it follows immediately that the complexity of both these algorithms is O(log n) in the worst case, where n is the num- ber of nodes in the leftist heap.
In closing, we note that INSERT can be written as in the heap representation of priority queues, by adding the new node at the end of the right path, percolating its value up (if necessary), and switching right and left children of some nodes (if necessary) to maintain the properties of the leftist heap after the insertion. As an exercise, write the INSERT algorithm for leftist heaps in this fashion. On the other hand, we cannot use the idea of percolating values down to implement DELETEMIN in leftist heaps the way we did in standard heaps: doing so would result in an algorithm with O(n) worst case complexity. As an exercise, construct a leftist heap where this worst case behaviour would occur.