Rumah >hujung hadapan web >tutorial js >Timbunan | Pelaksanaan Gilir Keutamaan menggunakan Javascript

Timbunan | Pelaksanaan Gilir Keutamaan menggunakan Javascript

WBOY
WBOYasal
2024-08-21 12:32:33648semak imbas

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:

  1. timbunan maks
  2. 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 }
*/

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!

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn