“This is the 11th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”
In detail introduced Heap (Heap) this data structure characteristics and principle, and provides the complete implementation of Java code, including the big top Heap, small top Heap construction, Heap node add, delete, big top Heap, small top Heap sort method!
Overview of the heap
1.1 Overview of the heap
To understand the heap, you must understand some basic properties of binary trees. If you are not familiar with binary trees, you can read this article: Introduction to binary trees and Java implementation case study.
The Heap is the Heap in the data structure, not the Heap in the memory model. A heap is a tree structure that satisfies the following properties:
- A heap is a complete binary tree, also known as a binary heap (binary heap).
- The value of any node in the heap is always no greater than/less than the value of its children.
If the value of each node is greater than or equal to the value of its left and right children, it is called the big top heap/maximum heap/big root heap (left); Or the value of each node is less than or equal to the value of its left and right children, known as the small top/minimum/small root heap, as shown on the right.
1.2 Common application and implementation of heap
Heap application:
- The heap is often used to implement a “PriorityQueue”. The priority queue can add data freely, but the data should be taken out from the minimum value in order;
- The heap is also used for heap sorting.
Implementation of heap: since the heap is a complete binary tree, according to the properties of binary tree, complete binary tree can be perfectly mapped to the array structure: if the nodes are numbered from 0 and mapped to the array, the relationship between nodes is as follows:
Big top pile: arr [I] > = arr [2 + 1] I && arr [I] > = arr [2 + 2] I (0 < = I < = n / 2-1)
Small top pile: arr [I] < = arr [2 + 1] I && arr [I] < = arr [2 + 2] I (0 < = I < = n / 2-1)
Small top pile: arr [I] < = arr [2 + 1] I && arr [I] < = arr [2 + 2] I (0 < = I < = n / 2-1)
N is the length of the array, and n/ 2-1 actually represents the index position of the last non-leaf node from beginning to end of the array.
Therefore, arrays are often used to implement heap structures, such as PriorityQueue in Java, which is a binary heap implemented using arrays. Since the heap counts as a partial order (there is only a parent node and child node size relationship, not the size relationship between two child nodes), the actual storage order of the heap with different algorithms for the same elements in the array is not necessarily the same, and heap sort is also an unstable sorting algorithm.
The difference between binary heap and binary sort tree:
- In a binary sort tree, the left child must be smaller than the parent, and the right child must be larger than the parent. But that’s not the case in the heap. Both children must be smaller than the parent in the largest heap, and both must be larger than the parent in the smallest heap. About binary sort tree: binary sort tree details and Java code complete implementation.
- Binary sort trees are typically implemented using linked lists, which take up more memory than they store. Additional memory must be allocated for node objects and left/right child node Pointers. The heap can use arrays to store data, node objects and left/right child nodes have a natural relationship, using indexes to reach, saving memory.
- Due to the nature of node size in a binary sort tree, searching in a binary sort tree is fast, similar to binary searching with an ordered array, and the search times will not exceed the tree depth, but searching in the heap will be slower. The purpose of using binary sort trees is to make it easy to find nodes, and the purpose of using heap is to put the largest (or smallest) nodes first, so that related sort, insert, and delete operations can be carried out quickly.
2 Implementation Principles
Here is an example of building a big top heap, which corresponds to the example in the implementation code below.
2.1 Build the big top heap from arrays
The build heap here is built from the “parent node.” In fact, heap sort is used in the process of the first time to build a big top heap process, here is not described, the specific principle of direct look at this article: 10 common sorting algorithm principle detailed explanation and the full implementation of Java code, you can directly see the principle part of the heap sort, very detailed.
The resulting array element positions and the structure mapped to the heap are as follows:
2.2 Add elements to build the big top heap
The build heap is built from “new nodes”, as opposed to heap sort, which is explained in detail here.
The general principle is as follows: Every element added, it is compared with the parent node. If the newly added node is less than or equal to the parent node, the element is added to that location. Otherwise, continue looking up the parent node until you find a position where the value of the new element at that position is less than or equal to the value of the element at the corresponding parent node, and move the elements in the original position backward. It’s a little bit abstract here, but let’s see what happens.
When the first element 49 is added, strat=0, where the heap[0] = 49 is added directly to the vertex of the heap. The position of the elements in the array and the structure mapped to the heap are as follows:
When the second element 38 is added, strat=1, parent=0, strat>0 enters the inner loop and determines the size of the parent node and the child node. Since 49>38, break breaks out of the loop, and the heap[1] = 49, the structure of the elements in the array and the map to the heap is as follows:
When adding a third element 65, strat = 2, the parent = 0, the strat > 0 into inner circulation, to judge the size of the parent and child nodes, as a result of 49 < 65, now move the value of the parent node to child nodes location, heap heap [0] = [2], Start =0; parent=0; parent=0;
Heap [start] = 65, heap[0]= 65. The position of the elements in the array and the structure mapped to the heap are as follows:
Heap [3] = heap[1]; heap[3] = heap[1]; heap[3] = heap[1]; heap[3] = heap[1]; heap[1] = heap[1]; heap[3] = heap[1]; heap[3] = heap[1]; heap[3] = heap[1]; heap[3] = heap[1]; heap[3] = heap[1]; heap[3] = heap[1]; heap[3] = heap[1]; heap[3] = heap[1] {65, 38, 49, 38}; start=1; parent=0
Heap [1] = heap[0]; heap[0] = heap[0]; heap[0] = heap[0]; heap[0] = heap[0]; heap[0] = heap[0]; Then change the index value of start to the index value of the parent node, i.e. start=0, and recalculate parent=0.
Heap [start] = 97, heap[0]= 97. The position of the elements in the array and the structure mapped to the heap are as follows:
Heap [4] = heap[1]; heap[4] = heap[1]; heap[4] = heap[1]; heap[4] = heap[1]; heap[1] = heap[1]; heap[4] = heap[1]; heap[4] = heap[1]; heap[4] = heap[1]; heap[4] = heap[1]; heap[4] = heap[1]; heap[4] = heap[1]; heap[4] = heap[1]; heap[4] = heap[1]; heap[4] = heap[1] {97, 65, 49, 38, 65}; start=1; parent=0;
At this point, start>0 starts the second inner loop, judging the size of parent and child nodes, 76<97, so break breaks out of the loop, and the heap[1] = 76 directly, at this point, the element positions in the array and the structure mapped to the heap are as follows:
When the 6th element 13 is added, strat=5, parent=2, then strat>0 enters the inner loop and determines the size of the parent node and the child node. Since 13<49, break breaks out of the loop and the heap[5] = 13, the structure of the elements in the array and the map to the heap is as follows:
When the 7th element 27 is added, strat=6, parent=2, strat>0 enters the inner loop and determines the size of the parent and child nodes. Since 27<49, break breaks out of the loop, and the heap[6] = 27 is immediately heap[6] = 27, and the structure mapped to the heap is as follows:
Heap [7] = heap[3]; heap[7] = heap[3]; heap[7] = heap[3]; heap[7] = heap[3]; heap[7] = heap[3] {97, 76, 49, 38, 65, 13, 27, 38}; start=3;
Since start>0 starts the second inner loop to judge the size of parent node and child node, since 49<76, break breaks out of the loop, and the heap[3] = 49 directly, at this point, the element positions in the array and the structure mapped to the heap are as follows:
Heap [8] = heap[3]; heap[8] = heap[3]; heap[8] = heap[3]; heap[8] = heap[3]; heap[8] = heap[3]; heap[8] = heap[3] {97, 76, 49, 49, 65, 13, 27, 38, 49}; start=3;
Heap [3] = heap[1] {97, 76, 49, 76, 65, 13, 27, 38, 49};
At this point, start>0 starts the third inner loop, judging the size of parent and child nodes, 78<97, so break breaks out of the loop, at this point, the direct heap[1] = 78, at this point, the element positions in the array and the structure mapped to the heap are as follows:
So this is the end result, and you can see that it’s not the same as the end result sequence that you would build directly from an array, but they all fit the requirements of the big top heap, which proves that the big top heap sequence is not unique.
2.3 Deleting Elements
- First check the array for the presence of the corresponding element, if not return false;
- Retrieves the index of the first element found if it exists (since there may be identical elements, the delete is the first element found);
- The next step is the same as rebuilding the big top heap in heap sorting, which is essentially swapping the elements to be deleted with the last-heap elements, removing the last-heap elements, and then rebuilding the big top heap down from the index of the deleted elements.
- The operation of reconstructing the big top heap downward only ensures that the structure below the heap meets the requirements from this index location. Down but the refactoring and heap sort, heap sort from the reconstruction of the pile top, thus can ensure the meet the requirements of the whole heap, and here is probably from the middle of the pile of a node, the reconstruction after down, also need to check the starting position of nodes have adjust the position, because the beginning is a big heap structure, That is, the parent node is greater than or equal to the child node. If the position is adjusted, then the structure before the initial index also meets the requirements. If the position is not adjusted, then the starting element may be greater than or equal to its child, but also larger than its parent. In this case, it is necessary to reconstruct the big top heap upward from that position to ensure that the structure of the heap from that index position is also satisfied.
2.4 the heap sort
Here is not much to describe, the specific principle directly read this article:10 kinds of common sorting algorithm principle detailed explanation and Java code complete implementation, you can directly look at the principle part of heap sort, very detailed.
Realization of big top heap
Classes that provide array-based implementations of the big top heap, provide methods for building the big top heap from collections, provide methods for adding and removing nodes, and provide methods for heap sorting (ordering) of the big top heap.
/** * big top heap implementation * {@linkMaxBinaryHeap()} Initializes the empty big top heap, using the default size * {@linkMaxBinaryHeap#MaxBinaryHeap(int)} Initializes the empty big top heap, using the specified capacity * {@linkMaxBinaryHeap#MaxBinaryHeap(Comparator)} initializes the empty big top heap using the specified Comparator * {@linkMaxBinaryHeap#MaxBinaryHeap(int, Comparator)} initializes the empty big top heap using the specified capacity and Comparator * {@linkMaxBinaryHeap(Collection)} Builds the large top heap from the specified Collection elements * {@linkMaxBinaryHeap(Collection, Comparator)} Constructs the large top heap from the specified Collection element, using the custom Comparator * {@linkMaxBinaryHeap#add(Object)} add elements and rebuild the big top heap * {@linkMaxBinaryHeap#remove(Object)} delete the element and rebuild the big top heap * {@linkMaxBinaryHeap#heapSort()} big top heapSort * {@linkMaxBinaryHeap#toString()} outputs the big top heap * *@author lx
*/
public class MaxBinaryHeap<E> {
/** * the physical storage structure of the heap, which uses arrays to implement */
private Object[] heap;
/** * Number of nodes */
private int size;
/** * Capacity */
private static int capacity = 16;
/** * If the elements use natural ordering, then the comparator is null; Otherwise, use a comparator to compare */
private final Comparator<? super E> cmp;
/** * A method to compare the size of elements, using a custom comparator if passed, otherwise requiring data types to implement the Comparable interface **@paramE1 The first object to be compared *@paramE2 is the second object to be compared@return0 is equal; E1 < e2; E1 > e2 */
private int compare(E e1, E e2) {
if(cmp ! =null) {
return cmp.compare(e1, e2);
} else {
return((Comparable<E>) e1).compareTo(e2); }}/** * Initializes the empty big top heap, using the default size */
public MaxBinaryHeap(a) {
this(capacity, null);
}
/** * Initializes the empty big top heap, specifying the size **@paramInitCapacity Specifies the capacity array */
public MaxBinaryHeap(int initCapacity) {
this(initCapacity, null);
}
/** * initializes the empty big top heap, specifying the comparator **@paramThe comparator specifies the */ comparator
public MaxBinaryHeap(Comparator<? super E> comparator) {
this(capacity, comparator);
}
/** * Initializes the empty big top heap, specifying the capacity and comparator **@paramInitCapacity Specifies the array capacity *@paramThe comparator specifies the */ comparator
public MaxBinaryHeap(int initCapacity, Comparator<? super E> comparator) {
if (initCapacity < 1) {
throw new IllegalArgumentException();
}
capacity = initCapacity;
this.heap = new Object[initCapacity];
cmp = comparator;
}
/** * Initialize the big top heap with a batch of data **@paramThe heap array * /
public MaxBinaryHeap(Collection<? extends E> heap) {
this(heap, null);
}
/** * Initializes the big top heap with a batch of data and a specified comparator@paramHeap array *@paramComparator Custom comparator */
public MaxBinaryHeap(Collection<? extends E> heap, Comparator<? super E> comparator) {
Object[] array = heap.toArray();
this.cmp = comparator;
if(array.getClass() ! = Object[].class) { array = Arrays.copyOf(array, array.length, Object[].class); }for (Object o : array) {
if (o == null) {
throw newNullPointerException(); }}this.heap = array;
this.size = array.length;
buildHeap(this.heap);
}
/** * Initialize the big top heap with a batch of data **@paramHeap data array */
private void buildHeap(Object[] heap) {
/* I starts at the index of the last non-leaf node and builds down until I =-1 ends the loop where the index of the element starts at 0, so the last non-leaf node array.length/ 2-1, which takes advantage of the property of a complete binary tree */
for (int i = heap.length / 2 - 1; i >= 0; i--) { buildHeap(heap, i, heap.length); }}/** * Initialize the big top heap with a batch number **@paramArr data array *@paramI Index of non-leaf nodes *@paramLength Indicates the heap length */
private void buildHeap(Object[] arr, int i, int length) {
// Take out the current non-leaf node element first, because the current element may keep moving
Object temp;
// Index of the child node of the node
int childIndex;
/* Loop to determine whether the parent is greater than two children, and end the loop if the left child index is greater than or equal to the heap length or the parent is greater than two children */
for (temp = arr[i]; (childIndex = 2 * i + 1) < length; i = childIndex) {
//childIndex + 1 < length indicates that the node has a right child, and if the value of the right child is greater than that of the left child, then childIndex is incremented by 1
if (childIndex + 1 < length && compare((E) arr[childIndex], (E) arr[childIndex + 1]) < 0) {
childIndex++;
}
// If the largest child is found to be larger than the root node, swap values to ensure that the root node of the large top heap is larger than the child node
// If the child node is changed, then the root of the child node will be affected, so continue the loop to determine the tree where the child node is
if (compare((E) arr[childIndex], (E) temp) > 0) {
swap(arr, i, childIndex);
} else {
// The parent node is larger than the largest child node, which satisfies the condition of the large top heap
break; }}}/** * Big top heap sort (order) * is essentially a loop of swapping top and bottom elements, removing bottom elements, and reconstructing the big top heap */
public Object[] heapSort() {
// Use a copy of the big top heap to sort the output
Object[] arr = Arrays.copyOf(heap, size);
/* Start heap sort, I = arr. length-1, that is, from the end of the big top heap to I =0 to end the loop */
for (int i = size - 1; i > 0; i--) {
// Swap the top and bottom of the heap
swap(arr, 0, i);
// Rebuild the big top heap
buildHeap(arr, 0, i);
}
return arr;
}
/** * add nodes to build a big top heap **@paramE Node to be added */
public void add(E e) {
* / / * found empty
if (e == null) {
throw new NullPointerException();
}
/* Check the capacity */
if (heap.length == size) {
resize();
}
/* Add a node */
addNode(e, size++);
}
/** * add node, and rebuild the big top heap upward, finally find a position to add a new node e, the node of the position is less than or equal to its parent **@paramE Node to be added */
private void addNode(E e, int start) {
// Get the parent index of the node at size
int parent = (start - 1) / 2;
/* If size>0 find the appropriate position: the new node at an inserted position is less than or equal to the value of the corresponding parent node */
while (start > 0) {
If the size of the parent node is less than or equal to the size of the new child node, then it meets the requirements of the small top heap. After reconstruction, start is the position where the child node is inserted
if (compare((E) heap[parent], e) >= 0) {
break;
} else {
Otherwise, move the value of the parent node to the position of the child node
heap[start] = heap[parent];
// Change the index of start to the index of the parent node
start = parent;
// Recalculates the index of the parent node, looping until it finds an index whose parent value is less than or equal to the value of the new child node
parent = (start - 1) / 2; }}// Insert the new node value in the appropriate position
heap[start] = e;
}
/** ** base array expansion */
private void resize(a) {
heap = Arrays.copyOf(heap, heap.length * 2, Object[].class);
}
/** * swap elements **@paramArray arr *@paramThe subscript star of the element A@paramThe subscript of the b element */
private static void swap(Object[] arr, int a, int b) {
Object temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/** * delete the first heap node found, and rebuild the big top heap **@paramE Node to be deleted *@returnFalse Delete failed true delete succeeded */
public boolean remove(E e) {
int eIndex = -1;
for (int i = 0; i < size; i++) {
// Compare to see if the elements are the same
if (compare((E) heap[i], e) == 0) { eIndex = i; }}/* The element to delete was not found */
if (eIndex == -1) {
return false;
}
/* Find */
// The original tail element x
E x = (E) heap[size - 1];
// Swap the position of the found element with the element at the bottom of the heap
swap(heap, eIndex, size - 1);
// Remove the heap tail element
heap[size--] = null;
// Rebuild the big top heap from eIndex down
buildHeap(heap, eIndex, size);
// After the build, if the element at eIndex is x, the heap structure has not been adjusted, then the element at that position is treated as the newly inserted element, and the big top heap needs to be built upwards
if (heap[eIndex] == x) {
// Call addNode to rebuild the big top heap upward from eIndex
addNode(x, eIndex);
}
return true;
}
public int size(a){
return size;
}
@Override
public String toString(a) {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for (int i = 0; i < size; i++) {
stringBuilder.append(heap[i]);
if(i ! = size -1) {
stringBuilder.append(",");
}
}
stringBuilder.append("]");
returnstringBuilder.toString(); }}Copy the codeRealization of small top heap
Classes that provide array-based implementations of small top heaps, methods for building small top heaps from collections, methods for adding and removing nodes, and methods for heap sorting (reverse order) of small top heaps. In fact, the implementations of the big and small top heap differ only in that some of the comparison conditions are reversed and most of the code is the same.
/** * small top heap implementation * {@linkMinBinaryHeap#MinBinaryHeap()} Initializes the empty small top heap, using the default size * {@linkMinBinaryHeap#MinBinaryHeap(int)} Initializes the empty small top heap, using the specified capacity * {@linkMinBinaryHeap#MinBinaryHeap(Comparator)} initializes the empty small top heap using the specified Comparator * {@linkMinBinaryHeap#MinBinaryHeap(int, Comparator)} initializes the empty small top heap using the specified capacity and Comparator * {@linkMinBinaryHeap#MinBinaryHeap(Collection)} Builds a small top heap from the specified Collection elements * {@linkMinBinaryHeap#MinBinaryHeap(Collection, Comparator)} Builds the small top heap from the specified Collection element, using a custom Comparator * {@linkMinBinaryHeap#add(Object)} add elements and rebuild the small top heap * {@linkMinBinaryHeap#remove(Object)} delete the element and rebuild the small top heap * {@linkMinBinaryHeap#heapSort()} small top heapSort * {@linkMinBinaryHeap#toString()} outputs the small top heap * *@author lx
*/
public class MinBinaryHeap<E> {
/** * the physical structure of the heap, which uses arrays to implement */
private Object[] heap;
/** * Number of nodes */
private int size;
/** * Capacity */
private static int capacity = 16;
/** * If elements use natural ordering, then the comparator is null */
private final Comparator<? super E> cmp;
/** * A method to compare the size of elements, using a custom comparator if passed, otherwise requiring data types to implement the Comparable interface **@paramE1 The first object to be compared *@paramE2 is the second object to be compared@return0 is equal; E1 < e2; E1 > e2 */
private int compare(E e1, E e2) {
if(cmp ! =null) {
return cmp.compare(e1, e2);
} else {
return((Comparable<E>) e1).compareTo(e2); }}/** * Initializes the empty small top heap, using the default size */
public MinBinaryHeap(a) {
this(capacity, null);
}
/** * Initializes the empty small top heap, specifying the size **@paramInitCapacity Specifies the capacity array */
public MinBinaryHeap(int initCapacity) {
this(initCapacity, null);
}
/** * initializes the empty small top heap, specifying the comparator **@paramThe comparator specifies the */ comparator
public MinBinaryHeap(Comparator<? super E> comparator) {
this(capacity, comparator);
}
/** * Initializes the empty small top heap, specifying the capacity and comparator **@paramInitCapacity Specifies the array capacity *@paramThe comparator specifies the */ comparator
public MinBinaryHeap(int initCapacity, Comparator<? super E> comparator) {
if (initCapacity < 1) {
throw new IllegalArgumentException();
}
capacity = initCapacity;
this.heap = new Object[initCapacity];
cmp = comparator;
}
/** * Initialize the small top heap with a batch of data **@paramThe heap array * /
public MinBinaryHeap(Collection<? extends E> heap) {
this(heap, null);
}
/** * Initializes the small top heap with a batch of data and a specified comparator@paramHeap array *@paramComparator Custom comparator */
public MinBinaryHeap(Collection<? extends E> heap, Comparator<? super E> comparator) {
Object[] array = heap.toArray();
this.cmp = comparator;
if(array.getClass() ! = Object[].class) { array = Arrays.copyOf(array, array.length, Object[].class); }for (Object o : array) {
if (o == null) {
throw newNullPointerException(); }}this.heap = array;
this.size = array.length;
buildHeap(this.heap);
}
/** * Build a small top heap **@paramHeap batch data */
private void buildHeap(Object[] heap) {
/* I starts at the index of the last non-leaf node and builds down until I =-1 ends the loop where the index of the element starts at 0, so the last non-leaf node array.length/ 2-1, which takes advantage of the property of a complete binary tree */
for (int i = heap.length / 2 - 1; i >= 0; i--) { buildHeap(heap, i, heap.length); }}/** * builds the small top heap from the specified index down to a node less than or equal to its child **@paramArray arr *@paramI Index of non-leaf nodes *@paramLength Indicates the heap length */
private void buildHeap(Object[] arr, int i, int length) {
// Take out the current non-leaf node element first, because the current element may keep moving
Object temp;
// Index of the child node of the node
int childIndex;
/* Loop to determine whether the parent is greater than two children, and end the loop if the left child index is greater than or equal to the heap length or the parent is greater than two children */
for (temp = arr[i]; (childIndex = 2 * i + 1) < length; i = childIndex) {
//childIndex + 1 < length indicates that the node has a right child, and if the value of the right child is less than that of the left child, then childIndex increases by 1, i.e. childIndex points to the right child
if (childIndex + 1 < length && compare((E) arr[childIndex], (E) arr[childIndex + 1) >0) {
childIndex++;
}
// If it is found that the smallest node (left and right child nodes) is smaller than the root node, a value swap is required to satisfy that the root node of the small top heap is smaller than the child node
// If the child node is changed, then the root of the child node will be affected, so continue the loop to determine the tree where the child node is
if (compare((E) arr[childIndex], (E) temp) < 0) {
swap(arr, i, childIndex);
} else {
// The parent node is less than or equal to the smallest child node, which satisfies the small top heap condition
break; }}}/** * Small top heap sort (order) **@paramArr requires the data set to be sorted */
public void bigHeapSort(Object[] arr) {
/* build a small top heap */
/* I starts at the index of the last non-leaf node and builds down until I =-1 ends the loop where the index of the element starts at 0, so the last non-leaf node array.length/ 2-1, which takes advantage of the property of a complete binary tree */
for (int i = arr.length / 2 - 1; i >= 0; i--) {
buildHeap(arr, i, arr.length);
}
/*2, start heap sort, I = arr. Length - 1, that is, the number of the bottom of the small top heap, until I =0 to end the loop */
for (int i = arr.length - 1; i > 0; i--) {
// Swap the top and bottom of the heap
swap(arr, 0, i);
// Rebuild the small top heap
buildHeap(arr, 0, i); }}/** * Small top heap sort (reverse order) * is essentially a loop of swapping top and bottom elements, removing bottom elements, and reconstructing the small top heap */
public Object[] heapSort() {
// Sort the output using a copy of the small top heap
Object[] arr = Arrays.copyOf(heap, size);
/*2, start heap sort, I = arr. Length - 1, that is, the number of the bottom of the small top heap, until I =0 to end the loop */
for (int i = arr.length - 1; i > 0; i--) {
// Swap the top and bottom of the heap
swap(arr, 0, i);
// Rebuild the small top heap, at this point the heap size is -1 before the swap
buildHeap(arr, 0, i);
}
return arr;
}
/** * Add node **@paramE The added node element */
public void add(E e) {
* / / * found empty
if (e == null) {
throw new NullPointerException();
}
/* Check the capacity */
if (heap.length == size) {
resize();
}
/* Add a node */
addNode(e, size++);
}
/** * add nodes, and rebuild the small top heap upward, finally find a position to add a new node e, the node of the position is greater than or equal to its parent **@paramE Node * to be added@paramStart is the index of the newly added element */
private void addNode(E e, int start) {
// Get the parent index of the size node
int parent = (start - 1) / 2;
/* If size>0 find the appropriate position: the new node at an inserted position is greater than or equal to the corresponding parent node */
while (start > 0) {
// Determine the size of the parent node and the new child node. If the parent node is less than or equal to the new child node, then the small top heap requirements are met
if (compare((E) heap[parent], e) <= 0) {
break;
} else {
Otherwise, move the value of the parent node to the position of the child node
heap[start] = heap[parent];
// Change the index of start to the index of the parent node
start = parent;
// Recalculates the index of the parent node, looping until it finds an index whose parent value is less than or equal to the value of the new child node
parent = (start - 1) / 2; }}// Insert the new node value in the appropriate position
heap[start] = e;
}
/** ** */
private void resize(a) {
heap = Arrays.copyOf(heap, heap.length * 2, Object[].class);
}
/** * swap elements **@paramArray arr *@paramThe subscript star of the element A@paramThe subscript of the b element */
private static void swap(Object[] arr, int a, int b) {
Object temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/** * delete the first heap node found and rebuild the small top heap **@paramE Node to be deleted *@returnFalse Delete failed true delete succeeded */
public boolean remove(E e) {
int eIndex = -1;
for (int i = 0; i < size; i++) {
if (compare((E) heap[i], e) == 0) { eIndex = i; }}if (eIndex == -1) {
return false;
}
// The original tail element x
E x = (E) heap[size - 1];
// Swap the position of the found element with the element at the bottom of the heap
swap(heap, eIndex, size - 1);
// Remove the heap tail element
heap[size--] = null;
// Rebuild the small top heap from eIndex down
buildHeap(heap, eIndex, size);
// After the build, if the element at eIndex is x, the heap structure has not been adjusted, then the element at that position is treated as the newly inserted element, and the small top heap needs to be built upwards
if (heap[eIndex] == x) {
// Call addNode to rebuild the small top heap upward from eIndex
addNode(x, eIndex);
}
return true;
}
@Override
public String toString(a) {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for (int i = 0; i < size; i++) {
stringBuilder.append(heap[i]);
if(i ! = size -1) {
stringBuilder.append(",");
}
}
stringBuilder.append("]");
returnstringBuilder.toString(); }}Copy the code5 Test Cases
/** * heap test **@author lx
*/
public class BinaryTest {
/** * Builds the big top heap in the constructor with an array */
@Test
public void testMaxBinaryHeap1(a) {
Integer[] arr = new Integer[]{49.38.65.97.76.13.27.49.78};
// Build the big top heap
MaxBinaryHeap<Integer> maxBinaryHeap = new MaxBinaryHeap<>(Arrays.asList(arr));
// Output the big top heap
System.out.println(maxBinaryHeap);
// Add nodes and rebuild the big top heap
maxBinaryHeap.add(11);
maxBinaryHeap.add(77);
// Output the big top heap
System.out.println(maxBinaryHeap);
// Delete the node and rebuild the big top heap
// Delete failed
System.out.println(maxBinaryHeap.remove(79));
// The deletion succeeded
System.out.println(maxBinaryHeap.remove(78));
// Output the big top heap
System.out.println(maxBinaryHeap);
// Heap sort (sequential sort)
System.out.println(Arrays.toString(maxBinaryHeap.heapSort()));
// Output the big top heap
System.out.println(maxBinaryHeap);
}
/** * Build the big top heap with the add method */
@Test
public void testMaxBinaryHeap2(a) {
MaxBinaryHeap<Integer> maxBinaryHeap = new MaxBinaryHeap<>();
maxBinaryHeap.add(49);
maxBinaryHeap.add(38);
maxBinaryHeap.add(65);
maxBinaryHeap.add(97);
maxBinaryHeap.add(76);
maxBinaryHeap.add(13);
maxBinaryHeap.add(27);
maxBinaryHeap.add(49);
maxBinaryHeap.add(78);
/ / output large pile top,78,49,76,65,13,27,38,49 [97]
System.out.println(maxBinaryHeap);
// Add nodes and rebuild the big top heap
maxBinaryHeap.add(11);
maxBinaryHeap.add(77);
// Output the big top heap
System.out.println(maxBinaryHeap);
// Delete node, you
// Delete failed
System.out.println(maxBinaryHeap.remove(79));
// The deletion succeeded
System.out.println(maxBinaryHeap.remove(78));
// Output the big top heap
System.out.println(maxBinaryHeap);
// Heap sort (sequential sort)
System.out.println(Arrays.toString(maxBinaryHeap.heapSort()));
// Output the big top heap
System.out.println(maxBinaryHeap);
}
/** * Builds the small top heap in the constructor with an array */
@Test
public void testMinBinaryHeap1(a) {
Integer[] arr = new Integer[]{49.38.65.97.76.13.27.49.78};
// Build a small top heap
MinBinaryHeap<Integer> minBinaryHeap = new MinBinaryHeap<>(Arrays.asList(arr));
// Output small top heap
System.out.println(minBinaryHeap);
// Add nodes and rebuild the small top heap
minBinaryHeap.add(11);
minBinaryHeap.add(77);
// Output small top heap
System.out.println(minBinaryHeap);
// Delete the node and rebuild the small top heap
// Delete failed
System.out.println(minBinaryHeap.remove(79));
// The deletion succeeded
System.out.println(minBinaryHeap.remove(78));
// Output small top heap
System.out.println(minBinaryHeap);
// Heap sort (reverse sort)
System.out.println(Arrays.toString(minBinaryHeap.heapSort()));
// Output small top heap
System.out.println(minBinaryHeap);
}
/** * Build the small top heap with the add method */
@Test
public void testMinBinaryHeap2(a) {
MinBinaryHeap<Integer> minBinaryHeap = new MinBinaryHeap<>();
minBinaryHeap.add(49);
minBinaryHeap.add(38);
minBinaryHeap.add(65);
minBinaryHeap.add(97);
minBinaryHeap.add(76);
minBinaryHeap.add(13);
minBinaryHeap.add(27);
minBinaryHeap.add(49);
minBinaryHeap.add(78);
// Output small top heap
System.out.println(minBinaryHeap);
// Add nodes and rebuild the small top heap
minBinaryHeap.add(11);
minBinaryHeap.add(77);
// Output small top heap
System.out.println(minBinaryHeap);
// Delete the node and rebuild the small top heap
// Delete failed
System.out.println(minBinaryHeap.remove(79));
// The deletion succeeded
System.out.println(minBinaryHeap.remove(78));
// Output small top heap
System.out.println(minBinaryHeap);
// Heap sort (reverse sort)
System.out.println(Arrays.toString(minBinaryHeap.heapSort()));
// Output small top heap
System.out.println(minBinaryHeap);
}
/** * remove A node that is smaller than or equal to the child node but smaller than the parent node */
@Test
public void testMinBinaryHeap3(a) {
MinBinaryHeap<Integer> minBinaryHeap = new MinBinaryHeap<>();
// Add nodes and rebuild the small top heap
minBinaryHeap.add(0);
minBinaryHeap.add(25);
minBinaryHeap.add(1);
minBinaryHeap.add(30);
minBinaryHeap.add(35);
minBinaryHeap.add(7);
minBinaryHeap.add(3);
minBinaryHeap.add(40);
minBinaryHeap.add(45);
minBinaryHeap.add(50);
minBinaryHeap.add(55);
minBinaryHeap.add(8);
minBinaryHeap.add(9);
minBinaryHeap.add(15);
minBinaryHeap.add(16);
System.out.println(minBinaryHeap);
System.out.println(Arrays.toString(minBinaryHeap.heapSort()));
// After removing 30, 30 and 16 switch positions, 16 is less than or equal to 40, 45 is true, so there is no adjustment
// But 16 is also less than the parent 25, so you need to build up a build
minBinaryHeap.remove(30);
System.out.println(minBinaryHeap);
System.out.println(Arrays.toString(minBinaryHeap.heapSort()));
}
Copy the codeRelated references:
- Data Structures and Algorithms
If you don’t understand or need to communicate, you can leave a message. In addition, I hope to like, collect, pay attention to, I will continue to update a variety of Java learning blog!