The heap presented in the text is also known as a max-heap, in which each node is
Question:
The heap presented in the text is also known as a max-heap, in which each node is greater than or equal to any of its children. A min-heap is a heap in which each node is less than or equal to any of its children. Min-heaps are often used to implement priority queues. Revise the Heap class in Listing 23.9 to implement a min-heap.
Listing
Transcribed Image Text:
1 public class Heap
1 public class Heap> { private java.util.ArrayList list = new java.util.ArrayList<>(); 3 /** Create a default heap */ 4. public Heap() { 6 /** Create a heap from an array of objects * / public Heap (E[] objects) { for (int i = 0; i < objects.length; i++) add(objects[i]); 10 11 12 13 14 /** Add a new object into the heap */ public void add(E newObject) { list.add(newObject); // Append to the heap int currentIndex = list.size() - 1; // The index of the last node 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 while (currentIndex > 0) { int parentIndex = (currentIndex - 1) / 2; // Swap if the current object is greater than its parent if (list.get (currentIndex).compareTo( list.get (parentIndex)) > 0) { E temp = list. get(currentIndex); list.set(currentIndex, list.get (parentIndex)); list.set (parentIndex, temp); else break; // The tree is a heap now 31 currentIndex = parentIndex; 32 33 34 35 /** Remove the root from the heap */ public E remove() { if (list.size( == 0) return null; 36 37 38 E removedObject = list.get (0); list.set (0, list.get(list.size() - 1)); list.remove (1ist.size() - 1); 39 40 41 42 int currentIndex = 0; 43 while (currentIndex < list.size()) { 44 45 int leftChildIndex = 2 * currentIndex + 1; int rightChildIndex = 2 * currentIndex + 2; 46 47 // Find the maximum between two children if (leftChildIndex >= list.size()) break; // The tree is a heap int maxIndex = leftChildIndex; if (rightChildIndex < list.size()) { if (list.get(maxIndex).compareTo( 48 49 50 51 52 53 list.get(rightChildIndex)) < 0) { 54 maxIndex = rightChildIndex; 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 // Swap if the current node is less than the maximum if (list.get(currentIndex).compareTo( list.get(maxIndex)) < 0) { E temp = list.get(maxIndex); list.set (maxIndex, list.get(currentIndex)); list.set (currentIndex, temp); currentIndex - maxIndex; else break; // The tree is a heap 70 return removedObject; } 71 72 73 /** Get the number of nodes in the tree */ public int getSize() { return list.size(); 74 75 76 77
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 50% (10 reviews)
Program Plan Define a class called MinHeap Add a constructor with obje...View the full answer
Answered By
Emel Khan
I have the ability to effectively communicate and demonstrate concepts to students. Through my practical application of the subject required, I am able to provide real-world examples and clarify complex ideas. This helps students to better understand and retain the information, leading to improved performance and confidence in their abilities. Additionally, my hands-on approach allows for interactive lessons and personalized instruction, catering to the individual needs and learning styles of each student.
5.00+
2+ Reviews
10+ Question Solved
Related Book For
Introduction to Java Programming, Comprehensive Version
ISBN: 978-0133761313
10th Edition
Authors: Y. Daniel Liang
Question Posted:
Students also viewed these Computer science questions
-
Unicode value \u0000 is also known as ____________. a. Nil b. Null c. Nada d. Void
-
The procedure BUILD-MAX-HEAP in Section 6.3 can be implemented by repeatedly using MAX-HEAP-INSERT to insert the elements into the heap. Consider the following implementation: BUILD-MAX-HEAP'(A) 1...
-
We can build a heap by repeatedly calling MAX-HEAP-INSERT to insert the elements into the heap. Consider the following variation on the BUILD-MAX-HEAP procedure: BUILD-MAX-HEAP (A) 1 A.heap-size = 1...
-
Sandys Socks makes the worlds best socks. Information for the last eight months follows: Prepare a scatter graph by plotting Sandys data on a graph. Then draw a line that you believe best fits the...
-
If S = {x1, x2, . . . , xn} is affinely independent, every x aff S has a unique representation as an affine combination of the elements of S; that is, there are unique scalars a1, a2, . . . , an...
-
Explain briefly what is meant by an accounting system.
-
What are the implications for a country attempting to manage its domestic economy if it is subject to an international business cycle? How might it attempt to overcome such problems? The problem is...
-
Saunders Company has recently become aware of the large total discounts on its orders and would like to know the impact on profit. The company computed its operating profit as follows: Required(a)...
-
8) Melanie and Gabriela have a dispute regarding ownership of a dog, Buddy. Gabriela removed Buddy's tags in order to give him a bath. Knowing what was coming, Buddy made a run for it and ended up at...
-
Refer to the financial statements of Express, Inc. given in Appendix C. What amount of depreciation expense was reported as an expense for the most recent reporting year? EXPRESS, INC. CONSOLIDATED...
-
Implement the following sort method using a heap. public static > void sort(E[] list)
-
Write the following overloaded methods that check whether an array is ordered in ascending order or descending order. By default, the method checks ascending order. To check descending order, pass...
-
Sand Dollar Company purchases all merchandise on credit. It recently budgeted the following month-end accounts payable balances and merchandise inventory balances. Cash payments on accounts payable...
-
Parker County Community College (PCCC) is trying to determine whether to use no insulation or to use insulation that is either 1 inch thick or 2 inches thick on its steam pipes. The heat loss from...
-
Rena and Hunter Alesio have two children, ages 5 and 7. The Alesios want to start saving for their childrens education. Each child will spend 6 years at college and will begin at age 18. College...
-
Why are economists unable to come up with a systemic policy response to capital flows? Explain
-
A mixture of liquid fuels (methane 56%, ethane 29%, propane 15%) is stored in room C. At a room temperature of 40C, the vapour pressure of the fuel mixture would be 200mmHg. What is the lower...
-
Alden Company uses a two-variance analysis for overhead variances. Practical capacity is defined as 32 setups and 32,000 machine hours to manufacture 6,400 units for the year. Selected data for 2016...
-
When sample sizes are equal (Ji = J), the parameters a1, a2, ... aI of the alternative parameterization are restricted by (ai = 0. For unequal sample sizes, the most natural restriction is (Ji ai =...
-
Complete the following acid-base reactions: (a) HCCH + NaH
-
Define the analog hierarchy used by telephone companies and list different levels of the hierarchy.
-
We need to use synchronous TDM and combine 20 digital sources, each of 100 Kbps. Each output slot carries 1 bit from each digital source, but one extra bit is added to each frame for synchronization....
-
In the analog hierarchy of Figure 6.9, find the overhead (extra bandwidth for guard band or control) in each hierarchy level (group, supergroup, master group, and jumbo group). Figure 6.9 48 kHz 12...
-
Dunder Mifflin started the month of June with $ 1 2 2 , 8 8 9 in assets. During the month of June, they bought $ 7 0 , 0 6 4 worth of paper on account and received $ 2 4 , 7 4 1 from a customer on...
-
Discuss at least two legal implications or ethical issues in creating a training course that discusses culture. Identify what laws and regulations should be considered. Explain how the demographic...
-
Eliott and Anne are each 40% partners in the XYZ Partnership. On February 1, 2023, Eliott sold his interest to Tamera, who was already a 20% partner. On April 2, 2023, Anne sold her interest to...
Study smarter with the SolutionInn App