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.

Heap is a complete binary tree, A complete binary tree is a binary tree in which all levels are completely filled and all the nodes in the last level are as left as possible. Based on these characteristic, it can be represented as an array. Each node’s position in the tree is corresponding to the index in the array as following diagram.

The relationship between the nodes in the heap has following formulas:
parentPos = (pos-1)/2
left = 2*pos+1
right=2*pos+2

Meanwhile, heap should also meets this criteria: the parent’s key is larger than both children’s keys. The max value is stored in the root. If we read the value level by level from top to bottom, all elements are partially sorted. Based on this, we can use heap to implement priority queue.

Please note when we use max heap, the priority queue is a descending priority (ie the bigger the key, the higher the priority). If we want ascending priority, we can use min heap to implement.

There are two ways to implement priority queue with heap. The first is to implement using iteration. The second is to use recursion. This post is using the iterative 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

We declare three attributes: heap, length and maxSize. heap is an array. maxSize is the max length of the array. It is used to initialize 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 switched the position with its parent. We call this process heap up (or trickle up). The time complexity is O(h). h is the height of the heap, which is better than enqueue in ordered array implementation of priority queue O(n).

## Doodle

### Dequeue

The dequeue operation is to remove the highest priority element, which is the first one in the array. When we remove the first element in the array, we move the last element to the first position to fill out the empty spot. But this element’s value might be smaller than it children. 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 (or trickle down). The time complexity is O(h), which is better than dequeue in unordered array implementation of priority queue O(n).

## 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.