DinS Written on 2017/4/26
1. Visually, what is a priority queue(优先级队列)?
Priority queue has many versions of implementation. Here I’ll use complete binary heap(完全二叉堆) as an example. Leftist heap(左式堆) is also a well-known version.
Conceptually, think heap as a tree:
Practically, implement heap as a vector:
Priority queue is a specialized data structure used to get the top priority element, or in other words extreme values in an efficient way. It only maintains a partial order(偏序关系) so that it can outperform vector in this respect.
A word of caution: one heap can get maximum or minimum element, but can’t get both. We’ll see the reason later.
2. Properties of heap
(1) Call-by-priority: each element in heap has a key, or priority. Key is not the data we want, but a tag to mark the priority of data. In the picture above the numbers are keys, not data.
(2) What’s the difference between concept and practice?
Complete binary tree has specific relations with vector. The rule is as follows:
Given an rank i,
Parent(i) = (i-1) >> 1
leftChild(i) = 1 + (i<<1)
rightChild(i) = (1+i) << 1
provided that the child exists.
*Notice: << and >> are both operation on bits. <<1 means move the binary one bit left, which equals i*2. >>1 means move the binary one bit right, which equals ⌊ i/2 ⌋ (floor).
e.g. Given the rank 1 in vector with priority 3, the parent of rank 1 is rank (1-1)>>1 = 0 with priority 4. The left child of rank 1 is rank 1+(1<<1) = 3 with priority 1. The right child of rank 1 is rank (1+1)<<1 = 4 with priority 4. This is in accordance with the tree picture.
Using this relation we can reap both the benefit of tree and high-performance of vector.
(3) Heap Property(堆序性)
Throughout the heap any node must meeting the following requirement:
The priority of parent(i) >= the priority of i
You can check the tree picture to confirm this.
3. Access
From the Heap Property we can conclude that the root node must have top priority. Thus we can get the extreme value in O(1) time.
4. Insert and percolate up(上滤)
To insert a new node and make sure Heap Property is maintained, we must do the following steps:
(1) Insert the node/element to the rear of vector. This takes O(1) time.
(2) If Heap Property is maintained, we’re done. If not, we need to do percolate up.
(3) Percolate up: keep comparing current node and its parent. If the priority of current node is bigger than its parent, swap these two nodes. This procedure continues until the current node is smaller than its parent or the current node reaches root. The number of swapping operations can’t be bigger than the height of tree, and since it’s a complete binary tree, the height won’t be taller than ⌊ log2n ⌋.
In conclusion insertion only takes O(logn) time. This is the worst case scenario. In practice we can expect comparison times to be constant.
Pseudo codes:
| HeapInsert(heap, target)
| {
| insert_to_rear(heap, target)
| i = heap.size() – 1
| while (parentExist(i))
| {
| if (target <= parentNode(i))
| break
| else
| {
| swap(target, parentNode(i))
| i = parentRank(i)
| }
| }
| }
e.g. insert a new node with priority 5
First insert the new node to the rear.
Next compare the new node with its parent. Because 5 is bigger than 0, we need to swap.
Next repeat the same procedure. Since 5 is bigger than 4, swap.
Now than 5 has reached the root, there’s no need to percolate up again. Heap property is maintained. The top priority node has made its way to the top.
5. Delete and percolate down(下滤)
Deleting a node is similar to inserting a node.
(1) Delete the root node, which has the top priority, and replace the empty root with the last node e. This takes O(1) time.
(2) If Heap Property is maintained, we’re done. If not, we need to do percolate down.
(3) Keep comparing e with its two children. If e is the biggest we can stop. If not, swap it with the bigger child. This procedure may keeping going until e is at the bottom. For the same reason as percolate up, percolate down may take O(logn) time.
Pseudo codes:
| HeapDelete(heap)
| {
| deleteTopPriority()
| replaceRootWithLastNode()
| i = 0
| while(hasChildren(i))
| {
| if (Node(i)>= leftChild(i) && Node(i) >= rightChild(i))
| break
| else
| {
| swap(Node(i), bigger(leftChild(i), rightChild(i)))
| i = biggerRank(leftChild(i), rightChild(i))
| }
| }
| }
e.g. delete operations in heap
First we have this heap. 4 is to be deleted.
Second after deletion we replace the root with the last node 2.
Since Heap Property is broken, we need to percolate down the root. 2 is smaller than 3, so we need to swap it with 3.
Now that 2 is bigger than 1 and there’s no other child, Heap Property is restored. Done.
6. Heapification(建堆)
In many occasion we’re not building heap from scratch. We want to make a heap out of existing data. One way is to keeping inserting the data to a new heap. This works but takes O(nlogn) time. That’s unacceptable because using this time we can sort the whole data.
Another way is to use the Floyd heapify algorithm. It’s very easy; simply apply percolateDown() to every internal nodes from bottom to top. Why this works? At first you can think every single node as a heap of size 1. As we apply percolateDown() to each node, what we are doing is merging heaps to get bigger heaps. During this process Heap Property is maintained. Thus in the end we get a single big heap.
The time cost to each percolateDown() equals the height of current node i. Then the total time cost is
