Priority Queue And Heap

When we need to find the minimum/ maximum element among a collection of elements. We can do this with the help of Priority Queue ADT.

Priority queue ADT is a data structure that supports the operations Insert and DeleteMin (which returns and removes the minimum set of element) or DeleteMax (which returns and removes the maximum set of element).

An example application of a priority queue is job scheduling, which is prioritized instead of serving in first come first serve. Or consider a situation where you want top 10 elements.

Priority Queue ADT 

The following operations make priority queues an ADT.

Main Priority Queues Operations 

A priority queue is a container of elements, each having an associated key.

• Insert (key, data): Inserts data with key to the priority queue. Elements are ordered based on key. 
• DeleteMin/ DeleteMax: Remove and return the element with the smallest/ largest key. 
• GetMinimum/ GetMaximum: Return the element with the smallest/ largest key without deleting it.

Auxiliary Priority Queues Operations

• kth - Smallest/ kth – Largest: Returns the kth -Smallest/ kth –Largest key in priority queue. 
• Size: Returns number of elements in priority queue. 
• Heap Sort: Sorts the elements in the priority queue based on priority (key).

Priority Queue Applications(to be done)

Priority queues have many applications - a few of them are listed below:

• Data compression: Huffman Coding algorithm 
• Shortest path algorithms: Dijkstra’s algorithm 
• Minimum spanning tree algorithms: Prim’s algorithm 
• Event-driven simulation: customers in a line 
• Selection problem: Finding kth- smallest element

Priority Queue Implementations

• Unordered Array Implementation
• Unordered List Implementation
• Ordered Array Implementation
• Ordered List Implementation
• Binary Search Trees Implementation
• Balanced Binary Search Trees Implementation
• Binary Heap Implementation

Problems:

1. Is there a min-heap/ max-heap with seven distinct elements so that the inorder traversal of it gives the elements in sorted order?
   Since a heap must be either a min-heap or a max-heap, the root will hold the smallest element or the largest. An inorder traversal will visit the root of the tree as its second step, which is not the appropriate place if the tree’s root contains the smallest or largest element.
2. Given a min-heap, give an algorithm for finding the maximum element.
   leaf nodes start from count+1/2 in heap. we have to start from i = count+1/2
3. Give an algorithm for deleting an arbitrary element from min heap.
   Time Complexity = Time for finding the element + Time for deleting an element = O( n) + O (logn) ≈ O( n). // Time for searching is dominated.
4. Give an algorithm for deleting the ith indexed element in a given min-heap.