Question? Leave a message!




Leftist heaps

Leftist heaps
ECE 250 Algorithms and Data Structures Leftist heaps Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20143 by Douglas Wilhelm Harder. Some rights reserved.Leftist heaps 2 Background A binary minheap allows the operations of push and pop to occur in an average case of Q(1) and Q(ln(n)) time, respectively Merging two binary minheaps, however, is an Q(n) operation Are there efficient heap structures that allow merging in Q(ln(n)) time Leftist heaps 3 An Idea A leftist heap is a nodebased binary tree New objects can be placed into a tree at any node which is not full – If we are to merge two heaps, one strategy would be to merge the heap with a subtree that has a nonfull node close to its root – How do you measure how close a nonfull node is to the rootLeftist heaps 4 Minimum nullpath length We will define a null path as any path from the root node to a node that is not full – The length of that path is the nullpath length (npl) The minimum nullpath length (minnpl) of a tree is the shortest distance from the root node to a nonfull node Like height, – The minnpl of a single node is 0 – The minnpl of an empty tree defined as –1Leftist heaps 5 Minimum nullpath length A few observations: – A binary tree with minnpl of m contains a perfect tree of height m m + 1 – Therefore, a binary tree with a minnpl of m has at least 2– 1 nodes – If a binary tree has to subtrees with minnpls of m and m , then the 1 2 minnpl of the tree is 1 + min(m , m ) 1 1 // recursive definitionany real implementation would use // member variables to store the minimum nullpath length template typename Type int BinarytreeType::minnullpathlength() const return empty() 1 : 1 + std::min( left() minnullpathlength(), right()minnullpathlength() ); Leftist heaps 6 Minimum nullpath length A leftist heap is a heap where the minnpl of the left subtree is always greater than or equal to the minnpl of the right subtree and both subtrees are leftist heaps The term leftist is results from the tree being heavier in the left rather than the right subtreeLeftist heaps 7 Merging We will demonstrate an algorithm for merging two leftist heaps Once we have a merging algorithm, we can implement push and pop in terms of merges: – Push is implemented as merging the leftist heap with a node being inserted treated as a trivial leftist heap – Pop is implemented by removing the root node and then merging the two subheapsLeftist heaps 8 Merging Merging two leftist heaps uses the following rules: – Given two leftist heaps, choose that heap that has the smaller root to be the leftist heap and: • If the right subheap is not empty, merge the other heap with the right sub heap of the selected root • If the right subheap is empty, attach the other heap as the right subheap of the selected rootLeftist heaps 9 Merging Suppose we are merging these two leftist heaps: – We compare the roots and note A ≤ B – Therefore, we merge the leftist heap B with the left subheap A 2Leftist heaps 10 Merging We will now repeat the merging procedureLeftist heaps 11 Merging In the special case that the right subheap of A is empty, we attach the leftist heap B as the right subheap of ALeftist heaps 12 Merging If, however, A is not empty, we must merge these two recursively: 2 – Either A ≤ B or A B 2 2Leftist heaps 13 Merging If A ≤ B, we repeat the process and merge the leftist heap B with 2 the right subheap A 22Leftist heaps 14 Merging If B A , B becomes the right subheap of A and we now merge the 2 right subheap of B with the subheap A 2Leftist heaps 15 Merging The three cases for merging heaps A and B 2 A is empty A ≤ B B A 2 2 2Leftist heaps 16 Merging Implementation: template typename Type int BinarytreeType::leftistmerge( BinarytreeType tree, BinarytreeType ptrtothis ) // Perform the merge if ( empty() ) ptrtothis = tree; else if ( retrieve() treeretrieve() ) right()leftistmerge( tree, righttree ); else ptrtothis = tree; treeright()leftistmerge( this, treerighttree ); // Corrections to maintain leftist property... Leftist heaps 17 Merging This procedure is repeated until the right subheap of tree is empty and the heap being merged is attached Once we have finished the merging process, we have a heap; however, it may no longer be leftist – As we traverse back to the root, compare the minnpls of the two sub heaps and swap them if the right minnpl is greater than the left minnpl – Recall that heaps are not ordered treesLeftist heaps 18 Merging Consider merging these two leftist heapsLeftist heaps 19 Merging Comparing the root nodes, 1 3 and thus we must merge the first leftist heap with the right subheap of the first heapLeftist heaps 20 Merging Comparing 3 and 4, 4 3 so we exchange the two heaps and merge the detached subheap with the right subheap of 3Leftist heaps 21 Merging Comparing 4 and 5, we exchange the two heaps and merge the detached subheap with the right subheap of 4Leftist heaps 22 Merging The right subheap of 4 is empty, and therefore we attach the heap with root 5Leftist heaps 23 Merging The heaps are merged, but the result is not a leftist heap We must recurs to the root and swap subheaps where necessaryLeftist heaps 24 Merging Node 3 is not a leftist heap and therefore we swap the two nodesLeftist heaps 25 Merging The root continues to have the leftist property and therefore we have merged the two leftist heapsLeftist heaps 26 Merging Implementation: template typename Type int BinarytreeType::leftistmerge( BinarytreeType tree, BinarytreeType ptrtothis ) // Perform the merge // Corrections to maintain leftist property if ( left()minnullpathlength() right()minnullpathlength() ) std::swap( lefttree, righttree ); Leftist heaps 27 Leftist Heaps Why the leftist property – The leftist property causes an imbalance towards the left – Insertions and merges are always performed to the right – This results in a balancing effect A push or insertion is simply the merging of an existing leftist heap and a trivial heap of size 1Leftist heaps 28 Pop We will demonstrate a pop from a leftist heapLeftist heaps 29 Pop Removing the minimum node results in two subheaps which we must mergeLeftist heaps 30 Pop nd Comparing the two root nodes, we must merge the 2 heap with the right subheap of the first:Leftist heaps 31 Pop Comparing 6 and 3, we exchange the two heaps and merge the detached subheap with the right subheap of 3Leftist heaps 32 Pop Comparing 7 and 6, we exchange the two heaps and merge the detached subheap with the right subheap of 6Leftist heaps 33 Pop The right subheap of 4 is empty, and therefore we attach the heap with root 5Leftist heaps 34 Pop As before, the heaps are merged, but the result is not a leftist heap – We must recurs back to the root and swap where necessaryLeftist heaps 35 Pop Node 6 is not a leftist heap and therefore we move the right sub heapLeftist heaps 36 Pop The root is not a leftist heap and therefore we swap the two sub heapsLeftist heaps 37 Pop The result is a leftist heapLeftist heaps 38 Implementation An implementation of a leftist heap data structure is available at http://ece.uwaterloo.ca/dwharder/aads/Algorithms/Leftistheaps/Leftist heaps 39 Summary This topic has covered leftist heaps: – Allow an averagetime O(ln(n)) merging of two heaps – Unlike a binary minheap, this uses linked allocationLeftist heaps 40 References 1 Cormen, Leiserson, and Rivest, Introduction to Algorithms, MIT Press, 1990, §7.13, p.152. rd 2 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §6.56, p.21525.Leftist heaps 41 Usage Notes • These slides are made publicly available on the web for anyone to use • If you choose to use them, or a part thereof, for a course at another institution, I ask only three things: – that you inform me that you are using the slides, – that you acknowledge my work, and – that you alert me of any mistakes which I made or changes which you make, and allow me the option of incorporating such changes (with an acknowledgment) in my set of slides Sincerely, Douglas Wilhelm Harder, MMath dwharderalumni.uwaterloo.ca
Website URL
Comment
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017