Question

Remarks: In all algorithm, always explain how and why they work. If not by proof, at least by a clear explanation. ALWAYS, analyze the running time complexity of your algorithms. In all algorithms, always try to get the fastest possible. A correct algorithm with a slow running time may not get full credit.

Do not write a program. Write pseudo-codes or explain in words

Question 1: Say that we want to maintain both a Queue and a Priority Queue. This means that when you do Enqueue you also add the item to the Priority Queue and when you do Dequeue you also remove the item from the Priority Queue. And vise-versa. Show how to do it.

Question 2:

1. Show how to implement a Queue by a Priority Queue. What is the run time per operation?

2. Show how to implement a Stack using Priority Queue. What is the run time per operation?

Question 3: Give a data structure that implements a Min-Heap and the command M ax(S) that returns the maximum in the heap. Try and make the last operation as fast as possible.

Question 4: Recall the problem in which you have k sorted array each of size n, which needs to make one single sorted array. Find another fast way to unite the arrays that does not use Priority Queue.

Question 5: Five an efficient data structure supporting the following operations. Insert(S, x), Delete−M ax(S), and Delete−1000 th(S) which deletes from H the 100 largest element in the structure. Assume that the number of elements is more than 100. Also assume that the numbers are pairwise distinct and so the 100"th largest element is well defined.

Answer 1

Ans 1.

Queue and Priority queue are the same but with one major difference i.e., the priority queue maintains/stores each enqueue operation as key and value pair such that the value with lowest priority is at the front (where dequeue operation takes place) and the value with highest priority is at rear (where enqueue operation takes place).

For example,

To enqueue in priority queue,

//priorityQueue is the PriorityQueue object

priorityQueue.put(1,"one") - here 1 is it's priority and "one" is the value

priorityQueue.put(2,"two")

if one dequeue from this priority queue, will get output as "one" and then"two" according to the priority.

For enqueueing in queue and priority queue,

i. Check if queue is full,

a. if full, return overflow.

b. else

- increment rear and insert data in queue

- start from the right end of the priority queue, if number is larger then shift the existing number/item to the right end of thr queue.

- Then insert the data and increment the count of that item by 1.

For dequeueing from queue and priority queue,

i. Check if queue is empty.

a. if empty, then return that queue is empty.

b. else

- increment front by 1 and return data stored in front previously i.e., before incrementing

- for priority queue, simply return the decremented count from the queue.

Ans 2.

// Queue using priority queue

The easiest way to create a priority queue is using the value of the number as it's priority.

So, here you will always be dequeuing the the value with lowest priority.

Enqueue and dequeue operation can be done as it is in priority queue neglecting its priority.

//Stack using priority queue

Stack has a LIFO (Last-In-First-Out) property different from queue, which has FIFO (First-In-First-Out) property.

i. Take a variable, ptr as 0.

ii. For push operation of stack,

a.increment ptr by 1. (this takes constant time)

b. Enqueue to the priority queue with (ptr,value/number) pair. (takes O(log(n)) time - priority queue operation)

iii. For pop operation of stack,

a.decrement ptr by 1. (takes constant time)

b. Use dequeue operation of priority queue. (takes O(log(n)) time - priority queue operation)

So, both the push and pop operation takes O(log n) time.

Ans 3.

Heap is itself a kind of data structure which consists of fixed or dynamic array.

Or in direct words, you can say that it is implemented using priority queue or binary tree.

A min heap is a complete binary tree where the root node is the smallest of all nodes or you can say that each internal node is smaller than or equal to the values of it's child node.

To get the maximum element in min-heap,

i. Assume, maxElement to be middle of heap (as it is array,finding middle element is O(1))

ii. Start a for loop from 1+(n/2) to n and set maxElement to maximum of previous maxElemnt and cuurent value of heap according to for loop.

iii. Finally, we have maximum of min-heap stored in maxElement variable.

Ans 4.

This can be implemented analogous to the merge sort algorithm (by using merge function from the merge sort algorithm).

Pseudo code for merging k sorted array of size n into a single sorted array:

i. For merging two arrays to obtain a single sorted array, one can use merge() function of merge sort as:

mergeArrays(int a1[], int a2[], int a3[])

here, a1, a2 are two arrays to be merged to obtain sorted a3.

Rest of the function remains same as that of merge() from merge sort.

For merging all these k arrays,

i. use recurssion with base conditions as:

a. if there is onle one array return the same array

b. else if there are two arrays call mergeArrays functions accordingly.

c. Recusively call,

mergekArrays from start index to mid index, and

mergekArrays from mid index to end index.

d. finally merge all the arrays to obtain the final single sorted array.

Ans 5.

Insert(S,x) and delete(Max(S)) is used in heap data structure, which is almost a complete binary tree.

To insert a node in heap:

i. Insert the element at the end.

ii. Then heapify that element which takes O(lg n) time.

To delete maximum element from heap:

i. find maximum element in heap as given in Ans 3.

ii. Replace the last element with root, and delete it.

iii. Heapify the root. (takes O(lg n) time)

To delete 100th largest element from the heap, first get the 100th largest element and then the same as given above to delete maximum element eith passing this element as argument to delete function.

To get 100th largest element:

i. store the minimum of root node and 2^100-1 (^ indicates the exponent)

ii. Start a for loop from i=1 to 100 and extract maximum element from heap.

After getting the 100th largest element, delete it as discussed earlier.

Note - Don't forget to heapify at last to satisfy the heap condition which takes O(lg n) time.