PriorityQueue.java
IndexMinPQ.java
Priority Queue is the most important data structure. Our survival instinct kept us asking what is the best choice for the current situation. Priority queue organize a collection of things, so that we can find the extreme value. We need to be able to add elements into the collection, we should be able to remove the extreme value from the collection.
In order to achieve the goal, there are many approaches. Let's take a look at two extremes.
The first approach, let's call it eager approach. We always keep the collection in a perfect ordered array, so when we need to give the extreme value, it is the first element. It takes no time at delivery time. However, how are you gonna to keep this perfect collection all the time? It has to be very costly. For example, if you want to add a new element into the middle of the array, you have to move half of the array elements to the next position, in order to empty a new slot for the new element. The cost is proportional to the size of the collection N. If we have a million elements to organize, each adds on cost is half million on average.
 |
| storage slots |
The second approach, on the other hand, is called lazy approach. We just need a bag to hold the things without order. Whenever you need to add a new element, you simply have to toss it into the bag, it cost little to do that. However, at delivery time, how are you gonna to give me the extreme value? You have to pour out the collections of things to the floor, read through each one of them in order to find the max one. Again, the cost is proportional to the size of the collection N.
 |
| a bag of things |
Both eager approach and lazy approach has actions proportional to N, which won't be very practical for large collections. All we are asking for is an approach that has reasonable maintenance cost and reasonable delivery cost.
 |
| electric pole |
If we look around, the natural tree is the expert of handling materials. If we compare an electrical pole with a tree with the same height. The tree have much more materials than the electrical pole. The reason is the tree have branches. However, gravity also put priority on the tree, force the root (the position that is most likely to break) to have the biggest diameter. The electrical pole has biggest diameter at the root and getting smaller upward. The tree has the same property, just not perfect -- you generally find smaller size upward, but you can not say the same if comparing across the branches.
 |
| natural tree with branches |
Now let's use 2 definitions to extract the 2 successful factors of tree on handling materials under the constraint of gravity.
Definition 1: Binary tree. A tree whose elements have at most 2 children is called a binary tree.
Natural tree has many branches, we only want the essence of branching, we start from the simplest case, 2 branches.
Definition 2: heap order. The value of each node is smaller than or equal to the value of its parent.
A heap ordered binary tree extracted the essence of a natural tree, this is the priority queue approach we are looking for. The extreme value is at the root.
Now, let's calculate the cost of absorbing a new element. We can add the new element at the tip of the heap ordered binary tree. The new element might break the heap order -- in that case, the parent node is smaller than the new node. We can restore the heap order by exchanging the new node with its parent. Now the element swim up (imagine the root system in the soil) to a new position, and get a new parent node. If the new parent is still smaller, we exchange them. We keep swim up the new element to higher position until the parent node at that position is bigger. Now the heap order is restored, the tree just absorbed a new element. At worst scenario, the new element has to be swim up from the tip to the root. The total number of exchange is proportional to the height of the tree lgN instead of the size of the elements N. The tree's height won't be tall for N element, because at each level of branch, the nodes doubles, some math tells us the height for an N node binary tree is lgN. If we have a million element, the height of the tree is 20. This is a huge difference. It cost eager approach a million move to restore the perfect order, it only cost priority queue 20 to restore the semi-perfect order.
 |
| add element and swim up |
It cost priority queue little to absorb new materials, how expensive for the priority to deliver the extreme value? Quick answer is it cost nothing, the extreme value is at the root. Wait a second, now the root is taken away, the tree is dead, how are you gonna to give me the next extreme value? We have to fix the tree after delivering the extreme value. Fixing the tree won't be costly. We remove the root, then put the smallest element from the tip to the root. Of course the heap order is broken by this temp root node, we can fix it. Start from root, we can exchange the element with the bigger one of its two children. At the new position, if there are bigger children, we keep exchange the parent and child node. We keep sink that element down to lower positions until it reaches a position with both children smaller. Now the dead tree is fixed. At worst scenario, we have to sink the element from root to the tip, the cost again is proportional to the height of the tree lgN.
 |
| delecte max and sink down |
Now we have build the conceptual tool to handle priority queue, lets build a mathematical model to future realize it.
We can use array to model the priority queue. The array index maps to the binary tree node. The parent/child relationship is established by the 2 formulas, for current index i:
- the parent node's index is i/2.
- the left child's index is i*2, the right child's index is i*2 + 1.
There are two small maths tricks here.
- 3/2 = 1 and 2/2 = 1, computer handles integer dividing by round at the floor, both index 2 and 3 have common parent 1.
- we leave index 0 unused, 0/2 and 0*2 both get nowhere, this point can not grow. We put tree root at index 1, the next branches have 2, 3, then next branches have 4, 5, 6, 7...
 |
| heap ordered binary tree represented with array |
With this math model, computer can change the ideal of priority queue into reality.
<Prev Next>
