5-1 Motivation: This project is to implement Priority Queue, using array or a co

Question

5-1 Motivation: This project is to implement Priority Queue, using array or a complete binary tree structure. Details about priority queue can be found from http://www.cse.cuhk.edu.hk/~taoyf/course/2100sum11/lec8.pdf

5-2 Requirements: You should name your Prority Queue class as PQ. The queue must be able to hold unlimited number of integers. It has two key operations: Push and Pop, which should have the time complexity of O(logn).

5-3 Files to turn in: You need to turn in four files: makefile, main.C, PQ.C, PQ.h. You should have a main.C that reads in or generates some integers, pushes them into the PQ one by one, and pops and prints them until the PQ is empty.

5-4 Grading The total points is 12, you will get full credit if you correctly implement it using tree structure, 6 points if you correctly implement it using array. No late turn in is acceptable, any late turn in will be given 0 point. Your code must be compilable on Linux/Unix, any code that cannot be compiled by g++ will automatically get ZERO point.

Explanation / Answer

import java.util.Scanner;

class Task
{
String job;
int priority;

// Constructor for initialization
public Task(String job, int priority)
{
this.job = job;
this.priority = priority;
}

public String toString()
{
return "Job Name : "+ job +" Priority : "+ priority;
}
}

/** Class PriorityQueue **/
class PQ
{
private Task[] heap;
private int heapSize, capacity;

// Constructor
public PQ(int capacity)
{
this.capacity = capacity + 1;
heap = new Task[this.capacity];
heapSize = 0;
}
/** function to clear **/
public void clear()
{
heap = new Task[capacity];
heapSize = 0;
}
/** function to check if empty **/
public boolean isEmpty()
{
return heapSize == 0;
}
/** function to check if full **/
public boolean isFull()
{
return heapSize == capacity - 1;
}
/** function to get Size **/
public int size()
{
return heapSize;
}
/** function to insert task **/
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;
}
/** function to remove task **/
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;
}
}

/** Class PriorityQueueTest **/
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 ");
PQ pq = new PQ(scan.nextInt() );

char ch;
/* Performing Priority Queue operations */
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

• Browse (All)
• Browse 5
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.