r3gor
diff --git a/‎Exercise_23/Exercise_23_07/Exercise_23_07.class‎
1.25 KB b/‎Exercise_23/Exercise_23_07/Exercise_23_07.class‎
1.25 KB
diff --git a/‎Exercise_23/Exercise_23_07/Exercise_23_07.java‎
Lines changed: 32 additions & 0 deletions b/‎Exercise_23/Exercise_23_07/Exercise_23_07.java‎
Lines changed: 32 additions & 0 deletions
diff --git a/‎Exercise_23/Exercise_23_07/Heap.class‎
1.57 KB b/‎Exercise_23/Exercise_23_07/Heap.class‎
1.57 KB
diff --git a/‎Exercise_23/Exercise_23_07/Heap.java‎
Lines changed: 77 additions & 0 deletions b/‎Exercise_23/Exercise_23_07/Heap.java‎
Lines changed: 77 additions & 0 deletions
@@ -0,0 +1,32 @@
+/*********************************************************************************
+* (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 Exercise_23_07 {
+	/** Heap sort method */
+	public  static <E extends Comparable<E>> void heapSort(E[] list) {
+		// Create a Heap of integers
+		Heap<E> heap = new Heap<>();
+
+		// Add elements to the heap
+		for (int i = 0; i < list.length; i++) 
+			heap.add(list[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] + " ");
+		System.out.println();
+	}
+}
@@ -0,0 +1,77 @@
+public class Heap<E extends Comparable<E>> {
+	private java.util.ArrayList<E> list = new java.util.ArrayList<>();
+
+	/** 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(objects[i]);
+	}
+
+	/** 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
+
+		while (currentIndex > 0) {
+			int parentIndex = (currentIndex - 1) / 2;
+			// Swap if the current object is less 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 greater 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();
+	}
+}