Objective: Maxheap priority queue Download inventory.txt, MaxHeap.java Default J
ID: 3775592 • Letter: O
Question
Objective: Maxheap priority queue
Download inventory.txt, MaxHeap.java
Default Java.util.PriorityQueue is Minimum Queue.
Write the main java program to read all records from inventory.txt to build a Maxheap Queue use both MaxHeap.java and java.util.PriorityQueue.
Print both Heap-queues and then remove the Max from Maxheap queue.
The order of the priority is the string value of the input records.
Given Codes:
/** Source code example for "A Practical Introduction to Data
Structures and Algorithm Analysis, 3rd Edition (Java)"
by Clifford A. Shaffer
Copyright 2008-2011 by Clifford A. Shaffer
*/
import java.lang.Comparable;
/** Max-heap implementation */
public class MaxHeap> {
private E[] Heap; // Pointer to the heap array
private int size; // Maximum size of the heap
private int n; // Number of things in heap
/** Constructor supporting preloading of heap contents */
public MaxHeap(E[] h, int num, int max)
{ Heap = h; n = num; size = max; buildheap(); }
/** @return Current size of the heap */
public int heapsize() { return n; }
/** @return True if pos a leaf position, false otherwise */
public boolean isLeaf(int pos)
{ return (pos >= n/2) && (pos < n); }
/** @return Position for left child of pos */
public int leftchild(int pos) {
assert pos < n/2 : "Position has no left child";
return 2*pos + 1;
}
/** @return Position for right child of pos */
public int rightchild(int pos) {
assert pos < (n-1)/2 : "Position has no right child";
return 2*pos + 2;
}
/** @return Position for parent */
public int parent(int pos) {
assert pos > 0 : "Position has no parent";
return (pos-1)/2;
}
/** Insert val into heap */
public void insert(E val) {
assert n < size : "Heap is full";
int curr = n++;
Heap[curr] = val; // Start at end of heap
// Now sift up until curr's parent's key > curr's key
while ((curr != 0) &&
(Heap[curr].compareTo(Heap[parent(curr)]) > 0)) {
DSutil.swap(Heap, curr, parent(curr)); // exchange content of Heap[curr] with Heap[parent(curr)]
curr = parent(curr);
}
}
/** Heapify contents of Heap */
public void buildheap()
{ for (int i=n/2 - 1; i>=0; i--) siftdown(i); }
/** Put element in its correct place */
private void siftdown(int pos) {
assert (pos >= 0) && (pos < n) : "Illegal heap position";
while (!isLeaf(pos)) {
int j = leftchild(pos);
if ((j<(n-1)) && (Heap[j].compareTo(Heap[j+1]) < 0))
j++; // j is now index of child with greater value
if (Heap[pos].compareTo(Heap[j]) >= 0) return;
DSutil.swap(Heap, pos, j);
pos = j; // Move down
}
}
/** Remove and return maximum value */
public E removemax() {
assert n > 0 : "Removing from empty heap";
DSutil.swap(Heap, 0, --n); // Swap maximum with last value
if (n != 0) // Not on last element
siftdown(0); // Put new heap root val in correct place
return Heap[n];
}
/** Remove and return element at specified position */
public E remove(int pos) {
assert (pos >= 0) && (pos < n) : "Illegal heap position";
if (pos == (n-1)) n--; // Last element, no work to be done
else
{
DSutil.swap(Heap, pos, --n); // Swap with last value
// If we just swapped in a big value, push it up
while ((pos > 0) &&
(Heap[pos].compareTo(Heap[parent(pos)]) > 0)) {
DSutil.swap(Heap, pos, parent(pos));
pos = parent(pos);
}
if (n != 0) siftdown(pos); // If it is little, push down
}
return Heap[n];
}
}
/** Source code example for "A Practical Introduction to Data
Structures and Algorithm Analysis, 3rd Edition (Java)"
by Clifford A. Shaffer
Copyright 2008-2011 by Clifford A. Shaffer
*/
import java.util.*;
import java.math.*;
/** A bunch of utility functions. */
class DSutil<E> {
/** Swap two Objects in an array
@param A The array
@param p1 Index of one Object in A
@param p2 Index of another Object A
*/
public static <E> void swap(E[] A, int p1, int p2) {
E temp = A[p1];
A[p1] = A[p2];
A[p2] = temp;
}
/** Randomly permute the Objects in an array.
@param A The array
*/
// int version
// Randomly permute the values of array "A"
static void permute(int[] A) {
for (int i = A.length; i > 0; i--) // for each i
swap(A, i-1, DSutil.random(i)); // swap A[i-1] with
} // a random element
public static void swap(int[] A, int p1, int p2) {
int temp = A[p1];
A[p1] = A[p2];
A[p2] = temp;
}
/** Randomly permute the values in array A */
static <E> void permute(E[] A) {
for (int i = A.length; i > 0; i--) // for each i
swap(A, i-1, DSutil.random(i)); // swap A[i-1] with
} // a random element
/** Initialize the random variable */
static private Random value = new Random(); // Hold the Random class object
/** Create a random number function from the standard Java Random
class. Turn it into a uniformly distributed value within the
range 0 to n-1 by taking the value mod n.
@param n The upper bound for the range.
@return A value in the range 0 to n-1.
*/
static int random(int n) {
return Math.abs(value.nextInt()) % n;
}
}
Text File:
CV06C1250B
MA06C1042A
MA06C1043A
SU04D1043B
SU04D1042B
CV06C1250A
CV06D1250B
HY09F3014A
KI04D1297A
Explanation / Answer
import java.util.Scanner;
class Task
{
String job;
int priority;
public Task(String job, int priority)
{
this.job = job;
this.priority = priority;
}
public String toString()
{
return "Job Name : "+ job +" Priority : "+ priority;
}
}
class PriorityQueue
{
private Task[] heap;
private int heapSize, capacity;
public PriorityQueue(int capacity)
{
this.capacity = capacity + 1;
heap = new Task[this.capacity];
heapSize = 0;
}
public void clear()
{
heap = new Task[capacity];
heapSize = 0;
}
public boolean isEmpty()
{
return heapSize == 0;
}
public boolean isFull()
{
return heapSize == capacity - 1;
}
public int size()
{
return heapSize;
}
public void insert(String job, int priority)
{
Task newJob = new Task(job, priority);
heap[++heapSize] = newJob;
int pos = heapSize;
while (pos != 1 && newJob.priority > heap[pos/2].priority)
{
heap[pos] = heap[pos/2];
pos /=2;
}
heap[pos] = newJob;
}
public Task remove()
{
int parent, child;
Task item, temp;
if (isEmpty() )
{
System.out.println("Heap is empty");
return null;
}
item = heap[1];
temp = heap[heapSize--];
parent = 1;
child = 2;
while (child <= heapSize)
{
if (child < heapSize && heap[child].priority < heap[child + 1].priority)
child++;
if (temp.priority >= heap[child].priority)
break;
heap[parent] = heap[child];
parent = child;
child *= 2;
}
heap[parent] = temp;
return item;
}
}
public class PriorityQueueTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Priority Queue Test ");
System.out.println("Enter size of priority queue ");
PriorityQueue pq = new PriorityQueue(scan.nextInt() );
char ch;
do
{
System.out.println(" Priority Queue Operations ");
System.out.println("1. insert");
System.out.println("2. remove");
System.out.println("3. check empty");
System.out.println("4. check full");
System.out.println("5. clear");
System.out.println("6. size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter job name and priority");
pq.insert(scan.next(), scan.nextInt() );
break;
case 2 :
System.out.println(" Job removed "+ pq.remove());
break;
case 3 :
System.out.println(" Empty Status : "+ pq.isEmpty() );
break;
case 4 :
System.out.println(" Full Status : "+ pq.isFull() );
break;
case 5 :
System.out.println(" Priority Queue Cleared");
pq.clear();
break;
case 6 :
System.out.println(" Size = "+ pq.size() );
break;
default :
System.out.println("Wrong Entry ");
break;
}
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.