Question: One way to delete nodes from a known position in a leftist heap is to use a lazy strategy. To delete a node, merely mark

One way to delete nodes from a known position in a leftist heap is to use a lazy strategy. To delete a node, merely mark it deleted. When a findMin or deleteMin is performed, there is a potential problem if the root is marked deleted, since then the node has to be actually deleted and the real minimum needs to be found, which may involve deleting other marked nodes. In this strategy, deletes cost one unit, but the cost of a deleteMin or findMin depends on the number of nodes that are marked deleted. Suppose that after a deleteMin or findMin there are k fewer marked nodes than before the operation.
a. Show how to perform the deleteMin in O(k logN) time.
b. Propose an implementation, with an analysis to show that the time to perform the deleteMin is O(k log(2N/k)).

Step by Step Solution

★★★★★

3.50 Rating (173 Votes )

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock

Lazy deletion in leftist heaps is discussed in the paper by Cheriton and Tarjan 10 The g... View full answer

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Document Format (1 attachment)

1486-C-S-A(391).docx

120 KBs Word File

Students Have Also Explored These Related Algorithms Questions!

During the course of an algorithm, we sometimes find that we need to maintain past versions of a dynamic set as it is updated. Such a set is called persistent. One way to implement a persistent set...

One way to handle tables whose size is not known in advance is to make them fixed, but when one fills up, to replace it with a bigger one, copy the old entries over to the new one, then release the...

During the course of an algorithm, we sometimes find that we need to maintain past versions of a dynamic set as it is updated. We call such a set persistent. One way to implement a persistent set is...

In this quest you will implement a class called Playlist as a singly linked list of nodes with Song_Entry objects as their payloads. Your code should be organized into a header file (Playlist.h) and...

PLEASE HELP ME CODE THIS PROGRAM. ALL I ASK FOR ARE SOME EXAMPLES OF HOW TO GO ABOUT DOING THIS AS YOU WILL SEE IN MY BOLD & ITALIC MESSAGES THROUGHOUT THIS PROBLEM. I HAVE INCLUDED CODE FOR YOU TO...

) Explain the term overloading in the context of Java constructors and methods. [2 marks] (b) Without describing the details of either, outline the relationship between the Java methods...

Please SOLVE C++ ,almost done just need iterators, namespace, and display lab The universities really liked the ability to bundle the information for the labs, but now there is some consideration...

Hello, Below is the code I have written for this assignment so far, I was wondering if someone could give me some guidance or help as what I can do better, what I am doing wrong? import...

make a project on topic priority queue using binary heap help with the research paper giving above to implementation code in python data structure do it in one day S.L. Graham, R.L. Rivest Editors...

1 Program descriptions You will write six programs for this project. Except where explicitly noted, your programs may assume that their inputs are properly formatted. However, your programs should be...

Consider the data from Exercise 2.4.7. Use the five-number summary that is given to create a boxplot of the data. Exercise 2.4.7. Statistics software can be used to find the five-number summary of a...

6. Choose 2 terms and explain what these molecules do during both transcription and translation . Use your own words in this answer (also, use plain language, not a lot of terminology). You may...

Jensen Bank is making a commercial real estate loan on Jackson Apartments with the following data; purchase price of $ 2 0 million, loan to value ratio of 7 5 % , minimum debt service coverage of 1 ....

7. According to Engels law, a. the price elasticity of demand for food is inelastic. b. the income elasticity for food items is inelastic. c. the income elasticity for food items is elastic. d....

Suppose a user, Maria, discovers that her private RSA key (d 1, n 1) is same as the public RSA key (e 2, n 2) of another user, Frances. In other words, d 1 = e 2 and n 1 = n 2. Should Maria consider...

Consider the use of counter mode, as shown in Fig. 8-15, but with IV = 0. Does the use of 0 threaten the security of the cipher in general?

The signature protocol of Fig. 8-18 has the following weakness. If Bob crashes, he may lose the contents of his RAM. What problems do this cause and what can he do to prevent them?

LR Industries is considering the purchase of a new piece of equipment to meet the increased demand for its Model XL-4 tennis racket. The equipment costs $100,000 plus $5,000 for installation and...

Please help!! :) Prepare a proforma balance sheet and income statement for Apple Inc - year 2015. Use 10 percent as the growth rate and calculate EFN using percentage of sales approach. Period Ending...

i) You are provided the following information on the Mexican Peso: Current spot rate: $ 0.1000/MP (MP - Mexican Peso) 300 day interest rate in the US: 7% 300 day interest rate in Mexico: 25% 300 day...