Рекурсивная реализация maxHeap в Javascript

Я читал о кучах и видел различные реализации в 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? 
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
В настоящее время производительность загрузки веб-сайта имеет решающее значение не только для удобства пользователей, но и для ранжирования в...
Безумие обратных вызовов в javascript [JS]
Безумие обратных вызовов в javascript [JS]
Здравствуйте! Юный падаван 🚀. Присоединяйся ко мне, чтобы разобраться в одной из самых запутанных концепций, когда вы начинаете изучать мир...
Система управления парковками с использованием HTML, CSS и JavaScript
Система управления парковками с использованием HTML, CSS и JavaScript
Веб-сайт по управлению парковками был создан с использованием HTML, CSS и JavaScript. Это простой сайт, ничего вычурного. Основная цель -...
JavaScript Вопросы с множественным выбором и ответы
JavaScript Вопросы с множественным выбором и ответы
Если вы ищете платформу, которая предоставляет вам бесплатный тест JavaScript MCQ (Multiple Choice Questions With Answers) для оценки ваших знаний,...
0
0
175
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Несколько вопросов:

(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());

Другие вопросы по теме