JAVA PROGRAM ----------------------------------------------

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:

1: [90, 80, 60, 20, 70, 10, 15]

2: [85, 20, 70, 10, 5]

Result: [90, 85, 60, 80, 70, 10, 15, 20, 20, 70, 10, 5]

Test your program for at least three sample outputs.

Bonus: The above strategy has an order of complexity O(nlogn). For bonus marks, 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; } } }