Home >Web Front-end >JS Tutorial >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
max heap (minimum heap)
Save the array length
class Heap{
constructor(arr){
this.data = [...arr];
this.size = this.data.length;
}
}
max-heapify is to convert each item that does not satisfy the maximum heap properties An operation for adjusting branch nodes.
As shown above:
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
Compare 2 with the left and right branches, from 2, 12, Find the maximum value in 5, and then exchange the position with 2
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
Repeat the operation of step 2, find the maximum value from 2, 4, and 7 and exchange it with 2
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);
}
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
rebuildHeap(){
// 叶子节点
const L = Math.floor(this.size / 2);
for(let i = L - 1; i>=0; i--){
this,maxHeapify(i);
}
}Maximum heap sort
sort() {
for(let i = this.size - 1; i > 0; i--){
swap(this.data, 0, i);
this.size--;
this.maxHeapify(0);
}
}Insertion and deletionThe insertion and deletion of this Deletion is relatively simple, it is the operation of inserting and deleting an array
insert(key) {
this.data[this.size] = key;
this.size++
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();
}Complete code/**
* 最大堆
*/
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;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!