JAVA program

A heap is essentially a priority queue. It is defined as a complete binary tree in which the key in every node x is greater than or equal to all the keys in the left and right subtrees of x. Since it is a complete binary tree, it can be implemented using a simple ArrayList that stores the keys in level order.

Add the following methods to Heap.java

a) Method T findMin() that returns the key with the smallest priority. For instance, if the heap is [90, 80, 60, 20, 70, 10, 15, 5, 9, 50] 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].

b) 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: [90, 80,60, 20, 70, 10, 15, 5, 9, 50]

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

[90, 80, 60, 20, 70, 10, 15, 50, 9]

Next sift 50 up until it finds the right spot.

[90, 80, 60, 50, 70, 10,15,20, 9]

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

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(); } } }