Question? Leave a message!




Leftist heaps

Leftist heaps
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
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 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
sharer
Presentations
Free