【堆与优先队列】：JavaScript应用详解与性能优化

# 1. 堆与优先队列的基本概念和原理

## 1.1 堆的定义和性质

堆是一种特殊的完全二叉树，它满足任何一个父节点的值都大于或等于（在最小堆中）其子节点的值，这样的结构保证了堆的根节点总是最大或最小的元素，这也是堆最重要的性质。堆可以分为最小堆和最大堆两种，最小堆的根节点是所有节点中最小的，而最大堆的根节点是最大的。

## 1.2 堆的操作

堆支持以下几种基本操作：
- 插入：将新元素添加到堆中，然后通过上浮（上堆化）操作保证堆的性质不变。
- 删除：从堆中删除根节点，并用最后一个元素替换根节点的位置，然后通过下沉（下堆化）操作保证堆的性质不变。

## 1.3 优先队列的定义和性质

优先队列是一种抽象数据类型，它允许插入任意数据，但每次删除操作总是返回队列中优先级最高的元素。在实现上，优先队列通常使用堆来支持高效的插入和删除操作。优先队列的性质依赖于它所使用的堆的类型，可以是最大优先队列（基于最大堆实现）或最小优先队列（基于最小堆实现）。

# 2. 堆与优先队列在JavaScript中的实现

## 2.1 堆的基本操作

### 2.1.1 堆的定义和性质

堆是一种特殊的完全二叉树，它满足两个性质：首先是结构性质，即任何一个非叶子节点的值都不大于或者不小于其子节点的值，这称为堆属性；其次是完全二叉树性质，意味着除了最后一层外，每一层都被完全填满，并且最后一层的所有节点都集中在左边。

在JavaScript中，堆可以用数组表示，因为数组可以很容易地反映出完全二叉树的结构。数组的第一个元素可以认为是堆的根节点，对于任意元素A[i]（从1开始计数）：

- 它的父节点是A[parseInt((i-1)/2)]。
- 它的左子节点是A[2*i+1]。
- 它的右子节点是A[2*i+2]。

### 2.1.2 堆的插入和删除操作

#### 插入操作

插入操作是将一个新元素添加到堆中，并保持堆的性质。基本步骤如下：

1. 将新元素添加到堆的末尾。
2. 将新元素向上移动，与它的父节点比较，如果满足堆性质，结束操作；否则，与父节点交换位置。
3. 重复第二步，直到新元素可以放在根节点位置或者它的父节点不再大于新元素为止。

function insertToHeap(heap, value) {
    heap.push(value);
    let index = heap.length - 1;
    let parentIndex = parseInt((index - 1) / 2);

    while (index !== 0 && heap[parentIndex] > heap[index]) {
        [heap[parentIndex], heap[index]] = [heap[index], heap[parentIndex]];
        index = parentIndex;
        parentIndex = parseInt((index - 1) / 2);
    }
}

let heap = [10, 15, 20, 30, 40];
insertToHeap(heap, 5);

上述代码中，新元素`5`被添加到堆的末尾，然后向上比较和交换，直到满足堆性质。

#### 删除操作

删除操作通常指的是删除堆中的最大元素（对于最大堆来说）。基本步骤如下：

1. 将根节点（最大元素）与堆的最后一个元素交换。
2. 移除最后一个元素（现在是原来的最大元素），并将其放入一个临时位置。
3. 将新的根节点向下移动，与它的子节点比较，如果满足堆性质，结束操作；否则，与较大的子节点交换位置。
4. 重复第三步，直到该节点可以放置在堆的任何位置或者它的子节点都不小于它为止。

function deleteFromHeap(heap) {
    if (heap.length === 0) return null;
    if (heap.length === 1) return heap.pop();

    let temp = heap[0];
    heap[0] = heap.pop();
    heapify(heap, 0);
    return temp;
}

function heapify(heap, index) {
    let largest = index;
    let left = 2 * index + 1;
    let right = 2 * index + 2;

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

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

    if (largest !== index) {
        [heap[index], heap[largest]] = [heap[largest], heap[index]];
        heapify(heap, largest);
    }
}

let heap = [10, 15, 20, 30, 40, 5];
console.log(deleteFromHeap(heap)); // 输出最大元素 40

上述代码实现了从最大堆中删除最大元素，并通过`heapify`函数确保剩余元素仍符合堆性质。

## 2.2 优先队列的实现

### 2.2.1 优先队列的定义和性质

优先队列是一种抽象数据类型，它允许插入元素并删除具有最高优先级的元素。在堆实现中，堆的根节点通常对应最高优先级的元素。

优先队列的一个基本性质是它维持了元素的优先级顺序。通常来说，具有最高优先级的元素（对于最大优先队列来说，是数值最大的元素）将首先被删除。

### 2.2.2 优先队列的插入和删除操作

优先队列的插入操作与堆的插入操作相同，因为堆本质上就是优先队列的一种实现方式。优先队列的删除操作就是移除堆的根节点，并重新调整堆以维持堆性质。

在JavaScript中，可以使用与堆相同的实现来完成优先队列的功能，只需调用堆的删除操作即可。

## 2.3 JavaScript中的堆与优先队列实现

### 2.3.1 JavaScript中的堆实现

堆可以使用JavaScript数组来实现。它允许通过数组索引快速访问和修改节点，同时保持堆性质。下面是使用JavaScript实现的最大堆的一个简单示例：

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

    insert(value) {
        this.heap.push(value);
        this.heapifyUp(this.heap.length - 1);
    }

    heapifyUp(index) {
        let currentIndex = index;
        let parentIndex = parseInt((index - 1) / 2);
        while (currentIndex > 0 && this.heap[parentIndex] < this.heap[currentIndex]) {
            [this.heap[parentIndex], this.heap[currentIndex]] = [this.heap[currentIndex], this.heap[parentIndex]];
            currentIndex = parentIndex;
            parentIndex = parseInt((currentIndex - 1) / 2);
        }
    }

    deleteMax() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        let max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown(0);
        return max;
    }

    heapifyDown(index) {
        let currentIndex = index;
        let leftChildIndex = 2 * currentIndex + 1;
        let rightChildIndex = 2 * currentIndex + 2;
        let largestIndex = currentIndex;

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

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

        if (largestIndex !== currentIndex) {
            [this.heap[currentIndex], this.heap[largestIndex]] = [this.heap[largestIndex], this.heap[currentIndex]];
            this.heapifyDown(largestIndex);
        }
    }
}

// 使用示例
let maxHeap = new MaxHeap();
maxHeap.insert(10);
maxHeap.insert(15);
maxHeap.insert(30);
maxHeap.insert(20);
consol