Question

1 Approved Answer

Posted on Sep 26, 2024

Heaps in Java Exercise Part 1: Add the following methods to Heap.java Method T findMin() that returns the key with the smallest priority. For instance,

Heaps in Java Exercise

Part 1: Add the following methods to Heap.java

Method T findMin() that returns the key with the smallest priority. For instance, if the heap is

0 1 2 3 4 5 6 7 8 9

the method returns 5. As another example, if the heap is [20, 10, 15, 6, 9, 6], it should return 6. To implement this method, you must not search the entire ArrayList. Rather, you should make use of the heap property and do a smart search. [Hint: the smallest element is always a leaf node].

Method T dequeueMin() that returns the key with the smallest priority and also deletes it. You can modify the sifting up operation to do this. For instance, if the heap is:

0 1 2 3 4 5 6 7 8 9

you would first find the smallest priority item using findMin(), then remove the last item (50) and put it in the place of 5.

0 1 2 3 4 5 6 7 8

Next sift 50 up until it finds the right spot.

0 1 2 3 4 5 6 7 8

If there are multiple keys with the minimum value, T dequeueMin() just removes one item.

Test the two methods in HeapDemo.java. Provide at least three sample outputs.

Part 2: Implement the HeapSort algorithm. The HeapSort algorithm is simple: Build a heap and destroy it. For this, write another client program HeapDemo2.java reads a text file with words, builds a heap with those words, and repeatedly removes the max item and puts it another text file. The resulting text file will have the words sorted in descending order. For example, if the input word file is:

there their about would these other which

the output word file is:

would which these there their other about

Test your program using a sample text file.

Part 3: Write a program HeapDemo3.java that has the following static method:

public static> Heap merge(Heap heap1, Heap heap2)

for merging two heaps. A simple way of merging two heaps is to copy the first heap into the result heap and then insert the items one by one from the second heap into the result heap. For instance, if the two heaps are:

0 1 2 3 4 5 6

0 1 2 3 4

the resulting merged heap will be:

0 1 2 3 4 5 6 7 8 9 10 11

Test your program for at least three sample outputs.

Part 4(Optional): The above strategy has an order of complexity O(nlogn). Can you design a faster algorithm?

Heap.java

import java.util.ArrayList; public class Heap> { ArrayList heapList; public Heap() { heapList = new ArrayList(); } public int size() { return heapList.size(); } public boolean isEmpty() { return heapList.isEmpty(); } public void clear() { heapList.clear(); } public void enumerate() { System.out.println(heapList); } public void add(T item) { heapList.add(item); int index = heapList.size()-1; int pindex = (index-1)/2; T parent = heapList.get(pindex); while (index>0 && item.compareTo(parent)>0) { heapList.set(index, parent); heapList.set(pindex, item); index = pindex; pindex = (index-1)/2; parent = heapList.get(pindex); } } public T deleteMax() { if (isEmpty()) { System.out.println("Heap is empty"); return null; } else { T ret = heapList.get(0); //get the item in the root. This is the largest item. T item = heapList.remove(heapList.size()-1); //remove the last item. if (heapList.size()==0) return ret;//if there was only one item in the heap to begin with, we are done. heapList.set(0, item); //otherwise, proceed. Put the item in the root. int index, lIndex, rIndex, maxIndex; T maxChild; boolean found=false; index = 0; lIndex = index*2+1; rIndex = index*2+2; while (!found) { if (lIndex0) { maxChild = heapList.get(lIndex); maxIndex = lIndex; } else { maxChild = heapList.get(rIndex); maxIndex = rIndex; } //sift down if necesssary if (item.compareTo(maxChild)<0) { heapList.set(maxIndex, item); heapList.set(index, maxChild); index = maxIndex; } else found = true; } else if (lIndex < size()) //case 2: item to be sifted down has only left child //note: item to be sifted down cannot have only right child - it will violate the complete binary tree property { if (item.compareTo(heapList.get(lIndex))<0) { heapList.set(index, heapList.get(lIndex)); heapList.set(lIndex,item); index = lIndex; } else found = true; } else //case 3: item to be sifted down has no children found = true; lIndex = index*2+1; rIndex = index*2+2; } return ret; } } }

HeapDemo.java

import java.util.Scanner; public class HeapDemo { public static void main(String[] args) { Heap myHeap = new Heap(); Scanner keyboard = new Scanner(System.in); System.out.print("Enter positive integers into the heap (-1 when done): "); Integer num = keyboard.nextInt(); while (num!=-1) { myHeap.add(num); num = keyboard.nextInt(); } System.out.println("The heap: "); myHeap.enumerate(); System.out.print("How many nodes to delete (0 to " + myHeap.size() + ")? "); int d = keyboard.nextInt(); if (d<0||d>myHeap.size()) System.out.println("Can't delete"); else if (d==0) myHeap.enumerate(); for(int i=1; i<=d;i++){ System.out.println("Deleting " + myHeap.deleteMax()); myHeap.enumerate(); } } }