In data structure, queue can correspond to the queuing phenomenon in our life, like buying breakfast queuing, on the bus queuing and so on. But there are some cases, we have to prioritize certain elements, for example: on the bus, although in the queue, or to prioritize the old, young, sick, disabled and pregnant first on the bus; when more than one computer to the printer to send a print request, a computer to print 100 pages, while the other computers are a single page of the print, at this time a more reasonable approach to prioritize the printing of a single page of requests, and then finally print a 100-page request. Although we all aspire to fairness, in the queue is also concerned about first-come-first-served, but in some special circumstances, or to allow the phenomenon of congestion. That's what we're going to tell you about today - thepriority queue。
Priority queue is also a queue, then the most basic two operations must have, that is, into the queue and out of the queue operation. We can think of several simple implementation methods, such as a simple chain table, in the queue when the last element added to the chain table, then out of the queue should be traversed throughout the chain table to find the smallest element, which is obviously not a good program. Or we directly use the AVL balanced binary tree, the smallest element is the leftmost child node, it is easy to find, but in the process of queue and out of the queue, involves the addition and deletion of nodes, then we have to rotate the tree to maintain the balance of the tree, which spends a lot of additional overhead. So is there a relatively cheaper solution? This isbinary pile (math)of the program.
binary pile (math)
It is fairly common for priority queue implementations to use a binary heap, which is a binary tree, but a binary tree with the requirement that thecomplete binary tree (math.)A complete binary tree is a tree whose nodes are arranged from top to bottom and cannot be separated by nodes. A complete binary tree is a tree whose nodes are arranged from top to bottom, left to right, and with no empty nodes in between. Let's look at the two examples in the figure below:
In the left figure, the J nodes are not arranged in order from left to right, so it is not a complete binary tree, while in the right figure, it satisfies the characteristics of a complete binary tree and is a complete binary tree.
A binary heap has even properties, a structural property and a heap order property. Let's look at the structural properties, the heap is a completely binary tree, is very regular. We can directly use the array to represent the binary heap, instead of using the structure of the chain, look at the figure below:
The 0th element in the array we leave empty, the 1st element is the root node, and the order after that is to follow the order of the complete binary tree. Through observation, we are surprised to find the following pattern, the ith element of the array is the position of the left child node is 2i, the position of the right child node is 2i + 1, the position of the parent node is i/2 (except the root node). We can use the structure of an array to represent a tree instead of using the structure of a chain, which makes it very simple to traverse the tree. However, there is a problem with the array structure in that the length of the array needs to be estimated in advance, and then we have to expand the array as it grows. This is the nature of the structure of a binary heap, which we can represent as an array.
Next we look at the heap order property, since we find the smallest element quickly, then the smallest element we want to put on the root node. Similarly, we consider any subtree is also a binary heap, then the smallest element in the subtree should be at the root node of the subtree. Then that means any node should be less than its descendant node. So the heap order property of a binary heap is that for any node in a binary heap, its parent node should be less than or equal to that node. Let's look at the following two examples:
The parent of node 6 in the left diagram is 21, which is less than 6 and does not satisfy the heap order property, so the left diagram is not a binary heap. The right figure satisfies the heap order property and is a binary heap.
stick
When we insert a new element into the binary heap, in order to meet the nature of the binary heap from top to bottom, from left to right, we first determine the location of the inserted element, and then compared with the position of the parent node, if greater than the parent node, then it is to meet the nature of the binary heap, direct insertion on it; if not, then you need to exchange the position of the two elements, after the exchange of the parent node and then go to the parent node to make comparisons, and so on. has been recursive until the nature of the binary heap to meet, or exchanged to the root node, is the smallest element in the binary heap. Also using the above example, let's say we want to insert a new element 14.
Since 14 is less than 21, it needs to continue to adjust upwards, the
When adjusted to this position, the properties of a binary heap are satisfied and we insert 14. Such a whole process is doneultrafiltration. Below we write a program to implement this process.
/**
* binary pile (math)
* @param <T>
*/
public class BinaryHeap<T extends Comparable<T>> {
private static final int DEFAULT_CAPACITY = 10;
private int currentSize;
private T[] array;
public BinaryHeap() {
this(DEFAULT_CAPACITY);
}
@SuppressWarnings("unchecked")
public BinaryHeap(int defaultCapacity) {
= 0;
= (T[])new Comparable[defaultCapacity];
}
/**
* binary pile (math)是否为空
* @return
*/
public boolean isEmpty() {
return == 0;
}
/**
* 使binary pile (math)为空
*/
@SuppressWarnings("unchecked")
public void makeEmpty() {
= 0;
= (T[])new Comparable[DEFAULT_CAPACITY];
}
/**
* Extended Arrays
* @param newSize Extended Arrays大小
*/
@SuppressWarnings("unchecked")
private void enlargeArray(int newSize) {
if (newSize < ) {
throw new RuntimeException("Extended Arrays小于原始数组");
}
T[] tmpArray = (T[])new Comparable[newSize];
(,0,tmpArray,0,);
= tmpArray;
}
/**
* binary pile (math)inserted element
* @param element inserted element
*/
public void insert(T element) {
if (currentSize == -1) {
enlargeArray( * 2 - 1);
}
int hole = ++currentSize;
for ([0] = element;([hole/2]) < 0;hole /= 2) {
[hole] = [hole/2];
}
[hole] = element;
}
}
Since the elements in the binary heap are comparable, we define generalizations that must implement theComparableinterface. Then we define the arrayarrayand the initial length of the arrayDEFAULT_CAPACITY. And finally define the current number of nodes in the binary heapcurrentSize. The two constructors andisEmpty、makeEmptyThe method is relatively simple, so I won't go into too much detail here. Next we look at the method of data expansionenlargeArray, first compare the new length with the current length of the array, and if it is less than, throw an exception. Then it's creating new data, data copying, and replacing the old data.
Next we focus on theinsertmethod, first determine thecurrentSizeand the length of the array -1. Why subtract 1 here? Because the 0th element of the data is not used, the root node of the binary heap in the first element. If equal, the array has been exhausted, the need to expand, expansion is also used when the expansion of 2 times expansion, here minus 1 or because the root node is not used. Then first determine the location of the cavity.hole=++currentSizeThe following for loop, which is the process of up-filtering, is also the essence of this paragraph. Everyone in the implementation, may be compared with the parent element, and then exchange, this method is not a problem, but the exchange of two elements to use 3 lines of code to complete, first the first variable is assigned to the temporary variable, and then the second variable is assigned to the first variable, and finally the temporary variable is assigned to the second variable. And here only 1 line of code is used, which is the benefit of using null position. In the for loop, the new element is assigned to the 0th element, here the use of the 0th element is useful, we continue to see, and then the new element and the parent node for comparison, the parent node's subscript is hole / 2, this in the previous introduction, if less than, the value of the current null position is the parent node's value, and then deal with the position of the null position, which is the position of the parent node, the hole / = 2. If so All the way to the root node, that is, when hole = 1, the parent node does not exist, but the program is written in the hole / 2, then it is the 0th element, the 0th element is the newly inserted element, and so on, comparing themselves with themselves, is equal, so it jumps out of the loop. Finally, the value of the empty element is assigned to the empty hole position. Here we cleverly use the 0th element to realize the comparison of the root node, making the jump out of the loop.
Delete Minimum
Deleting the minimum is our out-of-queue operation. Since we use a binary heap, the minimum is at the root node, and after deletion, a cavity is created at the root node. We put the last element of the binary heap, which is the element of currentSize, into the cavity position, and then compare it with the minimum of the two child nodes, and if it is larger than that, then we exchange the two elements, and the location of the cavity is shifted downward, until the properties of the binary heap are satisfied. This process is calledunderfilter。
After deleting the root node 13, a cavity is created, and at the same time, the length of the whole array is reduced by 1. We compare the last element 31, with the smallest sub-node 14 of the cavity, and 31 is greater than 14, so we exchange the positions, as follows:
Continuing the comparison, 31 is larger than the smallest sub-node 21, and the position of the cavity is shifted downward, the
Finally, 31 is less than the child node 32, then 31 is placed in the null position, which satisfies the properties of a binary heap, and the whole down-filtering process ends. Let's realize it in code.
/**
* take out the minimum value
* @return root element
*/
public T deleteMin() {
if (isEmpty()) {
throw new RuntimeException("Bifurcated heap is empty");
}
T minItem = [1];
[1] = [currentSize--];
perlocateDown(1);
return minItem;
}
/**
* filtration process
* @param hole
*/
private void perlocateDown(int hole) {
int child;
T tmp = [hole];
for (;hole * 2 <= currentSize;hole=child) {
child = hole * 2;
if (child != currentSize && [child].compareTo([child+1]) > 0) {
child += 1;
}
if ([child].compareTo(tmp) < 0) {
[hole] = [child];
} else {
break;
}
}
[hole] = tmp;
}
deleteMinThe method is simple, it takes the root node element, assigns the last element to the root node, the number of nodes minus 1, and then calls the down-filter method. We focus on the lower filter method, the input parameter is the location of the cavity, the input is 1, which is the location of the root node, we will assign the value to the temporary variable, here the value of the root node is the last element of the binary heap. Next we enter the loop, the loop is established by the condition that the cavity position has child nodes, thehole*2 <= currentSizeThe left child node is hole*2 and the right child node is hole*2+1. Then the position of the left child node is hole*2 and the right child node is hole*2+1. Here we are dealing specifically with whether the null is only one child node or not; the case of only one child node only occurs at the last position of the binary heap ifhole*2 == currentSize, after stating that there is only one child node, and it can only be the left child node, so that we are able to find out the smallest child node of hole, the logic of judgment is: ifhole*2 == currentSizeIn other cases, you need to compare the left and right child nodes, and use whoever is smaller. This is the logic of the first if in our for loop. After the logic is relatively simple, if the value of the hole is greater than the smallest child node, the exchange, the hole down, equal to the position of the smallest child node, until the jump out of the loop. Finally the temporary value is assigned to the hole position. This is the whole process of deletion and down-filtering.
Constructing a binary heap
The most important insertion and deletion methods we have talked about, so if we are given an array, how do we build a binary heap? We still have to start from the nature of the binary heap, that is, the nature of the structure and the nature of the heap order. The structure of the nature of the easier we will be the first 0 elements empty on it, then how to solve the nature of the heap order? Since we have abstracted the down-filtering process into a method above, this is not difficult to realize. We will first be the smallest subtree, through the filtering method into a binary heap, the smallest subtree node is the penultimate node in the tree, the penultimate node, some nodes have children, some nodes do not have children, there is no need to filter the children, so how to find the children of the node it? We have a variable currentSize, which is the location of the last node, its parent node is currentSize/2, is also the last node with children, and then we loop forward, each node to perform the filtering method once until the root node filtered, then the whole tree is a binary heap. We realize that
/**
* Constructing a binary heap
* @param items
*/
@SuppressWarnings("unchecked")
public BinaryHeap(T[] items) {
= ;
= (T[])new Comparable[ * 2 +1];
int i = 1;
for (T item: items) {
[i++] = item;
}
buildHeap();
}
/**
* Constructing a binary heap
*/
private void buildHeap() {
for (int i = / 2;i>0;i--) {
perlocateDown(i);
}
}
It's easy to implement, so here's a note about the loop with the conditioni>0, is not greater than or equal to because the 0th element is not used.
summarize
Well, here bifurcated heap on the introduction of the end, it is the realization of the most basic method of priority queuing, there are problems with the partners are welcome to leave a message in the comments section ~ ~ ~