Binary heap structure
Binary heap is a special binary tree with the following two characteristics:
1. It is a complete binary tree, meaning that every layer of the tree has left and right child nodes (except the leaf node of the last layer).
2. The leaf nodes of the last layer are all left child nodes as far as possible, which is called structural characteristics.
A binary heap is either the smallest heap or the largest heap. The minimum heap allows you to quickly export the minimum value of the tree, and the maximum heap allows you to quickly export the maximum value of the tree.
All nodes are greater than or equal to (maximum heap) or less than or equal to (minimum heap) each of its children. This is called heap property.
In the picture above:
The right side of the second layer in Figure 1 has no left and right child nodes, so it is illegal.
The left side of the second layer in Figure 2 has no left and right child nodes, so it is illegal.
The last child node on the right of Figure 3 should be at the right child node on the second layer on the left.
Figure 4 should look like Figure 6.
Figure 5 conforms to two characteristics of binary heap, so it is legal.
Figure 6 also conforms to two characteristics of binary heap, so it is legal.
FIG. 7 The second layer on the left has the right child node 4 without the left child node, which is illegal.
Figure 8 conforms to two characteristics of binary heap, so it is legal.
Realization of minimum heap structure of binary heap structure
There are two ways to represent a binary tree. The first is to use a dynamic representation called a pointer (represented by a node), as shown on the left. The second is to use an array that retrieves the values of the parent node, left and right child nodes by index values, as shown on the right side of the figure below.
Due to the nature of the binary heap, values are inserted from top to bottom and left to right each time a new node is inserted. It is also possible to map the value of a node to the index of an array.
The subscript of the left child node of all nodes is: 2 x the subscript of the parent node + 1
The subscript of the child node on the right of all nodes is 2 x the subscript of the parent node + 2
The subscript of the parent of all nodes is: math.floor ((subscript -1 of the current node) / 2)
For example, node 1 is the first value, so its subscript is 0. The subscript of child node 2 on the left of node 1 is 2*0+1=1, and the subscript of child node 3 on the right of node 1 is 2*0+0=2.
Interpolation operation of minimum heap structure
Suppose we want to insert a value of 1 into the heap.
First it checks if there’s a value on the root node, and there’s a value of 2.
So I’m going to check if the child on the left has a value, and it has a value of 3.
And I’m going to check if the child on the right has a value of 4.
Then check whether the left child node of node 3 has a value of 5.
Then check whether the right child node of node 3 has a value. No, so insert the value 1 into the right child node of node 3.
Node 1 is then swapped with node 3, and node 2 is swapped with node 1. This completes the insertion of the new value into the minimal heap structure.
Minimum heap structure removal minimum value
Removing the minimum (minimum heap) or maximum (maximum heap) means removing the first element in the array (the root of the heap). After removal, we move the last element of the heap directly to the root node, and then slowly swap with the nodes below. Until the swap to the heap structure is normal.
For example, remove root node 1 from the smallest heap.
First, move the last node 9 directly from its original position to the root node,
Then node 9 is compared with the left child node 2, and 9 is greater than 2. After the switch, node 2 is in the position of the root node, and node 9 becomes the left child node of node 2.
Then node 9 continues to be compared with the left child node 4, 9 is greater than 4, and the position is switched, after which node 9 becomes the left child node of node 4.
Then node 9 continues to compare with the child node 8 on the left, 9 is greater than 8, and the position is switched. After the switch is completed, there is no smaller node below node 9, and the heap structure is normal.
Self-realization of minimum heap structure
class MinHeap{ // Since binary heaps are arranged in absolute order without any special structure, we can use an array-like structure because array subscripts are in ascending order
constructor() {
this.heap = []
}
getLeftIndex(index){ // Specify the index of the node
// The left child index of a node
return 2 * index + 1
}
getRightIndex(index){
return 2 * index + 2
}
getParentIndex(index){
if(index === 0) {// If it is the root node, it has no parent node
return undefined
}
// All that's left is the non-root case minus 1 or 2, minus 1 down, minus 2 up
return Math.floor((index-1) /2) // The parent of the left child is (i-1) /2, and the parent of the right child is (i-2) /2
}
insert(value){
if(value){
this.heap.push(value) // Add the value to the end of the array
// raise the smallest value in the array to the top
this.shiftUp(this.heap.length-1) // start from the last value
return true
}
// Return false if there is no value
return false
}
shiftUp(index){ / / file
let parentIndex = this.getParentIndex(index) // Get the parent node index
while(index > 0 && this.heap[parentIndex] > this.heap[index]){ // Keep swapping until you reach the top
this.swap(this.heap,parentIndex,index)
index = parentIndex
parentIndex = this.getParentIndex(index)
}
}
swap(arr,a,b){ / / exchange
let temp = arr[a]
arr[a] = arr[b]
arr[b] = temp
}
size(){
return this.heap.length
}
isEmpty(){
return this.heap.length === 0 / / method
// return this.size() === 0
}
findMinValue(){
return this.isEmpty()?undefined:this.heap[0]}extract(){ // Delete the top minimum value
if(this.isEmpty()){ // If it is null
return undefined
}
if(this.size() === 1) {return this.heap.shift()
}
let removeNode = this.heap[0] // Return the current minimum
this.heap[0] = this.heap.pop() // Move the largest one to the front
this.shiftDown(0) // Move the largest down
return removeNode
}
shiftDown(index){ // Move the maximum down again and again
let currentIndex = index
let leftIndex = this.getLeftIndex(index) // Get the left child node
let rightIndex = this.getRightIndex(index) // Get the right child node
let size = this.size() // When the index exceeds the length
if(leftIndex < size && this.heap[currentIndex] > this.heap[leftIndex]){
currentIndex = leftIndex
}
if(rightIndex < size && this.heap[currentIndex] > this.heap[rightIndex]){
currentIndex = rightIndex
}
if(currentIndex ! == index){this.swap(this.heap,currentIndex,index)
this.shiftDown(currentIndex) / / recursion}}}Copy the code