Timbunan | Pelaksanaan Gilir Keutamaan menggunakan Javascript-tutorial js-php.cn

Timbunan | Pelaksanaan Gilir Keutamaan menggunakan Javascript

WBOY

Lepaskan： 2024-08-21 12:32:33

asal

638 orang telah melayarinya

Heap | Priority Queue Implementation using Javascript

pengenalan

Timbunan ialah struktur data berasaskan pokok khas yang memenuhi sifat timbunan.
Ia adalah pokok binari yang lengkap, yang bermaksud semua peringkat pokok telah diisi sepenuhnya kecuali tahap terakhir, yang diisi dari kiri ke kanan.

Terdapat dua jenis timbunan:

timbunan maks
timbunan min.

Timbunan Maks:

Dalam timbunan maksimum, untuk mana-mana nod I tertentu, nilai I adalah lebih besar daripada atau sama dengan nilai anak-anaknya.
Sifat ini mestilah benar untuk semua nod dalam Pokok Binari. Nilai tertinggi (maksimum) adalah pada akar pokok.

Timbunan Min:

Dalam timbunan min, untuk mana-mana nod I tertentu, nilai I adalah kurang daripada atau sama dengan nilai anak-anaknya.
Sifat ini mestilah benar untuk semua nod dalam Pokok Binari. Nilai terendah (minimum) adalah pada akar pokok.

Kami boleh memanggil mereka baris gilir keutamaan kerana setiap kali kami melakukan operasi sisipan dan pemadaman, operasi itu akan bubbleUp dan bubbleDown masing-masing.

Kita boleh melaksanakan perkara yang sama dalam tatasusunan tetapi bagaimana untuk mengira leftChildindex, rightChildIndex dan parentIndex?

Formula

Untuk mendapatkan anak

2i+1(kiri )
2i+2 (kanan)

Untuk mendapatkan ibu bapa

i-1/2

Di bawah saya menambah pelaksanaan minHeap sila semak.

class MinHeap {
    constructor() {
        this.data = [];
        this.length = 0;
    }

    insert(value) {
        this.data.push(value);
        this.length++;
        this.bubbleUp(this.length-1);
    }

    bubbleUp(index) {

        if (index == 0) {
            return ;
        }

        const parentIndex = this.getParentIndex(index);
        const parentValue = this.data[parentIndex];
        const value = this.data[index];

        if (parentValue > value) {
            this.data[parentIndex] = this.data[index];
            this.data[index] = parentValue;

            this.bubbleUp(parentIndex);
        }
    }

    getParentIndex(index) {
        return Math.floor((index-1)/2);
    }

    getLeftChildIndex(index) {
        return 2*index + 1;
    }

    getRightChildIndex(index) {
        return 2*index + 2;
    }

    bubbleDown(index) {
        if (index >= this.length) {
            return;
        }

        const lIndex = this.getLeftChildIndex(index);
        const rIndex = this.getRightChildIndex(index);

        const lValue = this.data[lIndex];
        const rValue = this.data[rIndex];
        const value = this.data[index];

        if (lValue < rValue && lValue < value) {
            // swap
            this.data[index] = this.data[lIndex];
            this.data[lIndex] = value;
            this.bubbleDown(lIndex);
        } else if (rValue < lValue && rValue < value) {
            this.data[index] = this.data[rIndex];
            this.data[rIndex] = value;
            this.bubbleDown(rIndex)
        }
    }

    delete() {
        if (this.length === 0) {
            return -1;
        }

        const out = this.data[0];
        if (this.length == 1) {
            this.data = [];
            this.length = 0;
            return out;
        }

        this.data[0] = this.data[this.length-1];
        this.length--;
        this.bubbleDown(0);
    }
}

const test = new MinHeap();

test.insert(50);
test.insert(100);
test.insert(101);
test.insert(20);
test.insert(110);
console.log(test)
test.delete();
console.log('---------After Delete -------')
console.log(test)
/*
MinHeap { data: [ 20, 50, 101, 100, 110 ], length: 5 }
---------After Delete -------
MinHeap { data: [ 50, 100, 101, 110, 110 ], length: 4 }
*/

Salin selepas log masuk

Beri tahu saya bahawa anda mempunyai sebarang pertanyaan, sila hubungi.

Atas ialah kandungan terperinci Timbunan | Pelaksanaan Gilir Keutamaan menggunakan Javascript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!