js实现的大根堆算法(基于链式的m叉树)

本文主要是介绍js实现的大根堆算法(基于链式的m叉树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

面向过程版本

var COUNT = 3;
/*获取待排序数据，数据的个数和值随机生成
*/
function getData() {var arr = [];var i = 0;var len = Math.max(10, ~~(Math.random() * 30 ));while(i <  len) {arr.push(~~(Math.random() * 100 ));i++;}   return arr;
}
/*节点构造函数@param val {any} 节点的值@param position {int} 节点的位置，即第几个节点
*/
function Node(val, position) {// 叉数，例如二叉树var count = COUNT;// 初始化节点的孩子为nullwhile(count) {this[count--] = null;}this.position = position;// 父节点、前继节点、后继节点this.parent = null;this.pre = null;this.next = null;// 孩子个数this.childs = 0;this.val = val;
}
/*构造COUNT叉树
*/
function makeTree(arr) {var i = 1;var root = new Node(arr[0], 0);var position = 1;var count = COUNT;// 初始化队列var queue = [root];// 保存上一个遍历的节点，用于前后节点的连接var preNodePtr;// 构造m叉树完成后，从哪个节点开始遍历这棵树，从最后一个非叶子节点开始var neededNode;// 是否已经找到了最后一个非叶子节点var isFind = false;// 用于寻找最后的非叶子节点var preNode = root;// 利用队列进行广度遍历while(queue.length) {var node = queue.shift();i = 1;// 给当前节点配置孩子数据，个数为COUNTwhile(i <= count) {// 判断当前的节点数是否已经超过数据的长度if (position < arr.length) {var newNode = new Node(arr[position], position);node[i] = newNode;newNode.parent = node;newNode.pre = preNode;preNode.next = newNode;node.childs++;queue.push(newNode);preNode = newNode;i++;position++;} // 全部数据赋值完成else {break;}}// 是否找到了最后的非叶子节点if (!isFind) {// 当前节点的孩子数为0，说明前一节点为最后一个非叶子节点if (node.childs === 0) {neededNode = preNodePtr;isFind = true;return {root: root,startNode: neededNode};} // 当前节点的孩子数小于分支数COUNT，说明当前节点为最后的非叶子节点else if (node.childs < COUNT){neededNode = node;isFind = true;return {root: root,startNode: neededNode};}// 保存前一个节点else {preNodePtr = node;}}}return root;
}
// 找出一棵树的最后非叶子节点，已经在makeTree里实现
function findNode(root) {var queue = [root];var node;var count = COUNT;var i = 1;var preNodePtr;while(queue.length) {node = queue.shift();if (node.childs === 0) {return preNodePtr;} else if (node.childs < COUNT) {return node;}preNodePtr = node;while(i <= count) {queue.push(node[i++]);}count = COUNT;  }
}
// 根据一颗无序的m叉树构建m叉大堆树
function buildHeapTree(root, startNode) {var node = startNode;// 从最后一个非叶子节点开始，到根节点结束，遍历其中的所有节点，调整成m叉堆的形式，最后根节点为值最大的节点while(node) {adjustHeapTree(node);node = node.pre;}return root;
}
// 以node节点为根节点，endNode为结束节点。把node子树调整成m叉堆，
function adjustHeapTree(node, endNode) {var i = 1;var max = node.val;var position = 0;var isEnd = false;while(i <= COUNT) {// 是否已经到达了结束节点，是则结束所有步骤if (endNode && node[i] && node[i].position >= endNode.position) {isEnd = true;break;}// 找到node节点和孩子中的最大值。if (node[i] && node[i].val > max) {max = node[i].val;position = i;}i++;}var temp;// 如果node节点的值不是最大的，那么和值最大的孩子节点进行值的互换if (position !== 0) {temp = node.val;node.val = node[position].val;node[position].val = temp;/*是否已经到达结束节点，是的话不需要再进行调整后续的子树，因为孩子节点的position和父节点的大以被置换值的孩子节点为根节点，调整成m叉树   */!isEnd && adjustHeapTree(node[position], endNode);}   
}/*对排序的主流程
*/
function heapSort(root, startNode) {if (!root.childs) {return;}var node = startNode;// 获取整个树的最后一个节点，即最后一个非叶子节点的最后一个节点var lastChild = getNodeLastChild(node);var endNode = lastChild;var temp;// 首先构建m叉堆buildHeapTree(root, startNode);while(endNode !== root) {// 把m叉堆中值最大的节点，即根节点的值和最后一个孩子的值互换temp = root.val;root.val = endNode.val;endNode.val = temp;// 以根节点为起点，endNode为终点，调整子树为m叉堆adjustHeapTree(root, endNode);// 终点根节点方向，往前挪一位，此时，endNode后面的节点都是有序的endNode = endNode.pre;}
}
// 或许某个节点的最后一个孩子节点
function getNodeLastChild(node) {var count = COUNT;while(count) {if (node[count]) {return node[count];}count--;}return null;
}
// 广度遍历root为根节点的m叉树
function echo(root) {var queue =[root];var result = [];var i = 1;while(queue.length) {i = 1;var node = queue.shift();result.push(node.val);while(i <= node.childs) {queue.push(node[i++]);}}console.log('sort: data',JSON.stringify(result),'\n');return result;
}
// 断言堆排序算法产生的数据是升序的
function assert(result) {var i = 0;while(i < result.length - 2) {if (result[i] > result[i+1]) {console.log('error',i, result,'\n');break;}i++;}
}
function start() {var data = getData();console.log('source data:',JSON.stringify(data));var {root, startNode} = makeTree(data);heapSort(root, startNode);assert(echo(root));
}
start();

粗糙的面向对象版本

function HeapSort(count) {this.data = [];this.COUNT = count || 2;
}HeapSort.prototype = {getData: function() {var arr = [];var i = 0;var len = Math.max(10, ~~(Math.random() * 30 ));while(i <  len) {arr.push(~~(Math.random() * 100 ));i++;}   this.data = arr;return arr;},makeTree: function makeTree() {var arr = this.data;var i = 1;var root = this.getNode(arr[0], 0);var position = 1;var count = this.COUNT;var queue = [root];var preNodePtr;var neededNode;var isFind = false;var preNode = root;while(queue.length) {var node = queue.shift();i = 1;while(i <= count) {if (position < arr.length) {var newNode = this.getNode(arr[position], position);node[i] = newNode;newNode.parent = node;newNode.pre = preNode;preNode.next = newNode;node.childs++;queue.push(newNode);preNode = newNode;i++;position++;} else {break;}}if (!isFind) {if (node.childs === 0) {neededNode = preNodePtr;isFind = true;this.startNode = neededNode;this.root = root;} else if (node.childs < this.COUNT){neededNode = node;isFind = true;this.startNode = neededNode;this.root = root;} else {preNodePtr = node;}}}return root;},findNode: function findNode(root) {var queue = [root];var node;var count = COUNT;var i = 1;var preNodePtr;while(queue.length) {node = queue.shift();if (node.childs === 0) {return preNodePtr;} else if (node.childs < this.COUNT) {return node;}preNodePtr = node;while(i <= count) {queue.push(node[i++]);}count = this.COUNT; }},buildHeapTree: function buildHeapTree() {var node = this.startNode;while(node) {this.adjustHeapTree(node);node = node.pre;}},adjustHeapTree: function adjustHeapTree(node, endNode) {var i = 1;var max = node.val;var position = 0;var isEnd = false;while(i <= this.COUNT) {if (endNode && node[i] && node[i].position >= endNode.position) {isEnd = true;break;}if (node[i] && node[i].val > max) {max = node[i].val;position = i;}i++;}var temp;if (position !== 0) {temp = node.val;node.val = node[position].val;node[position].val = temp;!isEnd && this.adjustHeapTree(node[position], endNode);}   },heapSort: function heapSort() {if (!this.root.childs) {return;}var root = this.root;var node = this.startNode;var lastChild = this.getNodeLastChild(node);var endNode = lastChild;var temp;this.buildHeapTree();while(endNode !== root) {temp = root.val;root.val = endNode.val;endNode.val = temp;this.adjustHeapTree(root, endNode);endNode = endNode.pre;}},getNodeLastChild: function getNodeLastChild(node) {var count = this.COUNT;while(count) {if (node[count]) {return node[count];}count--;}return null;},echo: function echo() {var queue =[this.root];var result = [];var i = 1;while(queue.length) {i = 1;var node = queue.shift();result.push(node.val);while(i <= node.childs) {queue.push(node[i++]);}}this.result = result;console.log('sort: data',JSON.stringify(result),'\n');},assert: function assert() {var result = this.result;var i = 0;while(i < result.length - 2) {if (result[i] > result[i+1]) {console.log('error',i, result,'\n');break;}i++;}},start: function start() {this.getData();console.log('source data:',JSON.stringify(this.data));this.makeTree();this.heapSort();this.echo();this.assert();},getNode(val, position) {var node = {};var count = this.COUNT;while(count) {node[count--] = null;}node.position = position;node.parent = null;node.pre = null;node.next = null;node.childs = 0;node.val = val;return node;}
}
new HeapSort().start();

算法正确性验证

var end = 10000;
var i = 0;
var time = setInterval(function() {if (i > end) {clearInterval(time);}i++;start();//new HeapSort().start();
},10)

算法性能比较

// 插入排序 
function insertSort(arr) {
for (var i = 1;i<arr.length;i++) {
var j=i-1;
var key = arr[i];
while (j>=0 && key<arr[j]) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}// 希尔排序
function shellSortRecursion(arr,step) {if(step<1) {return;}for (var i = step;i<arr.length;i++) {var j = i-step;var key = arr[i];while (j>=0 && key<arr[j]) {arr[j+step] = arr[j];j-=step;}arr[j+step] = key;}step = Math.floor(step/2);shellSortRecursion(arr,step);
}function start() {var data = getData();var start = new Date().getTime();var {root, startNode} = makeTree(data);heapSort(root, startNode);//insertSort(data)//shellSortRecursion(data,5)console.log((new Date().getTime() - start)/1000);
}
start();