Problem regarding the deletemin or findmin

Assignment Help Basic Computer Science

Reference no: EM13968213

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, removes 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 log N) time.

b. Propose an implementation, with an analysis to show that the time to perform the deleteMin is O(klog(2N/k)).

Reference no: EM13968213

Questions Cloud

About express and implied warranties on products : In this module you have learned about express and implied warranties on products as well as what elements a plaintiff must prove in order to succeed in a products liability case. Is there a stated warranty or is it an implied warranty? If it is state..

Perform insert using binomial queues : Give an algorithm to build a binomial queue of N elements, using at most N - 1 comparisons between elements. Propose an algorithm to insert M nodes into a binomial queue of N elements in O(M + log N) worst-case time. Prove your bound. Write an ef?ci..

Harge of writing the organizations code of ethics : You’ve proven yourself to the CEO of your company or organization on multiple occasions. To show her appreciation, she has put you in charge of writing the organization's code of ethics. There is likely going to be a promotion attached to this honor...

Legitimate-nondiscriminatory reason for its action : Craig applies for a job at Dispatch Transportation & Warehousing, Inc., for which he is well qualified. He passes a test to determine which applicants are eligible for hiring, but the employer discards the results, and Craig is rejected. Dispatch con..

Problem regarding the deletemin or findmin : In this strategy, removes 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.

What level of output does the firm break even : Consider the cost data below for a perfectly competitive firm in the short run. If the market price is $150, how many units of output will the firm produce in order to maximize profit in the short run? Specify the amount of economic profit or los..

Why shouldn''t we restrict imports of goods : Some people have said that this shows a double standard: If we're willing to restrict goods on these grounds, why shouldn't we restrict imports of goods that are produced with badly paid labor? Why is or isn't this argument valid?

Algorithm to merge the two heaps : a. Give an O(log N) algorithm to merge the two heaps if l = r. b. Give an O(log N) algorithm to merge the two heaps if |l - r|= 1. c. Give an O(log2 N) algorithm to merge the two heaps regardless of l and r.

Brief overview of the organizations services : Brief overview of the organizations service/products and a description of their target market. This is important to ensure that your analysis considers the needs of the target market in evaluating their pricing and channel decisions

User Account

All Pages