CS 310 Priority Queues

Assignment Objective

Implement Priority Queues using (1) Dynamic Array, (2) AVL tree, (3) K-ary Min Heap and (4) Binomial Min Heap and compare their performances.

Tasks

• Implement PQ using Binary Min tree
• Implement PQ using K-ary Min Heap
• Implement PQ using Binomial Min Heap
• Complete README.txt and report performance comparisons

All four of these PQs must implement PriorityQueue interface defined in PriorityQueue.java that has the following methods.

//add the given value using the provided priority
public void enqueue(DataType value, PriorityType priority);

//remove the value with the highest priority (i.e. smallest priority value)
public DataType dequeue();

//return the value of the element with highest priority (i.e. smallest priority value)
public DataType peek();

//return the priority of the element with highest priority
//(i.e. smallest priority value)
public PriorityType peekPriority();

//remove everything in the priority queue
public void clear();

//merge two priority queues into one and return the merged priority queue
public PriorityQueue merge(PriorityQueue other);

//return the size of the given priority queue
public int size();

Examples

Using cs310pa3.java to test your code. The usage is:

> java cs310pa3
Usage: java cs310pa3 pq-type file
pq-type: binary kary binomial

We will use the following command to test your code:

> java cs310pa3 binary data/words.txt
[00] create two Priority queues of type: Binary min Heap
[01] read 466544 words from data/words.txt
[02] n=43420 m=21903
[03] adding 43420 words to PQ#1
[04] removing 21710 words from PQ#1
[05] adding 21903 words to PQ#2
[06] removing 10951 words from PQ#2
[07] mering PQ#1 and PQ#2 into PQ#3
[08] clearing PQ#1 and PQ#2
[09] sorting PQ#3:
(...)

The program in cs310pa3.java first

• Creates two PQs and
• Insert random words loaded from data/words.txt with random prioirties.
• Then delete half of the elements from both PQS before merge them.
• Finally, the merged PQ is sorted using heap sort.