Priority Queue - Binary Heap
The priority queue is a fundamental data structure that supports access only to the minimum item. The classic implementation of the priority queue data structure is binary heap. Binary heap makes possible the insertion of new items and deletion of the minimum item in log worst-case time. Only an array is used and it is easy to implement. It has two properties: a structure property and an ordering property.
Tree is the only structure that gives dynamic logarithmic time bounds, so it is natural to organize the heap's data as a tree. Since we want the logarithmic bound to be a worst-case, the tree should be balanced.
The heap is a complete binary tree, allowing representation by a simple array and guaranteeing logarithmic depth.
Properties of a complete tree:
- Height of N nodes is at most ⌊ log N⌋. That is because a complete tree of height H has between 2H and 2H + 1 – 1 nodes.
- left and right links are not needed. The complete binary tree is represented by storing its level-order traversal in an array.
The parent is in position ⎣i/2⎦ , the left child is in position 2i, and the right child is in position 2i + 1. Every node except the root has a parent.
The heap-order priority is that, in a heap the parent is never lagers than the item in a node, so the parent should always be the minimum. This makes it easier to find the minimum quickly as the smallest element should always be at the root.
Heap order priority
This is a heap This is not a heap
Insertion in the heap is done by creating a hole at the next available location and after that we percolate it up until the new item can be placed in it, without violating the heap-order property.
Figure 1.1
On figure 1.1 we insert 14 in the tree, and the available location to put it is next to 32. 14 is smaller than 32 and 31, so it should be the parent of these two nodes. That is why a hole is made.
Figure 1.2
Later we can check that the heap property is not applied since 21 is still the parent node and it is NOT the smallest element. Thus, we need to insert 14 as parent and 21 in the place that 14 was before. Now all inserted elements do respect the property.
Insertion of elements takes constant time on average and logarithmic time in the worst case scenario. O(log N) is the time required to do the insertion, if the element we are inserting is the new minimum. That is because it will percolate up to the root.
deleteMin operation is managed as the insert operation. As mentioned before, finding the minimum is easy, but the hard part is to remove it. When the min element is deleted, a hole is created in the root. In this situation, the heap becomes one size smaller. Heap's structure property shows that the last node should be eliminated. This is represented on figure 1.3.
Figure 1.3
The best scenario would be if the last item could be places in the hole, but that is not always the case. From this phase, we continue the steps followed as insertion. The smallest element in the tree is 14, so it is inserted as a root. A hole is created and the smallest element should be placed there. Between 19 and 21 we insert 19, since 19 < 20. At the new hole item 26 is placed as it is smaller than 65.
Figure 1.4
Figure 1.5
For both worst case and average cases, deleteMin operation is logarithmic.
Below, using figure 2.1, are represented the steps that the build heap procedure follows.
Figure 2.1
As shown in figure 2.2, this tree doesn't respect the heap-order property. The left child of parent 1, 47, is not smaller than its children, 20 and 88. The same thing can be said for right child, 99, which is again not the smallest element.
Figure 2.2
On figure 2.3 are shown the steps to follow starting from the left child.
Firstly, 17 is placed as parent and 20 as its child. After that, we check that the node 47 is still not smaller than its children, thus we place 17 instead. After placing 47 in its place, we can check that there is another node (20) that is smaller than 47 and 61, so it is putted as a parent node.
Figure 2.3
The same procedure should be followed for the rest of the tree, by always checking if the parent node is smaller than other elements.
Figure 2.4
Above is the finished heap after applying the heap-order property