A priority queue is a queue in which we insert an element at the back (enqueue) and remove an element from the front (dequeue). In addition, every element has a priority associated with it. The element with the highest priority shall be dequeued first. The Priority queue can be implemented with array or heap.

We have introduced why we use heap to implement priority queue. There are two ways to implement priority queue with heap. The first is to implement using iteration. The second is to use recursion. In this post, we are using recursive solution.

Part 1 – priority queue implementation with ordered array
Part 2 – priority queue implementation with unordered array
Part 3 – priority queue implementation with heap iterative solution
Part 4 – priority queue implementation with heap recursive solution

### Enqueue

First we 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 actual number of elements in the array. It starts from 0.

To enqueue, we put the new value at the end of the array. Then we move it up based on its value compared to its parent. If it’s value larger than its parent, it should be swapped with its parent. We call this process heap up.

## Doodle

### Dequeue

The dequeue operation is to remove the highest priority element from the array. When we remove the first element in the array, we 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, we compare its value with its children’s values, and switch with the child with the larger value. This process is called heap down.

Please note this implementation is using recursion. The time complexity is the same as iterative implementation O(h), h is the height of the heap. However, the space complexity has increased to O(h) for the call stack. So it is not as efficient as 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 highest index. A for loop is used to iterate through each element.