- What is a Priority Queue?
- What is a Heap?
- When and where is a PQ used?
- Complexity PQ with binary heap
- Turning Min PQ into Max PQ
- Adding Elements to Binary Heap
- Removing Elements From a Binary Heap
What is a Priority Queue?
A priority queue is an Abstract Data Type(ADT) that operates similar to normal queue except that each element has certain priority. The priority of the elements in the priority queue determine the order in which elements are removed from the PQ.
NOTE: Priority Queue only supports comparable data, meaning the data inserted into the priority queue must be able to be ordered in some way either from least to the greatest or the greatest to the least. This is so that we are able to assign relative priority to each element.
Example
poll() means remove the highest priority element in priority queue.
What is a Heap?
A heap is a tree base DS that satisfies the heap invariant (also called heap property): If A is a parent node of B then A is ordered with respect to B for all nodes A, B in the heap.
When and where is a PQ used?
- Used in certain implmentations of Dijkstra's Shortest Path algorithm.
- Anytime you need th dynamically fetch the
next bestornext worstalgorithm. - Used in a Huffman coding(which is often used for lossless data compression)
- Best First Search(BFS) algorithm such as A* use PQs to continuously grab the next most promising node.
- Used by Minimum Spanning Tree(MST) algorithms.
Complexity PQ with binary heap
| Action | Complexity |
|---|---|
| Binary Heap construction | $O(n)$ |
| Polling | $O(log(n))$ |
| Peeking | $O(1)$ |
| Adding | $O(log(n))$ |
| Naive Removing | $O(n)$ |
| Advanced removing with help from a hash table * |
$O(log(n))$ |
| Naive contains | $O(n)$ |
| Contains check with help of a hash table |
$O(1)$ |
| Removing | $O(n)$ |
Using a hash table to help optimize these operations does take up linear space and also adds some overhead to the binary heap implementation.
Turning Min PQ into Max PQ
Often the standard library of most programming languages only provide a min PQ which sorts by smallest elements first, but sometimes we need a Max PQ.
Since elements in a priority queue are comparable they implement some sort of comparable interface which we can simply negate to achieve a Max heap.
Let $x, y$ be numbers in the PQ. For min PQ if $x<=y$ then $x$ comes out of the PQ before $y$, so the negation of this is if $x>=y$ then $y$ comes out before $x$.
An alternative method for numbers is to negate th numbers as you insert them into the PQ and negate them again when they are taken out. This has the same effect as negating the comparator.
Suppose lex is a comparator for strings which sorts strings in lexicographic order (the default in most programming languages). Then let nlex be the negation of lex, and also let s1, s2 be a string
/* normal */
lex(s1, s2) = -1 if s1 < s2
lex(s1, s2) = 0 if s1 = s2
lex(s1, s2) = +1 if s1 > s2
/* negate */
nlex(s1, s2) = -(-1) = +1 if s1 < s2
nlex(s1, s2) = 0 = 0 if s1 = s2
nlex(s1, s2) = -(+1) = -1 if s1 > s2
Example:
Adding Elements to Binary Heap
Ways of Implementing a priority Queue
Priority queues are usually implemented with heaps since this gives them the best possible time complexity.
The Priority Queue(PQ) is an Abstract Data Type, hence heaps are not eh only way to implements PQs. As an example, we could use an unsorted list but this would not give us the best possible time complexity.
Priority Queue With Binary Heap
There are many types of heaps we could use to implement a priority queue including:
- Binary Heap
- Fibonacci Heap
- Binomial Heap
- Pairing Heap ...
Binary Heap
A binary heap is a binary tree that supports the heap invariant. In a binary tree every node has exactly to children.
A complete binary tree is a tree in which at every level, except possibly the last is completely filled and all the nodes are as far left as possible.
Each parent node comes with two children nodes, if not showed means null.
Binary Heap Representation
Visualize the relationship between index and value of binary heap.
Add Elements to Binary Heap
Add element to binary tree starts from left to right, if the inserted values which violated heap invariants, then keep comparing value with parent node and switching until it is valid.
Removing Elements From a Binary Heap
Step:
- Find the target node.
- Swap Target node with the last node of tree.
- Now we perhaps violated the heap invariants.
- Do bubble up till the heap invariants satisfied.
Bubble up: Swap with the parent node if not satisfy the heap invariants.
Bubble down: Swap with the smaller children nodes, if tie, then swap with the left one.
Removing Elements From Binary Heap in O(log(n))
The inefficiency of the removal algorithm comes from the fact thant we have to perform a linear search to find out where an element is indexed at. What if instead we did a lookup using a Hashtable to find out where a node is indexed at?
A hashtable provides a constant time lookup and update for a mapping from a key(the node value) to a value (the index).
Caveat: What if there are two or more nodes with the same value? What problems would that cause?
Dealing with the multiple value problem
Instead of mapping one value to one position we will map one value to multiple positions. We can maintain a Set or Tree Set of indexes for which a particular node value(key) maps to.
Question: If we want to remove a repeated node in our heap, which node do we remove and does it matter which one we pick?
Answer: No it doesn't matter which node we remove as long as we satisfy the heap invariant in the end.