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> { 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