/** ========Implementation of Priority Heap ====== Complete the following class
ID: 3715233 • Letter: #
Question
/**
========Implementation of Priority Heap ======
Complete the following class with given prototype/header of a priority heap
+ Look for the TODO tasks and complete them
+ You may need to create a few more helper methods and heapify methods
+ add more test cases into the driver to test your code
*/
import java.util.*;
public class QHeap <K, V>{
//==========================================================
/** a simple nested class to represent the key-value pair */
class Item<K,V>{
public K key;
public V value;
public Item(K key, V value){
this.key = key;
this.value = value;
}
public String toString(){
return "key: " + this.key + " Value: " + this.value;
}
}//end of nested class
//==========================================================
//attributes
private final int DEFAULT_CAPACITY = 15;
private int count;
private int capacity; //the maximum heap before resize is needed
private ArrayList< Item<K,V> > storage;//array used to store the items
//constructors
public QHeap(){ //new heap with default size
this.count = 0; //no item in the storage yet
this.capacity = DEFAULT_CAPACITY;
//create the storage
this.storage = new ArrayList< Item<K,V> >(DEFAULT_CAPACITY);
}
/** create a heap with a specific size */
public QHeap(int requestSize){
this.count = 0; //no item in the storage yet
this.capacity = requestSize;
this.storage = new ArrayList< Item<K,V> >(this.capacity);//create the storage
}
/* copy constructor - copy the content of the given heap into a new one */
public QHeap(QHeap<K,V> given){
//TODO: copy the data of the given heap to the new heap ************
}
//methods
/* merge the given heap into this one */
public int merge(QHeap<K,V> second){
//TODO: merge the heap here ************
return this.count;
}
/** insert a key/value pair - the key is use for priority */
public void insert(K key, V value){
//TODO: insert an Item into the heap ************
//invoke heapify operation to keep the heap integrity
}
public int compare(Item a, Item b) throws ClassCastException{
return ((Comparable<Item>)a).compareTo(b);
}
protected void downheap(int j) {
while (hasLeft(j)) { // continue to bottom (or break statement)
int leftIndex = left(j);
int smallChildIndex = leftIndex; // although right may be smaller
if (hasRight(j)) {
int rightIndex = right(j);
if (compare(storage.get(leftIndex), storage.get(rightIndex)) > 0)
smallChildIndex = rightIndex; // right child is smaller
}
if (compare(storage.get(smallChildIndex), storage.get(j)) >= 0)
break; // heap property has been restored
swap(j, smallChildIndex);
j = smallChildIndex; // continue at position of the child
}
}
protected int left(int j) {
return 2*j +1;
}
protected int right(int j) {
return 2*j +2;
}
protected boolean hasLeft(int j){
return left(j) < storage.size();
}
protected boolean hasRight(int j){
return right(j) < storage.size();
}
public int size() {
return storage.size();
}
protected void swap(int i, int j) {
Item <K,V> temp = storage.get(i);
storage.set(i, storage.get(j));
storage.set(j, temp);
}
/**return the min Item */
public Item min(){
//TODO: get the min item and return ************
if(storage.isEmpty())
return null;
//dummy return
return storage.get(0);
}
/** remove and return the root node, i.e. min Item */
public Item<K,V> removeMin(){
//TODO: remove the min item and return ************
if (storage.isEmpty())
return null;
Item<K,V> answer = storage.get(0);
swap(0, storage.size() - 1);
storage.remove(storage.size() - 1);
downheap(0);
//dummy return
return answer;
}
//traverse the heap
public String inOrderTraversal(){
String output = "";
//TODO: return a string representing the in order traversal of the heap ************
for(int i = 1; i <= count; i++)
output += storage[i]+" ";
return output;
}
//======
//return the number of elements in the heap
//return true if the heap is empty
public boolean isEmpty(){
return this.count <= 0;
}
//print the content of the heap
public String toString(){
//empty heap
if(this.storage == null || this.count <= 0)
return "";
//print the content of the heap
Iterator< Item<K,V> > itr = this.storage.iterator();
String output = "";
while(itr.hasNext())
output += itr.next();
return output;
}
//==============================================
//===== Driver
// TODO: add more testing cases
public static void main(String[] args){
//create a heap
QHeap heap = new QHeap<Integer, String>(20);
heap.insert(2, "p1");
heap.insert(3, "p2");
//todo: put more data
heap.insert(5, "p3");
heap.insert(4, "p4");
heap.insert(8, "p5");
System.out.println(heap.size());
System.out.println(heap);
System.out.println(heap.min());
heap.removeMin();
System.out.println(heap);
//testing traversal
System.out.println(heap.inOrderTraversal());
//create a new heap
QHeap<Integer, String> heap2 = new QHeap<Integer, String> (10);
heap2.insert(4, "some data");
heap2.insert(5, "some more data");
System.out.println(heap2);
//merge the heap
heap.merge(heap2);
System.out.println(heap);//print the merged heap
heap.removeMin();
heap2.removeMin();
System.out.println(heap.size());
System.out.println(heap);//print the merged heap
System.out.println(heap2.size());
System.out.println(heap2);//print the heap
//create a new heap by copying an existing one
QHeap heap3 = new QHeap<Integer, String>(heap2);
System.out.println(heap3.size());
System.out.println(heap3);
System.out.println(heap3.min());
heap.removeMin();
System.out.println(heap3);
}//==================================================
}//end of the class
Explanation / Answer
Solution:
public class Qheap
{
public int [] A;
public int n;
public Qheap(int H[])
throws IOException
{
A = new int[B.length];
n = A.length;
for(int i=n/2-1; i>=0; i--)
{
Heapify(i);
}
}
public void Heapify(int i)
{
int left, r, min, tmp;
left = 2 * i + 1;
r = 2 * i + 2;
if(left < n && A[left] < A[i])
min = left;
else
min = i;
if(r < n && A[r] < A[min])
min = r;
if(min != i)
{
tmp = A[i];
A[i] = A[min];
A[min] = tmp;
Heapify(min);
}
}
public void Insert(int key)
{
int i;
m++;
n=m-1;
while(n > 0 && A[(n-1)/2] > key)
{
A[n] = A[(n-1)/2];
n = (n-1)/2;
}
A[n] = key;
}
public int Delete_root()
{
int min;
if(m < 1)
{
System.out.println("error");
return -1;
}
else
{
min = A[0];
A[0] = A[m-1];
n--;
Heapify(0);
return min;
}
}
public int Empty()
{
if(m == 0)
return 1;
else
return 0;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.