Introduction to binary trees (binary heaps) in JavaScript (code examples)

This article brings you an introduction (code example) about binary trees (binary heaps) in JavaScript. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Binary Tree

Binary Tree (Binary Tree) is a tree structure. Its characteristic is that each node has at most two branch nodes. A binary tree usually consists of It consists of root node, branch node and leaf node. Each branch node is often called a subtree.

• Root node: the top node of the binary tree

• Branch node: In addition to the root node and has leaf nodes

• Leaf node: except itself, has no other child nodes

Common terms

In a binary tree, we often use parent nodes and child nodes to describe it. For example, 2 in the figure is the parent node of 6 and 3, and conversely 6 and 3 are the child nodes of 2

Three properties of binary trees

1. ##On the i-th level of the binary tree, there are at most 2^i-1 nodes

• When i=1, there is only one root node, 2^(i-1) = 2^0 = 1

• When i=2, 2^k-1 = 2^2 - 1 = 3 nodes

• The number of nodes of a tree is at least 1, while the number of nodes of a binary tree can be 0

• There is no limit to the maximum degree (number of nodes) of a node in a tree, while the maximum degree of a node in a binary tree is 2

• There is no left or right distinction between the nodes of a tree, while the nodes of a binary tree There are left and right sides

• Full binary tree: A binary tree with depth k and 2^k - 1 nodes is called a full binary tree

• Complete binary tree: A complete binary tree refers to the left side of the last layer It is full, the right side may be full or not full, and the remaining levels are full. The binary tree is called a complete binary tree (a full binary tree is also a complete binary tree)

• left = index * 2 1, for example: the subscript of the root node is 0, then the value of the left node is the subscript array[0＊2 1]=1

• right = index * 2 2, for example: the subscript of the root node is 0, then the value of the right node is the subscript array[0*2 2]=2

• Ordinal>= floor(N/2) are all leaf nodes, for example: floor(9/2) = 4, then the values ​​starting from subscript 4 are all leaf nodes

• The key value of the parent node of the binary heap is always greater than or equal to (less than or equal to) the key value of any child node

• When the key value of the parent node is greater than or equal to ( Less than or equal to) the key value of each of its child nodes, it is called

  max heap (minimum heap)

  

• Left picture: The parent node is always greater than or equal to its child node , so it satisfies the properties of a binary heap,

• Right picture: Branch node 7, as the parent node of 2 and 12, does not satisfy its properties (greater than or equal to the child node).

• insert: insert node

• delete: delete node

• max-hepify: Adjust branch node heap properties

• rebuildHeap: Rebuild the entire binary heap

• sort: Sort

• Initialize an array structure

• Save the array length

    class Heap{
        constructor(arr){
            this.data = [...arr];
            this.size = this.data.length;
        }
    }

max-heapify maximum heap operation

max-heapify is to convert each item that does not satisfy the maximum heap properties An operation for adjusting branch nodes.

As shown above:

1. Adjust branch node 2 (branch node 2 does not meet the properties of the maximum heap )

• By default, the branch node is the maximum value

• According to the binary heap properties above, get the left node and right node of branch node 2 respectively

• Compare three nodes and get the subscript max of the maximum value

• If the node itself is the maximum value, stop the operation

• Exchange the max node with the parent node

• Recursion

    maxHeapify(i) {
        let max = i;
        
        if(i >= this.size){
            return;
        }
        // 当前序号的左节点
        const l = i * 2 + 1;
        // 当前需要的右节点
        const r = i * 2 + 2;
        
        // 求当前节点与其左右节点三者中的最大值
        if(l  this.data[max]){
            max = l;
        }
        if(r  this.data[max]){
            max = r;
        }
        
        // 最终max节点是其本身,则已经满足最大堆性质，停止操作
        if(max === i) {
            return;
        }
        
        // 父节点与最大值节点做交换
        const t = this.data[i];
        this.data[i] = this.data[max];
        this.data[max] = t;
        
        // 递归向下继续执行
        return this.maxHeapify(max);
    }

Reconstructing the heap

