## Sunday, 22 January 2017

### Chapter 23 Exercise 7, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

23.7 (Min-heap) 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.

public class Exercise07 {
/** Heap sort method */
public static <E extends Comparable<E>> void heapSort(E[] list) {
// Create a Heap of integers
Heap<E> heap = new Heap<E>();

// Add elements to the heap
for (int i = 0; i < list.length; i++)

// Remove elements from the heap
for (int i = list.length - 1; i >= 0; i--)
list[i] = heap.remove();
}

/** A test method */
public static void main(String[] args) {
Integer[] list = { -44, -5, -3, 3, 3, 1, -4, 0, 1, 2, 4, 5, 53 };
heapSort(list);
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}

static class Heap<E extends Comparable<E>> {
private java.util.ArrayList<E> list = new java.util.ArrayList<E>();

/** Create a default heap */
public Heap() {
}

/** Create a heap from an array of objects */
public Heap(E[] objects) {
for (int i = 0; i < objects.length; i++)
}

/** Add a new object into the heap */
list.add(newObject); // Append to the heap
int currentIndex = list.size() - 1; // The index of the last node

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

currentIndex = parentIndex;
}
}

/** Remove the root from the heap */
public E remove() {
if (list.size() == 0)
return null;

E removedObject = list.get(0);
list.set(0, list.get(list.size() - 1));
list.remove(list.size() - 1);

int currentIndex = 0;
while (currentIndex < list.size()) {
int leftChildIndex = 2 * currentIndex + 1;
int rightChildIndex = 2 * currentIndex + 2;

// 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(list.get(rightChildIndex)) > 0) {
maxIndex = rightChildIndex;
}
}

// 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
}

return removedObject;
}

/** Get the number of nodes in the tree */
public int getSize() {
return list.size();
}
}

}