You need knowledge to read this article
- 2. Prepare a pen and paper (draw it yourself, so you can really understand it)
1. How to use the least binary heap in LibuV?
Libuv applied the algorithm of the least binary heap to timer. Let’s take a look at the use of timer:
uv_timer_t timer_handle;
r = uv_timer_init(loop, &timer_handle);
// Call the timer callback every 10 seconds
r = uv_timer_start(&timer_handle, timer_cb, 10 * 1000.10 * 1000);
Copy the codeEvery time we call uv_timer_start, libuv inserts a timer message into the least binary heap, as follows:
int uv_timer_start(uv_timer_t* handle,
uv_timer_cb cb,
uint64_t timeout,
uint64_t repeat) {... . heap_insert(timer_heap(handle->loop), (struct heap_node*) &handle->heap_node, timer_less_than); . . }Copy the codeWhen uv_timer_stop is called, libuv removes a timer message:
int uv_timer_stop(uv_timer_t* handle) {
if(! uv__is_active(handle))return 0;
heap_remove(timer_heap(handle->loop),
(struct heap_node*) &handle->heap_node,
timer_less_than);
uv__handle_stop(handle);
return 0;
}
Copy the codeWhy use the least binary heap? Because it always puts the minimum value at the root node, and the minimum value here is the group that the timer first reaches the time point, so in order to query efficiency, such an algorithm is adopted:
void uv__run_timers(uv_loop_t* loop) {... .for (;;) {
heap_node = heap_min(timer_heap(loop));
if (heap_node == NULL)
break;
handle = container_of(heap_node, uv_timer_t, heap_node);
if (handle->timeout > loop->time)
break; . . }}Copy the codeLibuv minimum binary heap implementation source code here: heap-inl. H
Next, we start from libuv source code to learn the knowledge of the minimum binary heap, in order to make you not so strange, the C language implementation version of the conversion to Js version, we will explain the theory again, while the code implementation.
2. Basic concepts of binary heap
First, we need to know the definition of binary heap: binary heap is a complete binary tree, and the key value of any node is always less than or equal to the key value of its children.
So what is a complete binary tree? Let’s start by looking at what are the data structures for trees?
2.1. Complete binary tree
Is defined as:
For a binary tree of height H, if all nodes from layer 0 to layer H-1 are full. If the lowest layer of nodes is not enough, then all nodes are in a row on the left, and the empty space is on the right. Such a binary tree is a complete binary tree. As shown below:
Because of the unique nature of a complete binary tree, its data can be stored using arrays, without the need for a unique object to link the left and right nodes. Because the position of its left and right nodes has such a calculation relation with the position of its parent node:
K represents the index position of the parent node
left = 2 * k + 1
right = 2 * k + 2
Copy the code2.2. Minimum (large) binary heap
With complete binary trees, the magic data structure of binary heaps adds a hard condition: the key value of any node is always less (greater than) or equal to the key value of its children. Because its storage structure does not use the form of left and right nodes linked to each other, but uses a simple array, so it is called “heap”, but based on a complete binary tree, so the word “binary” is brought.
So with the above characteristics, when we insert or delete a value, in order to maintain the characteristics of binary heap, there are some binary heap stability adjustment algorithms (also called heap), detailed in the following.
3. Basic operation of binary heap
To understand the insert and delete operations of binary heap, we must first master two basic operations: one is to adjust the heap from the top down (Bubble Down), and the other is to adjust the heap from the bottom up (Bubble Up), which are respectively used for the delete and insert of binary heap.
3.1 Top-down adjustment (heapification)
In fact, this operation is based on the location of the parent node, search down the qualified child node, and keep swapping until the node is found to be larger than the parent node, as shown in the following diagram:
The implementation code is as follows:
// The heap process of the current node I
max_heapify(i) {
const leftIndex = 2 * i + 1 / / the left node
const rightIndex = 2 * i + 2 / / right node
let maxIndex = i // Current node I
// If there is a child node with more data than this node, then the swap is performed
if (leftIndex < this.heapSize && this.list[leftIndex] > this.list[maxIndex]) {
maxIndex = leftIndex
}
if (rightIndex < this.heapSize && this.list[rightIndex] > this.list[maxIndex]) {
maxIndex = rightIndex
}
if(i ! == maxIndex) { swap(this.list, maxIndex, i) // The maxIndex child node is swapped with the current node
// Adjust from the top down
this.max_heapify(maxIndex) // Build the heap on the child nodes recursively from the top down}}Copy the code3.2 Bottom-up adjustment (Heap building)
This adjustment is that when a new value is inserted, in order to ensure the characteristics of the binary heap, it is necessary to judge step by step from the newly inserted child node to the parent node, and keep changing positions until the whole binary heap meets the characteristics. The schematic diagram is as follows:
Here’s the core question: What is the sequence number of the last branch node?
The code implementation is as follows:
/ / build the heap
build() {
let i = Math.floor(this.heapSize / 2) - 1
while (i >= 0) {
// Adjust from bottom up, starting from the last branch node and adjusting from bottom up until all nodes are heaped
this.max_heapify(i--)
}
}
Copy the codeInsert and delete
With the above two operations, the implementation of insert and delete is a logical step. Just call the above two operations like this:
4.1 Insert Operations
// Add an element
insert(item) {
this.list.push(item);
this.heapSize++
this.build();
}
Copy the code4.2 Deleting a vm
The deletions here are all about removing the root node, then taking the number of the last node to the root node, and then adjusting the whole binary heap from top to bottom.
// Extract the first node of the maximum heap and restore the heap to the maximum heap
extract() {
if (this.heapSize === 0) return null
const item = this.list[0]
swap(this.list, 0.this.heapSize - 1)
this.heapSize--
this.max_heapify(0)
return item
}
Copy the codeThe complete code is shown below:
/ * * * * @ param array element exchange} {* A * @ param} {* I * @ param} {* j * /
function swap(A, i, j) {
const t = A[i]
A[i] = A[j]
A[j] = t
}
/** * Max */
class MaxHeap {
constructor(data) {
this.list = [...data]
for (let i = 0; i < data.length; i++) {
this.list[i] = data[i]
}
this.heapSize = data.length
this.build()
}
/ / build the heap
build() {
let i = Math.floor(this.heapSize / 2) - 1
while (i >= 0) {
// Adjust from bottom up, one loop per node
this.max_heapify(i--)
}
}
// Maximum [heap]
max_heapify(i) {
const leftIndex = 2 * i + 1
const rightIndex = 2 * i + 2
let maxIndex = i
if (leftIndex < this.heapSize && this.list[leftIndex] > this.list[maxIndex]) {
maxIndex = leftIndex
}
if (rightIndex < this.heapSize && this.list[rightIndex] > this.list[maxIndex]) {
maxIndex = rightIndex
}
if(i ! == maxIndex) { swap(this.list, maxIndex, i)
// Adjust from the top down
this.max_heapify(maxIndex)
}
}
// Extract the first node of the maximum heap and restore the heap to the maximum heap
extract() {
if (this.heapSize === 0) return null
const item = this.list[0]
swap(this.list, 0.this.heapSize - 1)
this.heapSize--
this.max_heapify(0)
return item
}
// Add an element
insert(item) {
this.list.push(item);
this.heapSize++
this.build();
}
print() {
return JSON.stringify(this.list)
}
size() {
return this.list.length;
}
/ / heap sort
sort() {
const result = []
let i = this.heapSize
while ( i > 0) {
result.push(heap.extract())
i--
}
return result
}
}
const array = [12.15.2.4.3.8.7.6.5]
const heap = new MaxHeap(array)
console.log('The largest heap is:', heap.print())
heap.insert(9)
console.log('The largest heap after 9 is:', heap.print())
heap.extract()
console.log('The largest heap after removing the root node is:', heap.print())
console.log(Binary heap heap sort result:, heap.sort())
console.log(heap.print())
Copy the codeReference this article is mainly reference from libuv source code learning minimum binary heap, their own implementation of a time for recording