Algorithm to merge the two heaps

Assignment Help Basic Computer Science

Reference no: EM13968210

Suppose that binary heaps are represented using explicit links. Consider the prob- lem of merging binary heap lhs with rhs. Assume both heaps are perfect binary trees, containing 2l - 1 and 2r - 1 nodes, respectively.

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.

Reference no: EM13968210

Questions Cloud

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

Power company to environmental-sustainability coordinator : After you complete your degree, you are hired by The Peddle Power Company to be their Environmental/Sustainability Coordinator. This is a new position for them, in the past they have made sure to comply with environmental rules and regulations and co..

Problem regarding the complexity of algorithm : If a d-heap is stored as an array, for an entry located in position i, where are the parents and children?

For the soon-to-be-incorporated firm of ebroadcast sports : Dennis is a promoter for the soon-to-be-incorporated firm of eBroadcast Sports, Inc. Dennis signs a contract with Fitz & Geraldo, Accountants, to render their services before eBroadcast Sports is incorporated and for one year after the incorporation.

User Account

All Pages