javascript中的Max堆？
javascript中的Max堆？
提问于 2019-08-28 11:06:23
我正在尝试用javascript编写函数来创建一个最大堆，我的当前代码是
var arr = [5, 9, 6, 7, 1, 3, 8]
var heap = []
for (var i = 0; i < arr.length; i++) {
addtoheap(arr[i]);
}
function addtoheap(term) {
heap.push(term);
if (heap.length > 1) {
heapify(heap, (heap.length - 1))
}
console.log(heap);
}
function heapify(heap, i) {
if (i == 0) {
return;
}
if (heap[i] > heap[Math.floor(i / 2)]) {
var temp = heap[i];
console.log("Swapping" + heap[i] + "--" + heap[Math.floor(i / 2)]);
heap[i] = heap[Math.floor(i / 2)];
heap[Math.floor(i / 2)] = temp;
return heapify(heap, Math.floor(i / 2));
} else {
return;
}
}
它给出的输出
5 交换9-5 9，5 6-5 9、6、5 7-6 9、7、5、6 9、7、5、6、1、3 8--6 8--7 9、8、5、7、1、3、6
不知道我在这里做错了什么，有人能指出我逻辑上的错误吗？
预期输出:最大堆9,7,8,5,1,3,6
回答 1
Stack Overflow用户
发布于 2019-08-28 11:52:33
正如Prasun在注释中提到的，JS使用0的索引，算法使用从1开始的索引。
function heapify(heap,i){
if(i==0) return;
if(heap[i] > heap[Math.floor((i-1)/2)]) {
var temp = heap[i];
console.log("Swapping" +heap[i] +"--" + heap[Math.floor(i/2)]);
heap[i] = heap[Math.floor((i-1)/2)];
heap[Math.floor((i-1)/2)] = temp;
return heapify(heap,Math.floor((i-1)/2));
}
else return;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/57690978
复制相关文章
相似问题
腾讯云开发者
