Implement a priority queue

Posted: 6 Jun, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Ninja is given a task to implement a priority queue using Heap data structure. The Ninja is busying preparing for the tournament., So he asked for your help.

Your task is to use the class as shown in the comments in the code editor and complete the functions push(), pop(), getMaxElement() and isEmpty() to implement a priority queue.

Note:

There are four types of queries.  

Type 1: push( x ) push element ‘x’ into queue.

Type 2: pop( ) delete the largest element from the queue, if the queue is empty then do nothing.

Type 3: getMaxElement( ) return largest element , if queue is empty return -1;

Type 4: isEmpty( ) return ‘1’ if queue is empty, otherwise return ‘0’.
Input Format:
First-line will contain ‘Q’, the number of queries. Then the queries follow.

Each query has at least one integer representing the type of query. In the case of type 1, you have space-separated integer X.
Output Format:
For each query of type 3 output an integer value in the newline.
Note:
You have to complete the function only.
Constraints:
1 <= Q <= 100
1 <= X <= 10 ^ 9

Time limit: 1 sec.
Approach 1

 

  1. Since the heap is maintained in the form of a complete binary tree, the heap can be easily represented in the form of an array.
  2. To keep the tree complete and shallow, while inserting a new element insert it in the leftmost vacant position in the last level i.e., at the end of our array, and perform some operation to maintain the property of the heap.
  3. Similarly, for deleting the maximum element, swap the root with the last leaf at the last level i.e, the last element of the array, and perform some operation to maintain the property of the heap.
  4. And to get the maximum element, return the first element of the heap (property of max Heap ).

 

  • ‘moveUp’ operation while inserting a new element:

While inserting a new element in the queue, we append a new element to the last of the heap array to maintain the heap property (completely tree). But after inserting the new element to the last, the other heap property may be violated ( root element should be greater than child element ), so apply the move up operation( Swap the incorrectly placed node with its parent until the heap property is satisfied ) to maintain the max heap property ( root element is greater than child element ).

 

  • ‘MoveDown’ operation while deleting the maximum element:

For deleting the maximum element we swap the last element from the heap with the first element from the heap and decrease the size of the heap by one.

But after swapping, heap property may be violated ( root element is greater than the child ). So to maintain that we apply move down operation (the algorithm is described below ) on the heap.

 

Algorithm :

 

'moveUp' operation on current node:

  • Get the parent node of the current node.
  • If a parent node exists (index greater equal to zero), then compare the parent node with the current node
    • If the parent node is lesser than the current node then swap and make the parent node as the current node and repeat step 1.
    • Else done

 

push ():

  • Increment the size of the heap by one.
  • Append the new element to the last of the heap
  • Now apply move up operation on the last element (as discussed above) to maintain the heap property.

 

'moveDown' operation on index ‘idx’:

 

  • Let's take the variable ‘greaterIdx’. Initialize it to ‘idx’.
  • Get left child index in variable ‘leftIdx’ and right child index in variable ‘rightIdx’
  • If ‘leftIdx’ is less than than the size of the heap and the element at ‘leftIdx’ is greater than the element at ‘greterIdx’ then assign ‘greterIdx’ equal to ‘leftIdx’.
  • If ‘rightIdx’ is less than than the size of the heap and the element at ‘rightIdx’ is greater than the element at ‘greterIdx’ then assign ‘greterIdx’ equal to ‘leftIdx’.
  • If ‘greaterIdx’ is not equal to ‘idx’ then swap element at ‘greaterIdx’ with the element at ‘idx’ and repeat step 1 at for element at index greaterIdx
  • Otherwise done.

 

pop ():

  • If the size of the heap is negative then do nothing
  • else swap the first element of the heap with the last element of heap.
  • Decrease the size of the heap by one.
  • Apply move-down operation (as discussed above) on the first element of the heap to maintain the heap property.


 

getMaxElement ():

  • If the size of the heap is equal to ‘ -1’ then return -1
  • otherwise, return the first element from the heap.


 

isEmpty():

  • If the size of the heap is equal to ‘ -1’ then return 1
  • Else return 0


 

Try Problem