Question? Leave a message!

Leftist heap example

leftist heap merge animation and leftist heap visualization
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
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 © 20143 by Douglas Wilhelm Harder. Some rights reserved.Leftist heaps 2 Background A binary min-heap 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 min-heaps, 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 node-based 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 sub-tree that has a non-full node close to its root – How do you measure how close a non-full node is to the root?Leftist heaps 4 Minimum null-path 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 null-path length (npl) The minimum null-path length (min-npl) of a tree is the shortest distance from the root node to a non-full node Like height, – The min-npl of a single node is 0 – The min-npl of an empty tree defined as –1Leftist heaps 5 Minimum null-path length A few observations: – A binary tree with min-npl of m contains a perfect tree of height m m + 1 – Therefore, a binary tree with a min-npl of m has at least 2– 1 nodes – If a binary tree has to sub-trees with min-npls of m and m , then the 1 2 min-npl of the tree is 1 + min(m , m ) 1 1 // recursive definitionany real implementation would use // member variables to store the minimum null-path length template typename Type int Binary_treeType::min_null_path_length() const return empty() ? -1 : 1 + std::min( left() -min_null_path_length(), right()-min_null_path_length() ); Leftist heaps 6 Minimum null-path length A leftist heap is a heap where the min-npl of the left sub-tree is always greater than or equal to the min-npl of the right sub-tree and both sub-trees are leftist heaps The term leftist is results from the tree being heavier in the left rather than the right sub-treeLeftist 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 sub-heapsLeftist 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 sub-heap is not empty, merge the other heap with the right sub- heap of the selected root • If the right sub-heap is empty, attach the other heap as the right sub-heap 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 sub-heap A 2Leftist heaps 10 Merging We will now repeat the merging procedureLeftist heaps 11 Merging In the special case that the right sub-heap of A is empty, we attach the leftist heap B as the right sub-heap 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 sub-heap A 22Leftist heaps 14 Merging If B A , B becomes the right sub-heap of A and we now merge the 2 right sub-heap of B with the sub-heap 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 Binary_treeType::leftist_merge( Binary_treeType tree, Binary_treeType &ptr_to_this ) // Perform the merge if ( empty() ) ptr_to_this = tree; else if ( retrieve() tree-retrieve() ) right()-leftist_merge( tree, right_tree ); else ptr_to_this = tree; tree-right()-leftist_merge( this, tree-right_tree ); // Corrections to maintain leftist property... Leftist heaps 17 Merging This procedure is repeated until the right sub-heap 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 min-npls of the two sub- heaps and swap them if the right min-npl is greater than the left min-npl – 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 sub-heap of the first heapLeftist heaps 20 Merging Comparing 3 and 4, 4 3 so we exchange the two heaps and merge the detached sub-heap with the right sub-heap of 3