6.25 We can perform buildHeap in linear time for leftist heaps by considering each ele- ment as a one-node leftist heap, placing all these heaps on a queue, and performing the following step: Until only one heap is on the queue, dequeue two heaps, merge them, and enqueue the result.
a. Prove that this algorithm is O(N) in the worst case.
b. Why might this algorithm be preferable to the algorithm described in the text?
6.26 Merge the two skew heaps in Figure 6.59.
6.27 Show the result of inserting keys 1 to 15 in order into a skew heap.
6.28 Prove or disprove: A perfectly balanced tree forms if the keys 1 to 2k −1 are inserted in order into an initially empty skew heap.
6.29 A skew heap of N elements can be built using the standard binary heap algorithm. Can we use the same merging strategy described in Exercise 6.25 for skew heaps to get an O(N) running time?
Already registered? Login
Not Account? Sign up
Enter your email address to reset your password
Back to Login? Click here