/** ========Implementation of Priority Heap ====== Complete the following class
ID: 657585 • 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 MinHeap
{
private int[] Heap;
private int size;
private int maxsize;
private static final int FRONT = 1;
public MinHeap(int maxsize)
{
this.maxsize = maxsize;
this.size = 0;
Heap = new int[this.maxsize + 1];
Heap[0] = Integer.MIN_VALUE;
}
private int parent(int pos)
{
return pos / 2;
}
private int leftChild(int pos)
{
return (2 * pos);
}
private int rightChild(int pos)
{
return (2 * pos) + 1;
}
private boolean isLeaf(int pos)
{
if (pos >= (size / 2) && pos <= size)
{
return true;
}
return false;
}
private void swap(int fpos, int spos)
{
int tmp;
tmp = Heap[fpos];
Heap[fpos] = Heap[spos];
Heap[spos] = tmp;
}
private void minHeapify(int pos)
{
if (!isLeaf(pos))
{
if ( Heap[pos] > Heap[leftChild(pos)] || Heap[pos] > Heap[rightChild(pos)])
{
if (Heap[leftChild(pos)] < Heap[rightChild(pos)])
{
swap(pos, leftChild(pos));
minHeapify(leftChild(pos));
}else
{
swap(pos, rightChild(pos));
minHeapify(rightChild(pos));
}
}
}
}
public void insert(int element)
{
Heap[++size] = element;
int current = size;
while (Heap[current] < Heap[parent(current)])
{
swap(current,parent(current));
current = parent(current);
}
}
public void print()
{
for (int i = 1; i <= size / 2; i++ )
{
System.out.print(" PARENT : " + Heap[i] + " LEFT CHILD : " + Heap[2*i]
+ " RIGHT CHILD :" + Heap[2 * i + 1]);
System.out.println();
}
}
public void minHeap()
{
for (int pos = (size / 2); pos >= 1 ; pos--)
{
minHeapify(pos);
}
}
public int remove()
{
int popped = Heap[FRONT];
Heap[FRONT] = Heap[size--];
minHeapify(FRONT);
return popped;
}
public static void main(String...arg)
{
System.out.println("The Min Heap is ");
MinHeap minHeap = new MinHeap(15);
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(17);
minHeap.insert(10);
minHeap.insert(84);
minHeap.insert(19);
minHeap.insert(6);
minHeap.insert(22);
minHeap.insert(9);
minHeap.minHeap();
minHeap.print();
System.out.println("The Min val is " + minHeap.remove());
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.