Question

For each algorithm, always explain how and why they work. If not by a proof, at least by a clear explanation. ALWAYS, analyze the running time complexity of your algorithms. Do not write a program. Write pseudo codes or explain in words

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

Q3: (a)Show how to implement a Queue by a Priority Queue. What is the run time per operation?

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

Answer 1

Solution 1: There are many ways of implementing a heap tree in the memory and one such way is to use the linked lists to perform the operations over the binary heap but the complexity of one such method is very high as you would have to maintain a lot of pointers in the memory to not just traverse the elements of the heap but to implement the algorithms as well. On the other hand, arrays can also be used for the implementation of the same, and the complexity in that is much less as compared to that using the linked lists this is because of the fact that the space complexity of this solution is much less as compared to the space complexity of the solution using the linked lists.

So if you want to get the minimum element from the min-heap then its always going to cost you O(1) as the minimum element is always present at the top of the tree or the first element of the array. The extraction of the minimum element would take O(logN) of time as once the key is removed, the heap needs to be heapified or balanced to its original state as the swappings have to be carried out and other movements have to be performed too and the same is the complexity for the deletion of the elements from the tree. The insertion of the elements into the tree may also take O(logN) of time as the insertion of a new node may violate the principles of the heap tree and hence it has to be heapified after the insertion.

See, if you are trying to find the maximum element from a max heap then you can find it in O(1) of time as it is present on the top of the tree but if you are trying to find the maximum in a min tree then you may have to traverse through all the levels of the tree in order to get the maximum elements present in the tree and in that worst case the time complexity of the algorithm is actually O(logN), where N is the number of nodes present within the tree.

Solution 2: A priority queue is a data structure that can be used for storage as well as the retrieval of the data elements on the basis of their priorities. An element with a higher priority would be dequeued first than an element with a lower priority. As far as the implementation of a queue is concerned using the priority queue, you must understand that when you are implementing a priority queue then you are already implementing a queue and the arrays can be used for implementing them. In order to get the element with the highest priority, the time taken by the algorithm in the worst-case would be O(n) where n is the number of elements present within the queue. The same amount of time would be required to delete the element with the highest priority in O(n) of time in the worst-case scenario.

There is one way that you can implement the queue using the priority queue and that is by sorting the elements present in the priority queue by their priority but this would take additional O(NlogN) of time for any sorting algorithm and then you can implement the simple enqueue and dequeue operations over the elements in a linear time.

Solution 3: A stack can be implemented using the priority queue by keeping track of the count that determines when the element was actually pushed into the stack. On the basis of this count, the priority of the elements within the priority queue can be decided. So basically you will have to use the key-value pairs for this implementation as the first element always serving the value and the first element serving as the key. In order to traverse and model this queue you can use the heap data structure and hence the traversal of the elements and all other operations would only take O(logN) amount of time even in the worst-case scenario for the push and pop operations given the fact that the elements are pushed and popped in a first-in-first-out manner, and hence it would be the most efficient solution to this problem.

Here's the solution to your question, please provide it a 100% rating. Thanks for asking and happy learning!!