CS211-Assignment 3 Priority Queue and Heapsort using Max-heaps Solved

The objective of this assignment is to implement Priority Queue and Heapsort using max-heaps.

 

Command-line argument:

Your program should receive a file (input file) as a command line argument. 

 

Input file 
The input file will be a text file where each line will be of any of the following format:

insert <number, maximum, extract-max, increase-key <index <number, sort, where <number represents any non-negative integer. 

 

The output must be in a file named ‘heap.txt’. Every line in the input file must have a corresponding output line in priority_queue.out. The details are given below.

 

Command
Meaning
Output
insert <number
Insert <number to the priority queue
<number inserted
maximum
Find the maximum in the priority queue
<maximum number /

<empty-line (if the priority queue is empty)
extract-max
Find and remove the maximum from the priority queue
<maximum number /

<empty-line (if the priority queue is empty)
increase-key <index <number
Make the key at <index as <number if <number is at least the current value at <index. ​Note that the index ranges from 0 to heap-size - 1
Key at <index changed to <number / <number is less than the current key at

<index
sort
Do a ​heapsort​ on the elements in the priority queue. Note that you don’t have to build a max-heap here. Further, the heap should not be disturbed. So, you may
Elements in the priority queue in ascending order. Two values are separated by a single space.
 
take a copy of the heap and do the heapsort on it.