To read this article, you need to know:

  • Binary search tree (js version of the simple implementation can refer to binary search tree simple learning)
  • Get a pen and paper (draw it yourself so you can really understand it)

1. How does LiBUV use the least binary heap?

Libuv applied the algorithm of the least binary heap to timer. Let’s review the use of timer first:

uv_timer_t timer_handle; r = uv_timer_init(loop, &timer_handle); R = uv_timer_start(& timer_Handle, timer_cb, 10 * 1000, 10 * 1000);Copy the code

Every 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 code

When 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 code

Why 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 code

Libuv 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.Copy the code

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 indicates the index position of the parent node. Left = 2 * k + 1. Right = 2 * k + 2Copy the code

2.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 stable adjustment algorithms, the details are explained below.

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

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:

BubbleDown (array, parentIndex, length) {// bubbleDown(array, parentIndex, length)letChildIndex = parentIndex * 2 + 1 // The value of parentIndex is compared with its children and grandchildren until it finds its own locationlet temp = array[parentIndex]
  while (childIndex < length) {

    if(childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {childIndex += 1} // All children are larger than the parentif (temp <= array[childIndex]) {
      break} array[parentIndex] = array[childIndex] ParentIndex = childIndex childIndex = childIndex * 2 + 1} array[parentIndex] = temp}Copy the code

3.2. Adjust from the bottom up

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:

The code implementation is as follows:

BubbleUp (array) {// You can see that this upward adjustment is a child node looking for a parent nodelet childIndex = array.length - 1

  let parentIndex = Math.floor((childIndex - 1) / 2)

  letTemp = array[childIndex] // If the parent node is larger than the child node, continue upwardwhile(childIndex > 0 && array[parentIndex] > temp) {
    array[childIndex] = array[parentIndex]
    childIndex = parentIndex
    parentIndex = Math.floor((parentIndex - 1) / 2)
  }

  array[childIndex] = temp
}
Copy the code

Insert 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:

The insert

Insert (newNode) {this.heap.push(newNode) this.length.length.this.bubbleup (this.heap)}Copy the code

Delete operation

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.

remove() {// Delete binary heap refers to remove the root node, then self-stableif (this.length === 1) {
    return this.heap[0]
  }
  const lastEle = this.heap.pop()
  const top = this.heap[0]
  this.heap[0] = lastEle
  this.length--
  this.bubbleDown(this.heap, 0, this.length)
  return top
}
Copy the code

The complete code is shown below:

const array = [8, 10, 4342, 2, 34, 18, 11, 77, 16, 66]

class MinBinaryHeap {
  constructor(array) {
    this.heap = [...array]
    this.length = this.heap.length

    this.buildHeap()
  }
  buildHeap() {
    for(leti = Math.floor(this.length / 2) - 1; i >= 0; i -= 1) { this.bubbleDown(this.heap, i, this.length - 1) } } bubbleDown(array, parentIndex, Length) {// We can see that this downward adjustment is the parent node to find the child node behaviorletChildIndex = parentIndex * 2 + 1 // The value of parentIndex is compared with its children and grandchildren until it finds its own locationlet temp = array[parentIndex]
    while (childIndex < length) {

      if(childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {childIndex += 1} This position is the final position of the parent nodeif (temp <= array[childIndex]) {
        break} array[parentIndex] = array[childIndex] ParentIndex = childIndex childIndex = childIndex * 2 + 1} array[parentIndex] = temp} bubbleUp(array) {// You can see that this upward adjustment is the behavior of the child node to find the parent nodelet childIndex = array.length - 1

    let parentIndex = Math.floor((childIndex - 1) / 2)

    let temp = array[childIndex]
    while(childIndex > 0 && array[parentIndex] > temp) { array[childIndex] = array[parentIndex] childIndex = parentIndex ParentIndex = math. floor(parentindex-1) / 2)} array[childIndex] = temp} insert(newNode) { This.heap. push(newNode) this.length++ this.bubbleup (this.heap)}print() {
  	return this.heap
  }
  remove() {// Delete binary heap refers to remove the root node, then self-stableif (this.length === 1) {
    	return this.heap[0]
    }
    const lastEle = this.heap.pop()
    const top = this.heap[0]
    this.heap[0] = lastEle
    this.length--
    this.bubbleDown(this.heap, 0, this.length)
    return top
  }
  sort() {
  	const result = []
    let i = this.heap.length
    while (i > 0) {
    	result.push(this.remove())
      i -= 1
    }
    return result
  }
}

const heap = new MinBinaryHeap(array)
console.log(The least binary heap is:, heap.print())

heap.insert(5)

console.log('The minimum binary heap after insertion of 5 is:', heap.print())

heap.remove()

console.log('The minimum binary heap after removing the root node is:', heap.print())

console.log(Binary heap heap sort result:, heap.sort())

console.log(heap.print())
Copy the code

reference

  1. Js data Structure – Binary tree (binary heap)
  2. Maximum heap virtualization
  3. Virtualization of the minimum heap