A priority queue is a data structure that stores a set of entries where each entry has an associated key and total order of the keys are maintained.
Prioroty key can be either min priority queue which maintains keys in increasing order or max priority queue which maintains keys in decreasing order. In this chapter we will use min priority queue.
Priority queue can identify and remove the smallest key very fast and an item can be inserted at any time.
Operations:
Priority queue supports following operations:
Insert - which inserts item into the priority queue Min - which returns the item with smallest key RemoveMin - which removes the item with smallest key and returns it
Here is a few example of the operations:
[ | | | | | ] Insert(4) [4| | | | | ] Insert(8) [4|8| | | | ] Insert(2) [2|4|8| | | ] Min() -> returns 2 and the priority queue is unchanged [2|4|8| | | ] RemoveMin() -> returns 2 and remove it from the priority queue [4|8| | | | ]
Priority tree can be implemented using a Binary Heap.
Complete Binary Tree A binary tree in which every level of the three is full except the bottom row- which is filled from left to right. A complete binary tree has 1+log(n) levels where n is the number of items.
Fig: Complete Binary Tree
Binary heap
A binary heap is a complete binary tree where entries must satisfy heap order property, that is, no child element has a key less than its parents key. Multiple copies of same keys are allowed.
(1) / \ / \ (3) (4) / \ / \ / \ / \ (9) (11) (12) (17) / \ / \ / (13) (14) (15) (16) (12) Fig: Binary heap
Storing binary heap in a array
We do a level order traversal and on each level we traverse from left to right and store the keys sequentially in an array. If we do this for the binary heap from above figure we get following array.
[x|1|3|4|9|11|12|17|13|14|15|16|12|---]
Notice that we have kept the first cell unused.
In the array any item i's children is located at 2i and 2i+1 indexes and item i's parent is located at index |i/2|
For example item at index 4 is 9. Its children are 8th ad 9th item and the keys are 13 and 14. Its parent is at 2nd index which is 3. From the above binary heap tree figure you may verify that these are correct keys.
Operations
Min(): Return the entry at the root. In the array the root is stored at index 1. This is a constant time operation.
Insert(k): 1. Place k at the first open position on the bottom level from left. In the array put k at the first empty space at the end of existing item. 2. Bubble up the element untill the heap order property is satisfied. If the parent key is bigger than the items key swap the item with its parent and repeat this process as long as parent's key is bigger or the item is at the root.
Fig: Insert example
RemoveMin(): 1. Remove the entry at root 2. Take the last entry from bottom level of the tree feom left and put it at root position. In array this is the last item. 3. Bubble the root entry down through the heap- until the items key is smaller than both of its children's key swap with smaller child
Fig: Remove example
Worst case performsnce Theta(log n) Best case performance Theta(1)
Bottom up heap construction
If we are given an array of items and we need to create a heap, we can insert each item in the tree one by one which will take Theta(n log n) time or we can use bottom up heap construction technique to do it in Theta(n)
BottomUpHesp(itemArray): [ref:] 1. Make a complete binary tree without considering order. For a given array of items no operation is required. 2. For each nonleaf node starting from last one bubble the item down (swap with smaller child) until its key both of its children's key.
Fig: Bottom up heap construction example
