Мин куча в javascript

Привет, я попытался реализовать минимальную кучу в javascript, но у меня возник вопрос относительно алгоритма удаления min. Я использую массив для внутреннего представления кучи. Когда я просачиваюсь вниз, каким должно быть условие остановки? В моем коде он равен 2 * k ‹= this.size, поэтому он может перейти к потенциально самому последнему элементу, но он не кажется« правильным », есть ли лучшее условие остановки? Заранее спасибо!

this.removeMin = function () {
    //replace root with last element and percolate downwards
    var min = this._heap[1],
        k,
        left,
        right;

    this._heap[1] = this._heap.pop();
    this.size--;
    k = 1;

    while ( ( 2 * k ) <= this.size) {
        left = 2 * k;
        right = 2 * k + 1;

        if (this._heap[k] > this._heap[left] && this._heap[k] > this._heap[right]) {
            if (this._heap[left] <= this._heap[right]) {
                swap(this._heap, k, left);
                k = left;
            } else {
                swap(this._heap, k, right);
                k = right;
            }
        } else if (this._heap[k] > this._heap[left]) {
            swap(this._heap, k, left);
            k = left;
        } else {
            swap(this._heap, k, right);
            k = right;
        }
    }

    return min;
};

javascript algorithm heap min-heap
person teaflavored    schedule 14.03.2016    source источник
comment
Почему? Индекс в основном удваивается на каждом шаге, поэтому вы должны попасть туда за O (log n)   -  person Stefan Haustein    schedule 14.03.2016
comment
Думаю, это правильное состояние. Поскольку вы проверяете количество элементов, вставленных в массив, а не длину массива.   -  person Prasanna    schedule 06.06.2020

Ответы (2)


arrow_upward
1
arrow_downward

Я думаю, вы пропустите одно условие if. Когда элемент k меньше правого и левого, движение вниз должно прекратиться. Это должно быть:

   if (this._heap[k] > this._heap[left] && this._heap[k] > this._heap[right]) {
        if (this._heap[left] <= this._heap[right]) {
            swap(this._heap, k, left);
            k = left;
        } else {
            swap(this._heap, k, right);
            k = right;
        }
    } else if (this._heap[k] > this._heap[left]) {
        swap(this._heap, k, left);
        k = left;
    } else if(this._heap[k] < this._heap[right]) {
        swap(this._heap, k, right);
        k = right;
    }else{
        break;
    }
person Yanhui Zhou    schedule 14.03.2016

arrow_upward
0
arrow_downward

Почему вы пишете код сравнения снова и снова. Поделившись приведенным ниже кодом для справки, который оптимизирует ваш код, вы можете заменить его своим циклом while.

.....
while (2 * k <= this.size) {
        let j = 2 * key;
        if (j < this.size && less(j, j + 1)) j++; // find smallest child
        if (!less(k, j)) break; // check parent is lesser than smallest child or not
        exch(k, j); //if parent is bigger then exchange
        k = j; //keep checking untill reaches to the end(this.size)
    }
.....
function less(i, j){
    if(this._heap[j] < this._heap[i] < 0) return true;
    else return false;
}
function exch(i, j){
    let temp = this._heap[i];
    this._heap[i] = this._heap[j];
    this._heap[j] = temp;
}

Надеюсь, это сработает.

person Prasanna    schedule 06.06.2020