Give an algorithm to perform deletemin

Assignment Help Basic Computer Science
Reference no: EM13968376

The 2-d heap is a data structure that allows each item to have two individual keys. deleteMin can be performed with respect to either of these keys. The 2-d heap is a complete binary tree with the following order property: For any node at even depth, the item stored at has the smallest key #1 in its subtree, while for any node at odd depth, the item stored at has the smallest key #2 in its subtree.

a. Draw a possible 2-d heap for the items (1,10), (2,9), (3,8), (4,7),  (5,6).

b. How do we ?nd the item with minimum key #1?

c. How do we ?nd the item with minimum key #2?

d. Give an algorithm to insert a new item into the 2-d heap.

e. Give an algorithm to perform deleteMin with respect to either key.

f. Give an algorithm to perform buildHeap in linear time.

Reference no: EM13968376

Questions Cloud

What the treatment is and how it is believed to help people : For this assignment, locate a credible source of your own about a current or recent advancement in the treatment of a mental disorder. In 1-2 pages, explain what the treatment is and how it is believed to help people who have been diagnosed with t..
Implement the pairing heap : 1. Use a k-d tree to implement deleteMin. What would you expect the  average running time to be for a random tree? 2. Use a k-d heap to implement a double-ended queue that also supports deleteMin.
Implement a double-ended priority queue : 1. Generalize the preceding exercise to obtain a k-d heap, in which each item can have k individual keys. You should be able to obtain the following bounds: insert in O(log N), deleteMin in O(2k log N), and buildHeap in O(kN). 2. Show that the k-d he..
Discuss any dual diagnosis issues : Discuss any dual diagnosis issues that are likely with this diagnosis. (Please include at least one source external to the text, to support your conclusions regarding possible dual diagnosis)
Give an algorithm to perform deletemin : Give an algorithm to insert a new item into the 2-d heap. Give an algorithm to perform deleteMin with respect to either key. Give an algorithm to perform buildHeap in linear time.
Find diffusion coefficient water at thermal neutron energy : Calculate the diffusion coefficient (D) of (light) water at thermal neutron energy (i.e., 0.025eV). Present your answer in cm.
Write a paper on afganistan on political stance information : Write a 4 page paper not counting title or refrence page in apa format on afganistan on the political stance information on military the economy social terrain features physical enviroment.
Describe the key components to the mental status exam : Describe the key components to the Mental Status Exam (MSE). How do the results of an MSE apply to diagnosis and treatment planning
Implement the insertion and range : 1. Suppose we call rotateWithLeftChild on an arbitrary 2-d tree. Explain in detail all the reasons that the result is no longer a usable 2-d tree. 2. Implement the insertion and range search for the k-d tree. Do not use recursion.

Reviews

Write a Review

Basic Computer Science Questions & Answers

  Identifies the cost of computer

identifies the cost of computer components to configure a computer system (including all peripheral devices where needed) for use in one of the following four situations:

  Input devices

Compare how the gestures data is generated and represented for interpretation in each of the following input devices. In your comparison, consider the data formats (radio waves, electrical signal, sound, etc.), device drivers, operating systems suppo..

  Cores on computer systems

Assignment : Cores on Computer Systems:  Differentiate between multiprocessor systems and many-core systems in terms of power efficiency, cost benefit analysis, instructions processing efficiency, and packaging form factors.

  Prepare an annual budget in an excel spreadsheet

Prepare working solutions in Excel that will manage the annual budget

  Write a research paper in relation to a software design

Research paper in relation to a Software Design related topic

  Describe the forest, domain, ou, and trust configuration

Describe the forest, domain, OU, and trust configuration for Bluesky. Include a chart or diagram of the current configuration. Currently Bluesky has a single domain and default OU structure.

  Construct a truth table for the boolean expression

Construct a truth table for the Boolean expressions ABC + A'B'C' ABC + AB'C' + A'B'C' A(BC' + B'C)

  Evaluate the cost of materials

Evaluate the cost of materials

  The marie simulator

Depending on how comfortable you are with using the MARIE simulator after reading

  What is the main advantage of using master pages

What is the main advantage of using master pages. Explain the purpose and advantage of using styles.

  Describe the three fundamental models of distributed systems

Explain the two approaches to packet delivery by the network layer in Distributed Systems. Describe the three fundamental models of Distributed Systems

  Distinguish between caching and buffering

Distinguish between caching and buffering The failure model defines the ways in which failure may occur in order to provide an understanding of the effects of failure. Give one type of failure with a brief description of the failure

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd