javascript - javascript中的最大堆？

Question

我正在尝试编写用于在 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 ]
[ 9, 7, 5, 6, 1, 3 ]
交换8--6 交换
8--7
[ 9, 8, 5, 7, 1, 3, 6 ]

不知道我在这里做错了什么，有人可以指出我的逻辑错误吗？

预期输出：最大堆 [9,7,8,5,1,3,6]

标签： javascriptalgorithmsortingheapmax-heap

Answer 1

正如 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;
    }    
}