JavaScript 中如何實(shí)現(xiàn)一個二叉堆？

在 JavaScript 中，可以通過數(shù)組來實(shí)現(xiàn)一個二叉堆。二叉堆分為最大堆和最小堆兩種類型，本問將以最大堆為例子。

一個二叉堆可以看做是一顆完全二叉樹，每個節(jié)點(diǎn)的值都大于等于其子節(jié)點(diǎn)的值（對于最大堆而言）。因此，在使用數(shù)組來實(shí)現(xiàn)二叉堆時，可以使用數(shù)組下標(biāo)來表示完全二叉樹的節(jié)點(diǎn)，并滿足以下規(guī)則：

  1. 對于任意節(jié)點(diǎn) i，其左子節(jié)點(diǎn)的下標(biāo)為 2i+1，右子節(jié)點(diǎn)的下標(biāo)為 2i+2。
  2. 對于任意節(jié)點(diǎn) i，其父節(jié)點(diǎn)的下標(biāo)為 Math.floor((i-1)/2)。

接下來，可以使用數(shù)組來實(shí)現(xiàn)一個最大堆。具體而言，可以定義一個數(shù)組 arr 來保存堆的元素，并定義一些方法來實(shí)現(xiàn)堆的常見操作，如插入元素、刪除堆頂元素等。下面是一個簡單的實(shí)現(xiàn)示例：

class MaxHeap {
    constructor() {
        this.heap = [];
    }

    // 插入元素
    insert(value) {
        this.heap.push(value);
        this.bubbleUp(this.heap.length - 1);
    }

    // 刪除堆頂元素
    extractMax() {
        const max = this.heap[0];
        const end = this.heap.pop();

        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.sinkDown(0);
        }

        return max;
    }

    // 上浮操作
    bubbleUp(index) {
        const element = this.heap[index];
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            const parent = this.heap[parentIndex];
            if (element <= parent) {
                break;
            }
            this.heap[parentIndex] = element;
            this.heap[index] = parent;
            index = parentIndex;
        }
    }

    // 下沉操作
    sinkDown(index) {
        const left = 2 * index + 1;
        const right = 2 * index + 2;
        let largest = index;

        if (left < this.heap.length && this.heap[left] > this.heap[largest]) {
            largest = left;
        }

        if (right < this.heap.length && this.heap[right] > this.heap[largest]) {
            largest = right;
        }

        if (largest !== index) {
            const temp = this.heap[index];
            this.heap[index] = this.heap[largest];
            this.heap[largest] = temp;
            this.sinkDown(largest);
        }
    }
}

在上述代碼中，MaxHeap 類定義了一個數(shù)組 heap 來保存堆的元素，同時實(shí)現(xiàn)了 insert、extractMax、bubbleUp 和 sinkDown 方法，分別用于插入元素、刪除堆頂元素、上浮操作和下沉操作。

在 bubbleUp 方法中，使用循環(huán)來不斷將新插入的元素上浮，直到滿足堆的條件；sinkDown 方法中，首先找出當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)，然后將當(dāng)前節(jié)點(diǎn)與兩個子節(jié)點(diǎn)中的最大值進(jìn)行比較，如果當(dāng)前節(jié)點(diǎn)的值小于最大值，則交換兩個節(jié)點(diǎn)的值，并遞歸進(jìn)行下沉操作，直到滿足堆的條件。

上面定義類的使用方式如下：

const maxHeap = new MaxHeap();

maxHeap.insert(26);
maxHeap.insert(103);
maxHeap.insert(721);
maxHeap.insert(911);
maxHeap.insert(202);

console.log(maxHeap.heap); // [ 911, 721, 103, 26, 202 ]

const max = maxHeap.extractMax();
console.log(max); // 911
console.log(maxHeap.heap); // [ 721, 202, 103, 26 ]

上面代碼首先創(chuàng)建了一個最大堆 maxHeap，插入了一些元素。然后，調(diào)用 extractMax 方法來刪除堆頂元素，得到最大值并打印。最后，打印修改后的堆結(jié)構(gòu)，可以看到堆頂?shù)脑匾呀?jīng)被刪除并且堆的結(jié)構(gòu)已經(jīng)滿足最大堆的條件。

 

二叉堆javascript