A priority queue is a queue in which we insert an element at the back (enqueue) and remove an element from the front (dequeue). The element with the highest priority shall be dequeued first. This priority queue implementation provides code to implement a priority queue using a heap using recursion, in which the time complexity of enqueue is O(logn), and the space complexity is O(logn).

Check out why we use a heap to implement a priority queue.

### Map of priority queue implementations

Part 4 – priority queue implementation with heap – recursive solution

### Enqueue

In the class, declare three attributes: heap, length, and maxSize. heap is an array to hold all elements in the priority queue. maxSize is the max size of the array. length is the actual number of elements in the array. It starts from 0.

To enqueue, you put the new value at the end of the array. Then you move it up based on its value compared to its parent. If its value is larger than its parent, it should be swapped with its parent. We call this process bubble up or heap up. The time complexity is O(logn).

## Doodle

### Dequeue

The dequeue operation is to remove the highest priority element from the array. When you remove the first element in the array, you move the last element to fill out the empty spot. But this element’s value might be smaller than its children’s. To correct this, you compare its value with its children’s values and switch with the child with the larger value. This process is called bubble down or heap down.

Please note this implementation is using recursion. The time complexity is the same as iterative implementation O(logn). However, the space complexity has increased to O(logn) for the call stack. So it is not as efficient as the iterative approach.

## Doodle

### Peek

Peek is to return the value of the highest priority element. Since the first one already has the largest value, this can be done by returning the first element in the array.

## Python

### Print

Print is to print all elements in the array, starting from the index 0 to the highest index. A for loop is used to iterate through each element.