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.
