define
Priority queue: a special queue in which elements are removed from the stack in order of priority rather than in order of entry.
Features of the heap:
- It must bePerfect binary tree
- Do it with an array
- The value of any node is the maximum or minimum value of all nodes in its subtree
- Maximum, called the “maximum heap”, also called the big top heap;
- Minimum, called the “minimum heap”, also known as the small top heap.
As you can see, for a data structure like the Heap, all nodes on the path from the root node to any node are ordered.
Heap of ADT
The realization of the heap
The heap is a full binary tree implemented in arrays, so in Java we can use an ArrayList, and when we insert elements into an ArrayList, it automatically grows when the array is short, so we don’t have to worry about the maximum size of the heap. The insert and delete operations in the above ADT are described here. In general, the maximum value, which is actually the first element in the maximum heap, is removed from the heap. The following implementation removes any node from the heap for generality.
Let’s take the composition of the maximum heap as an example and look at how to use arrays to implement the heap.
The maximum heap
insert
How is heap insertion implemented? As long as we keep in mind the definition of heap, it’s actually quite easy to implement. Here’s a review of the main points
- Perfect binary tree
- The value of any node is the maximum value of its left and right subtrees
- Do it with an array
Consider the heap shown below.
Suppose the existing element 60 needs to be inserted. In order to maintain the property of a full binary tree, the newly inserted element must be placed in the right subtree of node 44. At the same time in order to meet the value of any node should be greater than the value of left and right subtrees of the properties, comparing to the newly inserted element and its parent nodes, if larger than the parent, the parent node is down for the position of the current node, is constantly looking for upwards, in turn find smaller than their parent is down, until no eligible value. So, at the end, you’re done inserting; To summarize:
- The newly inserted node is added to the end of the array
- If it is larger than its parent, it replaces the current position with the parent and moves its position up.
- Until the parent is no longer larger than itself or it’s close to the first place in the array, it finds its place.
Here, for convenience, we directly take the index zero of the array, and put a null at zero, so that the index of the actual valid values in the array corresponds to the actual ordinal of the order traversal in our full binary tree. So, in a complete binary tree, if the node is n, then the left subtree is 2n, and the right subtree is 2n+1; In other words, for any node N, the parent is rounded to n over 2.
- Initialize the heap
public class MaxHeap<T extends Comparable<T>> {
private List<T> mHeap;
public MaxHeap(a) {
mHeap = new ArrayList<>();
// For convenience, place an empty element in the array at index 0, so that the array starts at index 1
// In a complete binary tree, if the node value is n, the left subtree is 2n, and the right subtree is 2n+1
mHeap.add(0.null); }}Copy the codeOf course, to ensure order, we need the elements in the heap to implement the Comparable interface.
- The insert
/** * insert into the heap *@param value
*/
public void insert(T value) {
// The newly inserted elements are placed first and last in the array, keeping the full binary tree nature
mHeap.add(value);
// Get the index position of the last element in the array, starting at index=1
int index = mHeap.size() - 1;
// Parent position
int pIndex = index / 2;
// In the range of the array, compare the insert value to its parent. If the value is larger than the parent, replace the current value with the parent, and the index position is raised to the parent
while (index > 1) {
// If the inserted node is less than or equal to its parent, no adjustment is required
if (compare(value, mHeap.get(pIndex)) <= 0) {
break;
} else {
// Drop the smaller value of the parent in turn
mHeap.set(index, mHeap.get(pIndex));
// Go up one layer
index = pIndex;
// The new parent
pIndex = index / 2; }}// Finally find the position of index and put the value in
mHeap.set(index, value);
}
/ * * * *@param a
* @param b
* @returnA >b returns a value greater than 0, and vice versa less than 0 */
private int compare(T a, T b) {
return a.compareTo(b);
}Copy the codeHere it is important to note that when inserting nodes is greater than the parent, we didn’t exchange algorithm of two elements, but the small elements “drop down”, because we finally just want to find a right place, exchange is unnecessary, only need to put the value up at the last in the right place.
delete
Now that you understand the implementation of inserts, the same rules apply to deletes.
Suppose we want to remove node 58 from the figure above. In order to maintain the property of a full binary tree, it is easy to think of replacing 58 with the last element 31; Then compare the size relationship between 31 and its subtree. If it is smaller than the left or right subtree (if it exists), it will be replaced by a larger value from the left or right subtree, and it will run to the position of the corresponding subtree, and the operation will be repeated until no subtree is smaller than it. In this case, along the lines above, 44 will run to the root node, which will be replaced by 31, and the heap will still be the heap. To summarize:
- Locate the location of the node to be deleted in the array
- Replace the element at this position with the last element in the array
- The current position is compared with its left and right subtrees to ensure that it conforms to the maximum heap of node rules
- Remove the last element
/** * delete any value of the heap *@param value
* @return* /
public boolean delete(T value) {
if (mHeap.isEmpty()) {
return false;
}
// Get the index of the element in the array
int index = mHeap.indexOf(value);
if (index == -1) { // The deleted element is not in the array, i.e. the deleted element is not in the heap
return false;
}
// Get the index position of the last element in the array, starting at index=1
int lastIndex = mHeap.size() - 1;
T temp = mHeap.get(lastIndex);
// Replace the deleted position with the last element
mHeap.set(index, temp);
int parent;
for (parent = index; parent * 2 <= mHeap.size()-1; parent = index) {
// The left subtree index of the current node
index = parent * 2;
// The left subtree index is not equal to the array length, so there must be a right subtree
if(index ! = mHeap.size()-1 && compare(mHeap.get(index), mHeap.get(index + 1))"0) {
// If the right subtree is large, then the subtree points to the right subtree
index=index+1;
}
if (compare(temp, mHeap.get(index)) > 0) {
// If the current node is larger than its left and right subtrees, the node exits without adjusting
break;
}else {
// Subtree shift, replace the current nodemHeap.set(parent, mHeap.get(index)); }}// parent replaces the final position of the node
mHeap.set(parent, temp);
// Remove the last element of the array
mHeap.remove(lastIndex);
return true;
}Copy the codeOne thing to note about the delete operation is that since our array starts at index =1, we need to pay attention to the relationship between the array boundary value and its length.
Let’s test the maximum heap implementation:
The test class
private static Integer[] arrays = new Integer[]{10.8.3.12.9.4.5.7.1.11.17};
private static void MaxHeapTest(a) {
MaxHeap<Integer> mMaxHeap = new MaxHeap<>();
for (int i = 0; i < arrays.length; i++) {
mMaxHeap.insert(arrays[i]);
}
mMaxHeap.printHeap();
System.out.printf("delete value %d from maxHeap isSuccess=%b \n".17, mMaxHeap.delete(17));
mMaxHeap.printHeap();
System.out.printf("delete value %d from maxHeap isSuccess=%b \n".1, mMaxHeap.delete(1));
mMaxHeap.printHeap();
System.out.printf("delete value %d from maxHeap isSuccess=%b \n".12, mMaxHeap.delete(12));
mMaxHeap.printHeap();
System.out.printf("insert value %d to maxHeap \n".16);
mMaxHeap.insert(16);
mMaxHeap.printHeap();
}Copy the codeThe implementation of printHeap() can be seen in the minimum heap complete source code below.
Output:
17 12 5 8 11 3 4 7 1 9 10
delete value 17 from maxHeap isSuccess=true
12 11 5 8 10 3 4 7 1 9
delete value 1 from maxHeap isSuccess=true
12 11 5 8 10 3 4 7 9
delete value 12 from maxHeap isSuccess=true
11 10 5 8 9 3 4 7
insert value 16 to maxHeap
16 11 5 10 9 3 4 7 8Copy the codeAs you can see, when we first complete the traversal insertion, we will build a full binary tree as shown below, which is obviously also the maximum heap. When we delete or insert an element at a time, we can see that our insert and delete operations are correct, based on the output corresponding to the heap.
例 句 : This tree is crooked, just like that.
The following several output corresponding tree, interested students can hand animation, learning binary tree hand animation tree is really a good method.
The minimum heap
The minimum heap, the value of each node is less than the value of its left and right subtrees, so it’s easy to think of building the maximum tree by reversing all the logic of determining the size. In fact, it is that simple, the complete code for the full minimum heap implementation is given below, without specific analysis.
public class MinHeap<T extends Comparable<T>> {
private List<T> mHeap;
// The current number of elements in the heap
public int size;
public MinHeap(a) {
mHeap = new ArrayList<>();
// For convenience, place an empty element in the array at index 0, so that the array starts at index 1
// In a complete binary tree, if the node value is n, the left subtree is 2n, and the right subtree is 2n+1
mHeap.add(0.null);
}
public void insert(T value) {
// The newly inserted elements are placed first and last in the array, keeping the full binary tree nature
mHeap.add(value);
// Get the index position of the last element in the array. Note that we start at index=1, so the last element is sized -1
int index = mHeap.size() - 1;
// Parent position
int pIndex = index / 2;
// In the range of the array, compare the interpolated value to its parent. If the value is smaller than the parent, replace the current value with the parent. The index position is raised to the parent
while (index > 1) {
// If the inserted node is greater than or equal to its parent, no adjustment is required
if (compare(value, mHeap.get(pIndex)) >= 0) {
break;
} else {
// In turn, "push" the parent's larger values down and "push" the smaller values up
mHeap.set(index, mHeap.get(pIndex));
// Go up one layer
index = pIndex;
// The new parent
pIndex = index / 2; }}// Finally find the position of index and put the value in
mHeap.set(index, value);
}
public boolean remove(T value) {
if (mHeap.isEmpty()) {
return false;
}
// Get the index of the element in the array
int index = mHeap.indexOf(value);
if (index == -1) { // The deleted element is not in the array, i.e. the deleted element is not in the heap
return false;
}
// Get the index position of the last element in the array. Note that we start at index=1, so the last element is sized -1
int lastIndex = mHeap.size() - 1;
T temp = mHeap.get(lastIndex);
// Replace the deleted position with the last element
mHeap.set(index, temp);
int parent;
for (parent = index; parent * 2 <= mHeap.size()-1; parent = index) {
// The left subtree index of the current node
index = parent * 2;
// The left subtree is not equal to the array length, so there must be a right subtree
if(index ! = mHeap.size()-1 && compare(mHeap.get(index), mHeap.get(index + 1)) >0) {
// If the right subtree is small, the subtree points to the right subtree
index=index+1;
}
if (compare(temp, mHeap.get(index)) < 0) {
// If the current node is smaller than its left and right subtrees, the node exits directly without adjustment
break;
}else {
// Subtree shift, replace the current nodemHeap.set(parent, mHeap.get(index)); }}// parent replaces the final position of the node
mHeap.set(parent, temp);
// Remove the last element of the array
mHeap.remove(lastIndex);
return true;
}
private int compare(T a, T b) {
return a.compareTo(b);
}
public void printHeap(a){
StringBuilder sb = new StringBuilder();
for(int i=1; i<mHeap.size(); i++) { sb.append(mHeap.get(i)).append(""); } System.out.println(sb.toString()); }}Copy the codeTest class does not occupy space here, interested students can directly see the source code.
Ok, so that’s the implementation of the heap.