堆数据结构详解：最大堆与最小堆的实现与应用 | 优先队列与堆排序

堆（Heap）是一种特殊的树形数据结构，通常用于实现优先队列。堆可以分为最大堆和最小堆两种类型：

1. 最大堆：在最大堆中，每个节点的值都大于或等于其子节点的值。因此，堆的根节点是整个堆中的最大值。

2. 最小堆：在最小堆中，每个节点的值都小于或等于其子节点的值。因此，堆的根节点是整个堆中的最小值。

堆的性质

• 完全二叉树：堆通常是一个完全二叉树，这意味着除了最后一层，其他层都是满的，并且最后一层的节点尽可能地集中在左边。
• 堆序性质：在最大堆中，父节点的值总是大于或等于子节点的值；在最小堆中，父节点的值总是小于或等于子节点的值。

堆的操作

1. 插入（Insert）：将新元素插入堆的末尾，然后通过“上浮”操作（向上调整）来恢复堆的性质。
2. 删除（Delete）：通常删除堆顶元素（最大堆中的最大值或最小堆中的最小值），然后将堆的最后一个元素移动到堆顶，并通过“下沉”操作（向下调整）来恢复堆的性质。
3. 构建堆（Build Heap）：将一个无序数组转换为堆，通常通过从最后一个非叶子节点开始，逐个进行“下沉”操作来实现。

堆的应用

• 优先队列：堆是实现优先队列的理想数据结构，因为它可以在O(log n)时间内插入和删除元素，并且可以在O(1)时间内获取最大或最小元素。
• 堆排序：堆排序是一种基于堆的排序算法，其时间复杂度为O(n log n)。
• Dijkstra算法：在图的单源最短路径算法中，堆用于高效地选择下一个最短路径节点。

堆的实现

堆通常使用数组来实现，因为完全二叉树的性质使得数组可以高效地表示堆结构。对于数组中的任意一个元素，其父节点和子节点的位置可以通过简单的数学计算得到：

• 父节点位置：parent(i) = floor((i - 1) / 2)
• 左子节点位置：leftChild(i) = 2 * i + 1
• 右子节点位置：rightChild(i) = 2 * i + 2

示例代码（最大堆的插入和删除操作）

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

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

    bubbleUp(index) {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] >= this.heap[index]) break;
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }

    extractMax() {
        if (this.heap.length === 0) return null;
        const max = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.bubbleDown(0);
        }
        return max;
    }

    bubbleDown(index) {
        const length = this.heap.length;
        const element = this.heap[index];
        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let swapIndex = null;

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

            if (rightChildIndex < length) {
                if (
                    (swapIndex === null && this.heap[rightChildIndex] > element) ||
                    (swapIndex !== null && this.heap[rightChildIndex] > this.heap[leftChildIndex])
                ) {
                    swapIndex = rightChildIndex;
                }
            }

            if (swapIndex === null) break;
            [this.heap[index], this.heap[swapIndex]] = [this.heap[swapIndex], this.heap[index]];
            index = swapIndex;
        }
    }
}

// 使用示例
const heap = new MaxHeap();
heap.insert(10);
heap.insert(5);
heap.insert(15);
heap.insert(2);
console.log(heap.extractMax()); // 输出 15
console.log(heap.extractMax()); // 输出 10

总结

堆是一种高效的数据结构，特别适用于需要频繁获取最大或最小元素的场景。通过合理的设计和实现，堆可以在O(log n)时间内完成插入和删除操作，并且在O(1)时间内获取堆顶元素。