首頁 > web前端 > js教程 > 主體

堆|使用Javascript實作優先權隊列

WBOY
發布: 2024-08-21 12:32:33
原創
618 人瀏覽過

Heap | Priority Queue Implementation using Javascript

介紹

堆是一種特殊的基於樹的資料結構,滿足堆屬性。
它是一棵完全二元樹,這意味著除了最後一層是從左到右填充之外,樹的所有層都被完全填充。

堆有兩種:

  1. 最大堆
  2. 最小堆。

最大堆:

在最大堆中,對於任何給定節點 I,I 的值大於或等於其子節點的值。
對於二元樹中的所有節點,此屬性必須為 true。最高值(最大值)位於樹的根部。

最小堆:

在最小堆中,對於任何給定節點 I,I 的值小於或等於其子節點的值。
對於二元樹中的所有節點,此屬性必須為 true。最低值(最小值)位於樹的根部。

我們可以稱它們為優先權佇列,因為每次執行插入和刪除操作時,它都會分別 bubbleUpbubbleDown

我們可以在數組中實現相同的功能,但是如何計算 leftChildIndex、rightChildIndex 和 ParentIndex?

公式

為了生小孩

2i+1(左)
2i+2(右)

取得父母

i-1/2

下面我新增了一個 minHeap 的實現,請檢查。

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 }
*/

登入後複製

如果您有任何疑問,請隨時與我聯繫。

以上是堆|使用Javascript實作優先權隊列的詳細內容。更多資訊請關注PHP中文網其他相關文章!

來源:dev.to
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網:公益線上PHP培訓,幫助PHP學習者快速成長!