We can see that the newly initialized heap Represented by an array, at this time it may not satisfy the properties of a maximum heap or a minimum heap. At this time, we may need to build the entire heap into what we want.
We did the max-heapify operation above, and max-heapify only adjusts a certain branch node. To build the entire heap into a maximum heap, you need to perform a max-heapify operation on all branch nodes. As shown in the figure below, we need to perform max-hepify operations on the four branch nodes 12, 3, 2, and 15 in sequence

• Find all branch nodes: The properties of the heap mentioned above mentioned that the serial number of the leaf node>=Math.floor(n/2), so it is smaller than the serial number of Math.floor(n/2) These are all nodes we need to adjust.

• For example, the array shown in the middle is [15,2,3,12,5,2,8,4,7] => Math.floor(9/2 )=4 => Those with index less than 4 are 15, 2, 3, and 12 (nodes that need to be adjusted), while 5, 2, 8, 4, and 7 are leaf nodes.

• Perform maxHeapify operation on all found nodes

    rebuildHeap(){
        // 叶子节点
        const L = Math.floor(this.size / 2);
        for(let i = L - 1; i>=0; i--){
            this,maxHeapify(i);
        }
    }

• Exchange the first and last positions

• Change the last The element is taken out from the heap, which is equivalent to the size-1 of the heap

• Then perform a max-heapify operation on the root node of the heap

• Repeat In the above three steps, we know that size=0 (we have already done this boundary condition in the max-heapify function)

    sort() {
        for(let i = this.size - 1; i > 0; i--){
            swap(this.data, 0, i);
            this.size--;
            this.maxHeapify(0);
        }
    }

• Insert to the end

• Heap length 1

• Determine whether it is still a maximum heap after insertion

• If not, reconstruct the heap

  insert(key) {
    this.data[this.size] = key;
    this.size++
    if (this.isHeap()) {
      return;
    }
    this.rebuildHeap();
  }

• Delete an element in the array

• Heap length-1

• Determine whether it is a heap

• If not, then reconstruct the heap

  delete(index) {
    if (index >= this.size) {
      return;
    }
    this.data.splice(index, 1);
    this.size--;
    if (this.isHeap()) {
      return;
    }
    this.rebuildHeap();
  }

/**
 * 最大堆
 */

function left(i) {
  return i * 2 + 1;
}

function right(i) {
  return i * 2 + 2;
}

function swap(A, i, j) {
  const t = A[i];
  A[i] = A[j];
  A[j] = t;
}

class Heap {
  constructor(arr) {
    this.data = [...arr];
    this.size = this.data.length;
  }

  /**
   * 重构堆
   */
  rebuildHeap() {
    const L = Math.floor(this.size / 2);
    for (let i = L - 1; i >= 0; i--) {
      this.maxHeapify(i);
    }
  }

  isHeap() {
    const L = Math.floor(this.size / 2);
    for (let i = L - 1; i >= 0; i++) {
      const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER;
      const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER;

      const max = Math.max(this.data[i], l, r);

      if (max !== this.data[i]) {
        return false;
      }
      return true;
    }
  }

  sort() {
    for (let i = this.size - 1; i > 0; i--) {
      swap(this.data, 0, i);
      this.size--;
      this.maxHeapify(0);
    }
  }

  insert(key) {
    this.data[this.size++] = key;
    if (this.isHeap()) {
      return;
    }
    this.rebuildHeap();
  }

  delete(index) {
    if (index >= this.size) {
      return;
    }
    this.data.splice(index, 1);
    this.size--;
    if (this.isHeap()) {
      return;
    }
    this.rebuildHeap();
  }

  /**
   * 堆的其他地方都满足性质
   * 唯独跟节点，重构堆性质
   * @param {*} i
   */
  maxHeapify(i) {
    let max = i;

    if (i >= this.size) {
      return;
    }

    // 求左右节点中较大的序号
    const l = left(i);
    const r = right(i);
    if (l  this.data[max]) {
      max = l;
    }

    if (r  this.data[max]) {
      max = r;
    }

    // 如果当前节点最大，已经是最大堆
    if (max === i) {
      return;
    }

    swap(this.data, i, max);

    // 递归向下继续执行
    return this.maxHeapify(max);
  }
}

module.exports = Heap;

Copy after login

The above is the detailed content of Introduction to binary trees (binary heaps) in JavaScript (code examples). For more information, please follow other related articles on the PHP Chinese website!