First, the difference between queue and priority queue
- Queue is a first-in-first-out (FIFO) data structure, corresponding to the queuing scene In life, the First person In line always passes First, In turn.
- A priority queue is a special queue. From the word “priority”, it can be seen that there is queue-jumping phenomenon. For example, when you queue up to get into a railway station, there will be some people who are in a hurry to jump the queue and pass the ticket check first. The priority queue contains at least two data structures for operations: INSERT, which inserts elements into the priority queue (enqueue); And deleteMin, which finds and deletes the smallest element in the priority queue.
Priority queue (heap) characteristics
-
Binary heap is often used to implement priority queue. In data structure, priority queue also refers to heap.
-
Two properties of a heap:
-
Structure: A heap is a binary tree that is completely filled except for the bottom layer, which is filled in from left to right. Such a tree is called a complete binary tree.
-
Heap ordering: Since we want to find the smallest element quickly, the smallest element should be at the root, and any node should be smaller than its descendants. This is the min-heap. If you are looking for the largest element, then the largest element should be at the root, and any node should be larger than its descendants, which is the max-heap.
Structural:
Complete the binary tree
It has been observed that a complete binary tree can be represented directly using an array without using other data structures. So we just need to pass in a size to build the structure of the priority queue (elements are compared using the compareTo method).
public class PriorityQueue<T extends Comparable<? super T>> {
public PriorityQueue(int capacity) {
currentSize = 0;
array = (T[]) new Comparable[capacity + 1];
}
}
Copy the code
For any element at position I in the array whose left son is at position 2i, the right son is at 2i+1, and the parent is at I /2 (rounded down). It is usually stored at subscript 1. The advantage of this is that it is easy to find the left, right, and parent nodes. If we start at 0, the left son is at 2i+1, the right son is at 2i+2, and the parent is at (I -1)/2 (round down).
Heap sequence:
We set up the minimum heap, that is, for every element X, the keyword in X’s parent is less than (or equal to) the keyword in X, except for the root node (which has no parent node).
As shown in the figure, only the left side is the heap, and the red nodes on the right violate heap orderliness. According to heap order, only constant O(1) is needed to find the smallest element.
Basic heap operations
- Insert
- Filter up: To insert element X, we create a hole in the next available position (otherwise it breaks the structure and is not a complete binary tree). If the element is inserted into the hole without breaking heap orderliness, the insertion is complete. Otherwise, the parent node is moved down to the hole, that is, the hole takes a step towards the root. Continue this process until X is inserted into the hole. This process is called upfiltration.
Figure 18 shows the process of insertion. A hole is established in the next available position (satisfying the structure). When it is found that the hole cannot be inserted directly, the parent node is moved down and the hole bubbles up. Continue this process until heap orderliness is satisfied. This implements the insertion of elements into the priority queue (heap).
- Java implementation filtering
/ * *
* Inserts into priority queues to maintain heap orderliness
*
* @paramX: inserted element
* /
public void insert(T x) {
if (null == x) {
return;
}
/ / capacity
if (currentSize == array.length - 1) {
enlargeArray(array.length * 2 + 1);
}
/ / filter
int hole = ++currentSize;
for (array[0] = x; x.compareTo(array[hole / 2]) < 0; hole /= 2) {
array[hole] = array[hole / 2];
}
array[hole] = x;
}
/ * *
* Capacity expansion method
*
* @paramNewSize: Indicates the capacity after expansion. The value is 2 times the original capacity plus 1
* /
private void enlargeArray(int newSize) {
T[] old = array;
array = (T[]) new Comparable[newSize];
System.arraycopy(old, 0, array, 0, old.length);
}
Copy the codeThe up-filtering process can be repeated using the swap operation, but if the X-up-filtering D layer is inserted, 3d assignments are required; We only need d+1 assignment this way.
If the inserted element is the new minimum and filters all the way up to the root, the insertion takes O(logN). But on average, the filtration stops earlier. It has been shown that sequential inserts require an average of 2.607 comparisons, so the average INSERT operation moves elements up 1.607 levels. The number of filters is only one less than the number of inserts.
- DeleteMin (delete minimum element)
- Down filter: Similar to up filter operation. Because we’re building the minimum heap, deleting the minimum is deleting the root node, which breaks the structure. Therefore, we create a hole at the root node. In order to satisfy the structure, the last element X in the heap must be moved to the appropriate position. If it can be directly put into the hole, the deletion is complete (generally not possible). Otherwise, the smaller of the left and right sons of the hole is moved to the hole, that is, the hole is moved down a layer. Keep doing this until X can be put into the hole. In this way, structural and heap ordering can be satisfied. This process is called downfiltering.
As shown in the figure: create a hole at the root and place the last element into the hole, the structure has been satisfied; The holes need to be moved down to a suitable position in order to satisfy the heap orderliness.
Note: A common error in heap implementations is to have only an even number of elements, i.e. a node with only one child. So we need to test the existence of the right son.
/ * *
* Delete the minimum element
* If the priority queue is empty, UnderflowException is thrown
*
* @return: Returns the minimum element
* /
public T deleteMin(a) {
if (isEmpty()) {
throw new UnderflowException();
}
T minItem = findMin();
array[1] = array[currentSize--];
percolateDown(1);
return minItem;
}
/ * *
* Lower filter method
*
* @paramHole: filters down from array subscript hole1
* /
private void percolateDown(int hole) {
int child;
T tmp = array[hole];
for (; hole * 2 <= currentSize; hole = child) {
/ / left son
child = hole * 2;
// Check whether the right son exists
if(child ! = currentSize &&
array[child + 1].compareTo(array[child]) < 0) {
child++;
}
if (array[child].compareTo(tmp) < 0) {
array[hole] = array[child];
} else {
break;
}
}
array[hole] = tmp;
}
Copy the codeThe worst time complexity of this operation is O(logN). On average, elements placed at the root almost filter down to the bottom layer (from the layer), so the average time complexity is O(logN).
Four,
Priority queues are often implemented using binary heaps. This article illustrates the two basic operations of binary heaps: insert and delete minima. Insert is executed at O(1) constant time and deleteMin is executed at O(logN). I believe you can look at the Java PriorityQueue source code. Today I’ve only covered the basic operations of binary heap, and I’ll talk about some additional operations and analysis next time. For example, how do you prove buildHeap is linear? And the application of priority queues.
Disclaimer: Both pictures and texts are original, if reproduced, please indicate the source. If there are mistakes, please help to point out, welcome to discuss; If feel ok, slightly a praise to support support.