Priority Queues
(Max) Priority Queue = Max-In-First-Out
![](/2020/04/14/ds4/max_priority_queues.png)
1. Basic Operations
insert(value,priority)
deleteMax()
update(value,priority)
isEmpty()
2. Naïve implementation: Array
Store in an array, ordered by priority (the highest at the end):
insert(value, priority)
- find the position where to store the element, shift to the right the elements starting from that position1. deleteMax()
- return the last stored element.
3. Better implementation: Binary Heaps
3.1 Definition
Invariants of heap trees are as follows:
- The priority of every node is higher than (or equal to) that of its children.
- All levels are completely filled, except possibly the last one, which is partially filled from the left.
![](/2020/04/14/ds4/binary_heap.png)
3.2 Insertion
Insert the value at the end of the last level and then keep bubbling it up as long as it is larger than its parent.
Inserting p
to a heap which already has n
elements stored in it (pseudocode):
1 | void insert(int p, int[] heap, int n){ |
3.3 Delete Max
- Make the last node in the last level the new root.
- Then bubble down: keep swapping it with the higher priority child as long as any of its children has a higher priority.
![](/2020/04/14/ds4/delete_max.png)
pseudocode:
1 | int deleteMax(int[] heap, int n){ |
3.4 Storing heap trees in arrays
![](/2020/04/14/ds4/store_ht_in_arrays.png)
If we start counting from 1.
![](/2020/04/14/ds4/ht_arr.png)
or
For a node stored on position i
.
- its left child is on position
2*i
. - its right child is on position
2*i + 1
. - its parent is on position
i div 2
.
3.5 Heapify
Method 1:
Can insert entry by entry and bubble up each time, total
Method 2:
Simply fill the array and bubble down each entry. This is
1 | void heapify(int[] arr, int n){ |