Я читал о кучах и видел различные реализации в javascript. https://codepen.io/beaucarnes/pen/JNvENQ?editors=0010 хороший пример вставки и удаления. Однако я хочу написать создание максимальной кучи рекурсивным способом. Например, в C++ следующий код должен помочь:
// C++ program for building Heap from Array
#include <iostream>
using namespace std;
// To heapify a subtree rooted with node i which is
// an index in arr[]. N is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Function to build a Max-Heap from the given array
void buildHeap(int arr[], int n)
{
// Index of last non-leaf node
int startIdx = (n / 2) - 1;
// Perform reverse level order traversal
// from last non-leaf node and heapify
// each node
for (int i = startIdx; i >= 0; i--) {
heapify(arr, n, i);
}
}
источник: https://www.geeksforgeeks.org/building-heap-from-array/ Проблема в том, что когда я перевожу его на javascript:
function build_max_heap( A, n) {
let start_index = Math.floor(n/2);
for (let i=start_index; i>=0; i--){
heapify(A, n, i);
}
}
function heapify(A, n, i){
let left = 2 * i;
let right = 2 * i + 1;
let largest = i;
if (A[left] > A[largest]) largest = left;
if (A[right] > A[largest]) largest = right;
if (largest !== i) swap(A[i], A[largest]);
heapify(A, n, largest)
}
function swap (A, x, y){
let c = x;
x = y;
y = c;
}
Я получаю эту ошибку:
VM56:2 Uncaught RangeError: Maximum call stack size exceeded
at heapify (<anonymous>:2:20)
at heapify (<anonymous>:10:9)
at heapify (<anonymous>:10:9)
at heapify (<anonymous>:10:9)
at heapify (<anonymous>:10:9)
at heapify (<anonymous>:10:9)
at heapify (<anonymous>:10:9)
at heapify (<anonymous>:10:9)
at heapify (<anonymous>:10:9)
at heapify (<anonymous>:10:9)
```
Can anyone help me figure out what's wrong with my implementation?
Несколько вопросов:
(1) У вас есть ошибка в этой части:
let left = 2 * i;
let right = 2 * i + 1;
Это неправильно. Представьте себе индекс корня, которым является i=0
, каким будет значение left
? Опять 0... этого не может быть. Правильная формула находится в коде, который вы цитировали ранее:
let left = 2 * i + 1;
let right = 2 * i + 2;
(2) Вторая ошибка возникает в строке, где вы вызываете swap
. Вы не передаете правильные аргументы. Ожидается 3: A
, а затем два индекса. Вы передаете два значения. Должно быть (см. также следующий пункт):
swap(A, i, largest);
(3) И тогда функция swap
имеет неправильную реализацию (JavaScript имеет вызов только по значению). Изменение x
или y
внутри этой функции не влияет на массив. Это должно быть так:
function swap (A, x, y){
let c = A[x];
A[x] = A[y];
A[y] = c;
}
(4) Наконец, рекурсивный вызов функции heapify
должен выполняться только в том случае, если сделан обмен:
if (largest !== i) {
swap(A, i, largest);
heapify(A, n, largest)
}
Исправлен код во фрагменте:
function build_max_heap( A, n) {
let start_index = Math.floor(n/2);
for (let i=start_index; i>=0; i--){
heapify(A, n, i);
}
}
function heapify(A, n, i){
let left = 2 * i + 1;
let right = 2 * i + 2;
let largest = i;
if (A[left] > A[largest]) largest = left;
if (A[right] > A[largest]) largest = right;
if (largest !== i) {
swap(A, i, largest);
heapify(A, n, largest)
}
}
function swap (A, x, y) {
let c = A[x];
A[x] = A[y];
A[y] = c;
}
// example call
let A = [4, 3, 2, 1, 5, 9, 8, 7, 6];
build_max_heap(A, A.length);
console.info(A.join());