/** ========Implementation of Priority Heap ====== Complete the following class
ID: 657534 • 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
}
/**return the min Item */
public Item min(){
//TODO: get the min item and return
//dummy return
return null;
}
/** remove and return the root node, i.e. min Item */
public Item removeMin(){
//TODO: remove the min item and return
//dummy return
return null;
}
//traverse the heap
public String inOrderTraversal(){
String output = "";
//TODO: return a string representing the in order traversal of the heap
return output;
}
//======
//return the number of elements in the heap
public int size(){
return this.count;
}
//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
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
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.