CS2092D Assignment #5 Solution

QUESTIONS

1. Write a program that uses the Heap-Sort algorithm for sorting a given input sequence of integers present in an array A in non-decreasing order and prints the number of comparisons performed during sorting. Your program must contain the following functions: (the notation A[i..j] denotes the sub-array of A, contained within the ith and jth indices, both inclusive).
• A recursive function Max-Heapify(A,i) that takes as input an array A and lets the value at A[i] “float down” in the max-heap so that the subtree rooted at index i obeys the max-heap property.
• A function Build-Max-Heap(A) that takes as input an array A and build a max-heap on the input array A[1...n] where n is equal to A.length.
• A function Heapsort(A) that takes as input an array A and sorts an array A in place.
Input format:
• The first line of the input contains an integer n ∈ [0,105], the size of the array A.
• The second line lists the n elements in A, as space-separated integers in the range [−103,103].
Output Format:
• The first line of the output contains the elements of A in sorted order, separated by space.
• The second line of the output contains the number of comparisons performed during sorting.
Note:
The number of comparisons made by Heap-Sort is highly dependent on its implementation. As such, we will be considering the number of comparisons as per the algorithm given in CLRS.
Sample Input:
8
98 67 56 45 43 23 20 12
Sample Output:
12 20 23 43 45 56 67 98
24
• Main() - repeatedly reads a character ‘i’, ‘e’, ‘m ’, ‘d’ or ‘s’ from the terminal and calls the sub-functions appropriately until character ‘s’ is entered.
• Min-Heap-Insert(Q,k) - A function that inserts a new element with priority value k into the priority queue Q.
• Heap-Extract-Min(Q) - A function that takes as input a priority queue Q, removes and prints the element with the lowest priority. If the priority queue is empty, print −1.
• Heap-Minimum(Q) - A function that takes as input a priority queue Q, prints the element with the lowest priority without actually removing it from the priority queue. If the priority queue is empty, print −1.
Input format:
• First line contains a character from ‘i’, ‘e’, ‘m’, ‘d’, ‘s’ followed by at most two integers. The integers, if given, are in the range [1,106].
• Character ‘i’ is to insert the next integer, from the input into the priority queue. Character ‘i’ and integer are separated by space.
• Character ‘e’ is to remove and print the lowest key from the priority queue Q.
• Character ‘m’ is to print the lowest key from the priority queue Q without actually removing it.
• Character ‘d’ is to decrease the priority of an element in the priority queue. In this case, character ‘d’ is followed by two more integers, each separated by space. After this operation, the value at the position of first integer is decreased to the second integer.
• The character ‘s’ is to ‘stop’ the program.
Output Format:
• The output (if any) of each command should be printed on a separate line.
• For option ‘e’, remove and print the lowest key from the priority queue. If the priority queue is empty, then print −1.
• For option ‘m’, print the lowest key in the priority queue. If the priority queue is empty, then print −1.
Note:
In CLRS, Max-Priority Queue is discussed. CLRS also give an idea about how to implement Min-Priority Queue.
Sample Input :
i 100 i 110 i 95 e e i 120 e i 30
m
d 0 25m
e
e e s
Sample Output:
95
100
110
30
25
25
120 -1
Write a menu driven program to implement the above scenario as a Patient Scheduling Application, using a Priority Queue, Q (implemented as heap). Implement the following operations:
• Main() - repeatedly reads a character ‘i’, ‘e’, ‘m ’, ‘c’, ‘d’ or ‘s’ from the terminal and calls the sub-functions appropriately until character ‘s’ is entered.
• Insert-Patient(Q, k) - Inserts a new patient with token number k into the Queue Q.
• Extract-Next-Patient(Q) - Get the token number of the patient to be treated next and remove his/her priority from the queue.
• Get-Next-Patient(Q) - Get the token number of the patient to be treated next, from the Queue Q without removing it.
• Change-Token-Number(Q, k, x) - Change the token number of a patient from old value k to new value x in Queue Q. Assume that token number k is present in the Queue and x is lower than the current token number k.
• Display-Queue(Q) - Display all patients’ token numbers in the Queue Q in the order of their treatment (patient with lowest token number is treated first) without changing the queue.
Input format:
• The first line of the input contains a character from ‘i’, ‘e’, ‘m’, ‘c’, ‘d’, ‘s’ followed by at most two integers. The integers, if given, are in the range [1,106].
• Character ‘i’ is to insert the next integer, from the input into the Queue. Character ‘i’ and integer are separated by space.
• Character ‘e’ is to remove and print the patient with lowest token number from the Queue Q.
• Character ‘m’ is to print the patient with lowest token number from the Queue Q without removing it.
• Character ‘c’ is to change the token number of a patient in the Queue. In this case, character ‘c’ is followed by two more integers, each separated by space. After this operation, the patient’s token number with first integer is decreased to the second integer.
• The character ‘d’ is to display all patients’ token numbers in the Queue in the order of their treatment (Patient with lowest token number is treated first) without changing the queue.
• The character ‘s’ is to ‘stop’ the program.
Output Format:
• The output (if any) of each command should be printed on a separate line.
• For option ‘e’, remove and print the patient with lowest token number from the priority queue. If the Queue is empty, then print −1.
• For option ‘m’, print the patient with lowest token number in the Queue. If the Queue is empty, then print −1.
• For option ‘d’, display all patients’ token numbers in the Queue in the order in which they will get treatment (patient with lowest token number is treated first). Each token number should be separated by space.
Sample Input :
i 2 i 15 i 5 e i 4
m c 5 1 d e e e e s
Sample Output:
2
4
1 4 15
1
4
15
-1