A max-priority queue implements a priority queue using a max-heap. There are many applications of max-priority queues, such as scheduling jobs on a shared computer where max-priority queue keeps track of the jobs to be performed and their relative priorities. When a job is finished or interrupted, the scheduler calls EXTRACT-MAX to select the highest-priority job from among those pending. INSERT helps scheduler add a new job to the queue. Assume that the functions of a max-heap priority queue are defined as follows:

INSERT(X) { Add element X to the end of the max-heap Increment the size of the max-heap by 1 Max-heapify the max-heap //As max-heap condition is probably violated after inserting X

}

EXTRACT-MAX() { Remove and print the root element from max-heap Move the last element at the end (leaf) of the heap to the root Decrement the size of the max-heap by 1 Max-heapify the max-heap //As max-heap condition is probably violated after extraction and moving }

where the MAX-HEAPIFY function can be found in our Heapsort lecture slides. Implement the max-heap algorithms above to demonstrate the execution of

INSERT(T)

EXTRACT-MAX()

back to back operations on the following max-heap. Please show your step by step work.

Note that EXTRACT-MAX() should execute on the resulting max-heap after INSERT(T) operation.