Heapsort не работает в Javascript

Question

Я пытаюсь реализовать heapsort в Javascript, но есть undefined элемент в array.length - 2 и элемент с индексом 0 не отсортирован. Вот код:

var heapSort = function(array) {
  var swap = function(array, firstIndex, secondIndex) {
    var temp = array[firstIndex];
    array[firstIndex] = array[secondIndex];
    array[secondIndex] = temp;
  };
  var maxHeap = function(array, i) {
    var l = 2 * i;
    var r = l + 1;
    var largest;
    if (l <= array.heapSize && array[l] > array[i]) {
      largest = l;
    } else {
      largest = i;
    }
    if (r <= array.heapSize && array[r] > array[largest]) {
      largest = r;
    }
    if (largest != i) {
      swap(array, i, largest);
      maxHeap(array, largest);
    }
  };
  var buildHeap = function(array) {
    array.heapSize = array.length;
    for (var i = Math.floor(array.length / 2); i >= 1; i--) {
      maxHeap(array, i);
    }
  };
  buildHeap(array);
  for (var i = array.length; i >= 2; i--) {
    swap(array, 1, i);
    array.heapSize--;
    maxHeap(array, 1);
  }
};
var a = [55, 67, 10, 34, 25, 523, 1, -2];
heapSort(a);
document.getElementById("getHeapSort").innerHTML = a;

* {
  font-family: Arial, sans-serif;
}

<p id="getHeapSort"></p>

Я понял что array[i] == undefined когда i = array.length, Я попытался исправить это (настройка i = array.length - 1 ), но массив вышел в совершенно ином порядке. Я также подумал, что 0 никогда не менялся местами, потому что я всегда больше 0. Снова, я попробовал, и массив вышел в совершенно другом порядке.

Answer 1

Вы использовали индексацию на основе 1 вместо индексации на основе 0 в JavaScript. Я также добавил след для вашего удобства.

Попробуй это:

var heapSort = function(array) {
  var swap = function(array, firstIndex, secondIndex) {
    var temp = array[firstIndex];
    array[firstIndex] = array[secondIndex];
    array[secondIndex] = temp;
  };
  var maxHeap = function(array, i) {
    var l = 2 * i;
    var r = l + 1;
    var largest;
    if (l < array.heapSize && array[l] > array[i]) {
      largest = l;
    } else {
      largest = i;
    }
    if (r < array.heapSize && array[r] > array[largest]) {
      largest = r;
    }
    if (largest != i) {
      swap(array, i, largest);
      maxHeap(array, largest);
    }
  };
  var buildHeap = function(array) {
    array.heapSize = array.length;
    for (var i = Math.floor(array.length / 2); i >= 0; i--) {
      maxHeap(array, i);
    }
  };
  buildHeap(array);
  for (var i = array.length-1; i >= 1; i--) {
    swap(array, 0, i);
    array.heapSize--;
    maxHeap(array, 0);

    document.getElementById("getHeapSort").innerHTML = document.getElementById("getHeapSort").innerHTML + a + "<br>";
  }
};
var a = [55, 67, 10, 34, 25, 523, 1, -2];
document.getElementById("getHeapSort").innerHTML = a + "<br>";
heapSort(a);

Вот JFiddle: http://jsfiddle.net/mbL5enL5/1/