(a) Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9,...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
(a) Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2, one at a time and in the giver order, into an initially empty binary min heap. (b) Show the result of performing three deleteMin operations in the heap of the previous binary min heap. (c) Write a method replaceKey in the MinHeap class with the following signature: public void replaceKey(Integer oldKey, Integer newKey) The method will replace the first occurrence of oldKey with the newKey, and restore the Min-Heap property after the change. If the oldKey does not exist in the heap, the method prints an appropriate message and returns without changing the heap. Example: Suppose our binary heap object (bh) has the following keys: *** 4 6 7 32 19 64 26 99 42 54 28 Then the method call: bh.replaceKey (oldKey Integer(54), newKey Integer(2)) should change the keys to: *** 2 4 7 32 6 64 26 99 42 19 28 Note: You can assume that the methods perlocateUp and perlocateDown are already implemented in your MinHeap class. (d) What is the running time complexity of your replaceKey method? Justify (e) Consider an initially empty max-heap, where the following keys are to be inserted one at a time: 11, 19, 23, 12, 13, 17, 13, 14, 18, and 33. Draw the tree that results after building this max-heap. (f) Is it possible to find the maximum in a min-heap with N integer nodes in O(logn) time? Justify. Important Notes: For this problem, you have only one Java implementation in part (c). In this part you need to submit only the implementation of the replaceKey method. For parts (a), (b), and (e) of this problem, you must draw the min (or max) heaps using the appropriate graphics tools at your convenience. Heaps that were drawn by hand will be not accepted. (a) Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2, one at a time and in the giver order, into an initially empty binary min heap. (b) Show the result of performing three deleteMin operations in the heap of the previous binary min heap. (c) Write a method replaceKey in the MinHeap class with the following signature: public void replaceKey(Integer oldKey, Integer newKey) The method will replace the first occurrence of oldKey with the newKey, and restore the Min-Heap property after the change. If the oldKey does not exist in the heap, the method prints an appropriate message and returns without changing the heap. Example: Suppose our binary heap object (bh) has the following keys: *** 4 6 7 32 19 64 26 99 42 54 28 Then the method call: bh.replaceKey (oldKey Integer(54), newKey Integer(2)) should change the keys to: *** 2 4 7 32 6 64 26 99 42 19 28 Note: You can assume that the methods perlocateUp and perlocateDown are already implemented in your MinHeap class. (d) What is the running time complexity of your replaceKey method? Justify (e) Consider an initially empty max-heap, where the following keys are to be inserted one at a time: 11, 19, 23, 12, 13, 17, 13, 14, 18, and 33. Draw the tree that results after building this max-heap. (f) Is it possible to find the maximum in a min-heap with N integer nodes in O(logn) time? Justify. Important Notes: For this problem, you have only one Java implementation in part (c). In this part you need to submit only the implementation of the replaceKey method. For parts (a), (b), and (e) of this problem, you must draw the min (or max) heaps using the appropriate graphics tools at your convenience. Heaps that were drawn by hand will be not accepted.
Expert Answer:
Related Book For
Data Structures and Algorithm Analysis in Java
ISBN: 978-0132576277
3rd edition
Authors: Mark A. Weiss
Posted Date:
Students also viewed these programming questions
-
Quakers Inc. has an equity beta of 1.8. The tax rate is 35%. The firm has 30% debt and 70% equity. What is its asset beta? O 0.4036 O 0.6229 O 1.4078 O 1.8624
-
CANMNMM January of this year. (a) Each item will be held in a record. Describe all the data structures that must refer to these records to implement the required functionality. Describe all the...
-
The following additional information is available for the Dr. Ivan and Irene Incisor family from Chapters 1-5. Ivan's grandfather died and left a portfolio of municipal bonds. In 2012, they pay Ivan...
-
What is the future value of the following cash flows, given an appropriate discount rate of 7.74% (to the nearest penny)? Year 1 Year 2 Year 3 Year 4 Year 5 $2,005 $4,054 $6,159 $8,532 $11,985
-
The Electrolux Group (hereafter Electrolux) is a producer of home appliances and appliances for professional use, selling more than 40 million products to customers in 150 countries. The companys...
-
The Chapter Problem for Chapter 3 includes Table, which lists the numbers of chocolate chips in Chips Ahoy regular cookies. Those numbers have a distribution that is approximately normal with a mean...
-
Which of the following is NOT a control implication of distributed data processing? a. redundancy b. user satisfaction c. incompatibility d. lack of standards
-
Why are companies like Kmart able to continue in business after experiencing federal indictments, convictions of top executives, and bankruptcy, while accounting firms, like the once highly...
-
21 IIST T a) How many subsets does it have? b) How many proper subsets does it have? a) The set has subsets. (Simplify your answer.)
-
On January 1, 2024, Morrow Incorporated purchased a spooler at a cost of $40,000. The equipment is expected to last eight years and have a residual value of $4,000. During its eight-year life, the...
-
Q2. Suppose that time series {X} is an AR(1) process Xt = axt-1 Wt, where 0 < a <1 and W is normalized standard white noise with Wt ~ N(0, 1). If we have observed X1 and X3, and we would like to...
-
The half life of Solonium is 84 years. You had 35 grams of Solonium in 1977 , write a model where x is the number of Years since 1977 and y is the amount of Solonium left. (write two ordered pairs...
-
Quick Fix Inc. repairs bikes. The company's revenue is modeled by the function R(h)=220h-160 for every h hours spent repairing bikes. The company's overhead cost is modeled by the function...
-
In what ways do iterative processes exemplify the principle of gradual evolution within dynamic environments ?
-
5. Answer the following questions regarding dividend discount models: b. What is the general formula to calculate the capital gains yield and the dividend yield of a stock (one that holds when firm's...
-
S-F:7-5 Journalizing petty cash Learning Objective 4 Prepare the journal entries for the following petty cash transactions of Online Gaming Supplies: Mar. 1 Established a petty cash fund with a $150...
-
Design an experiment to demonstrate that RNA transcripts are synthesized in the nucleus of eukaryotes and are subsequently transported to the cytoplasm.
-
That 25 -cent postcard in the gift shop may soon become a thing of the past. RogueSheeps postage application is giving the traditional postcard a run for its money, as it allows users to send a...
-
Using the data in BE3-1 1, prepare the cost section of port for Motta Company.
-
Data for Madlock Company are given in BE3-8. Production records indicate that 18,000 units were transferred out, and 2,000 units in ending work in process were 50% complete as to conversion cost and...
Study smarter with the SolutionInn App