Detailed explanation of the JavaScript implementation method of heap

Definition of heap

A maximum (minimum) heap is a tree in which the key value of each node is not less than (greater than) the key value of its child (if it exists). The big heap is a complete binary tree and is also a maximum tree. The mini-heap is a completely binary tree and also a minimal tree.

In addition, remembering these two concepts is very important for writing code:

1. The relationship between parent nodes and child nodes: see the definition

2. Complete binary tree: refer to [2]

Basic operations

1. Build (build heap)

2. Insert

3. Delete (delete: the smallest or largest one)

Code implementation

First of all, there are two very important things before writing code Points:

1. An array can be used as the storage structure of the heap, which is very simple and easy to operate; 2. In addition, because the array is used as the storage structure, the relationship between parent and child nodes can be determined based on the index. Found each other easily.

For JavaScript, starting with 0 as the array index, the relationship is as follows:

nLeftIndex = 2 * (nFatherIndex+1) - 1;
nRightIndex = 2* (nFatherIndex+1);

As mentioned earlier, it is helpful to pay attention to two concepts:

1. Because it is an array, the relationship between parent and child nodes There is no need for a special structure to maintain. It can be obtained through calculation between indexes, saving a lot of trouble. If it is a linked list structure, it will be much more complicated;

2. The concept of a complete binary tree can be referred to [2]. The leaf nodes are required to be filled from left to right before the next layer can be filled. This ensures that there is no need to modify the array Make large movements as a whole. This is also a shortcoming of random storage structures (arrays): after deleting an element, it is more time-consuming to move the entire element forward. This feature also causes the heap to add the last leaf node to the root node when deleting elements. Code implementation:

/******************************************************
* file : 堆
* author : "page"
* time : "2016/11/02"
*******************************************************/
function Heap()
{
 this.data = [];
}
 
Heap.prototype.print = function () {
 console.log("Heap: " + this.data);
}
 
Heap.prototype.build = function(data){
 // 初始化
 this.data = [];
 if (!data instanceof Array)
 return false;
 
 // 入堆
 for (var i = 0; i < data.length; ++i) {
 this.insert(data[i]);
 }
 
 return true;
}
 
Heap.prototype.insert = function( nValue ){
 if (!this.data instanceof Array) {
 this.data = [];
 }
 
 this.data.push(nValue);
 // 更新新节点
 var nIndex = this.data.length-1;
 var nFatherIndex = Math.floor((nIndex-1)/2);
 while (nFatherIndex > 0){
 if (this.data[nIndex] < this.data[nFatherIndex]) {
 var temp = this.data[nIndex];
 this.data[nIndex] = this.data[nFatherIndex];
 this.data[nFatherIndex] = temp;
 }
 
 nIndex = nFatherIndex;
 nFatherIndex = Math.floor((nIndex-1)/2);
 }
}
 
Heap.prototype.delete = function( ){
 if (!this.data instanceof Array) {
 return null;
 }
 
 var nIndex = 0;
 var nValue = this.data[nIndex];
 var nMaxIndex = this.data.length-1;
 // 更新新节点
 var nLeaf = this.data.pop();
 this.data[nIndex] = nLeaf;
 
 while (nIndex < nMaxIndex ){
 var nLeftIndex = 2 * (nIndex+1) - 1;
 var nRightIndex = 2 * (nIndex+1);
 
 // 找最小的一个子节点(nLeftIndex < nRightIndex)
 var nSelectIndex = nLeftIndex;
 if (nRightIndex < nMaxIndex) {
 nSelectIndex = (this.data[nLeftIndex] > this.data[nRightIndex]) ? nRightIndex : nLeftIndex;
 }
 
 if (nSelectIndex < nMaxIndex && this.data[nIndex] > this.data[nSelectIndex] ){
 var temp = this.data[nIndex];
 this.data[nIndex] = this.data[nSelectIndex];
 this.data[nSelectIndex] = temp;
 }
 
 nIndex = nSelectIndex;
 }
 
 return nValue;
}
// test
var heap = new Heap();
heap.build([1, 3, 5, 11, 4, 6, 7, 12, 15, 10, 9, 8]);
heap.print();
// insert
heap.insert(2);
heap.print();
// delete
heap.delete();
heap.print();

Some summary about JavaScript

Here are the oriented An implementation method of objects, it doesn’t feel too elegant. I don’t know if there is a better way of expressing and writing;

I learned several uses of arrays: the push and pop operations are so easy to use;

The method of judging arrays was also temporarily searched from the Internet (instanceof). I was not very impressed. If I don’t use it, I will probably forget it next time.

Reference

[1] "Data Structure and Algorithm Analysis: C Language Description"

[2] Graphical Data Structure (8) - Binary Heap

[3]>Data Structure: Heap

Summary

JavaScript’s array implements push and pop operations. Many other languages ​​also provide similar data structures and operations (such as C++’s Vector), and also support random operations. So, I began to think that if the concept of automatic sorting is simply added to these structures, then a heap can be easily solved. Later, when I saw the make_heap of C++ STL, I realized that I knew too little, but I was glad that my way of thinking was right. of. I didn’t check JavaScript, I think it exists or it is easy to implement;

After I implemented it myself, I found that this structure is also very simple, as long as you are willing to get in close contact with it once;

The details of JavaScript are still not there I know too much about it. For example, you need to read more information about the application of arrays before you can use it; I still haven’t come into contact with the soul of JavaScript, and the essence requires continuous learning and practice;

These codes, as long as you understand the concepts and programming The basics can be written out. However, the code can be written more concisely. For example, when the delete function finds the smallest child node, the indexes of the left and right nodes do not need to be compared. The one on the left must be smaller. It feels like the code part can still be optimized and streamlined.