定义

在数据结构中，"堆"通常指的是一种特殊的完全二叉树数据结构，被用于实现优先队列和堆排序。

堆可以分为两种主要类型：最大堆和最小堆。

• 最大堆（Max Heap）： 在最大堆中，父节点的值大于或等于任何一个子节点的值。这意味着堆的根节点是包含最大值的节点。

• 最小堆（Min Heap）： 在最小堆中，父节点的值小于或等于任何一个子节点的值。这意味着堆的根节点是包含最小值的节点。

堆的主要特性是堆中的任意节点的值总是满足堆的性质（最大堆或最小堆），这使得在堆中查找最大或最小元素的时间复杂度为O(1)。

实现

常见的操作包括插入元素insert和删除堆顶元素extract，这两个操作的时间复杂度均为O(log n)，其中n是堆中元素的个数。

一般使用数组来实现堆，数组在内存中是连续存储的，有助于提高堆操作的效率。

可以利用数组的索引关系来表示堆的父子节点关系，使得实现相对简单。

在数组中，对于给定的元素 heap[i]：

• i = 0 时表示根节点
• 其父节点的索引是 (i - 1) / 2（向下取整），即 heap[Math.floor((i - 1) / 2)]。
• 其左子节点的索引是 2 * i + 1，即 heap[2 * i + 1]。
• 其右子节点的索引是 2 * i + 2，即 heap[2 * i + 2]。

下面是使用js实现最小堆的过程

首先使用数组来保存数据

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

insert

然后实现insert方法，在插入数据时，需要调整元素顺序，使它符合最小堆的性质：父节点的值小于两个子节点的值

insert(val) {
    this.heap.push(val)
    this._heapifyUp()
}
_heapifyUp() {
    let currentIndex = this.heap.length - 1
    while (currentIndex > 0) {
        const parentIndex = Math.floor((currentIndex - 1) / 2) // 找到父节点的索引值
        if (this.heap[currentIndex] < this.heap[parentIndex]) {
            [this.heap[currentIndex], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[currentIndex]]
            currentIndex = parentIndex
        } else {
            break
        }
    }
}

只需要考虑父节点与子节点的大小，至于两个子节点的大小顺序如何，堆不在乎。

测试一下

const minHeap = new MinHeap();
minHeap.insert(4);
minHeap.insert(2);
minHeap.insert(8);
minHeap.insert(5);
minHeap.insert(1);

console.log(minHeap.heap) //  [1, 2, 8, 5, 4] 
console.log(minHeap.heap[0]) // 可以直接返回最小值

extractMin

接着，实现extractMin删除堆顶元素的方法，删除之后，需要重新调整数组顺序，就是将左右子节点中较小的那个节点作为父节点，然后调整该节点后续的所有子节点。

extractMin() {
    if (!this.heap.length) return undefined
    let val = this.heap[0]
    this.heap[0] = this.heap.pop() // 删除第一个节点
    this._heapifyDown()
    return val
}
_heapifyDown() {
    let currentIndex = 0
    const len = this.heap.length
    while (true) {
        let smallestIndex = currentIndex
        let leftIndex = currentIndex * 2 + 1
        let rightIndex = currentIndex * 2 + 2

        if (leftIndex < len && this.heap[leftIndex] < this.heap[smallestIndex]) {
            smallestIndex = leftIndex
        }
        if (rightIndex < len && this.heap[rightIndex] < this.heap[smallestIndex]) {
            smallestIndex = rightIndex
        }
        if (currentIndex !== smallestIndex) {
            [this.heap[currentIndex], this.heap[smallestIndex]] = [this.heap[smallestIndex], this.heap[currentIndex]]
            currentIndex = smallestIndex
        } else {
            break
        }
    }
}

完整代码

完整代码如下

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

    insert(val) {
        this.heap.push(val)

        this._heapifyUp()
    }


    _heapifyUp() {
        let currentIndex = this.heap.length - 1
        while (currentIndex > 0) {
            const parentIndex = Math.floor((currentIndex - 1) / 2)
            if (this.heap[currentIndex] < this.heap[parentIndex]) {
                [this.heap[currentIndex], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[currentIndex]]
                currentIndex = parentIndex
            } else {
                break
            }
        }
    }

    extractMin() {
        if (!this.heap.length) return undefined
        let val = this.heap[0]
        this.heap[0] = this.heap.pop() // 删除第一个节点
        this._heapifyDown()
        return val
    }
    _heapifyDown() {
        let currentIndex = 0
        const len = this.heap.length
        while (true) {
            let smallestIndex = currentIndex
            let leftIndex = currentIndex * 2 + 1
            let rightIndex = currentIndex * 2 + 2

            if (leftIndex < len && this.heap[leftIndex] < this.heap[smallestIndex]) {
                smallestIndex = leftIndex
            }
            if (rightIndex < len && this.heap[rightIndex] < this.heap[smallestIndex]) {
                smallestIndex = rightIndex
            }
            if (currentIndex !== smallestIndex) {
                [this.heap[currentIndex], this.heap[smallestIndex]] = [this.heap[smallestIndex], this.heap[currentIndex]]
                currentIndex = smallestIndex
            } else {
                break
            }
        }
    }
}

const minHeap = new MinHeap();
minHeap.insert(4);
minHeap.insert(2);
minHeap.insert(8);
minHeap.insert(5);
minHeap.insert(1);

console.log(minHeap.heap) // [1, 2, 8, 5, 4]

console.log(minHeap.extractMin()) // 1
console.log(minHeap.heap) // [2, 4, 8, 5]

如果要实现最大堆，只需要将上面的代码中进行父子节点大小判断的地方进行改造就可以了，这里不再展开。

与堆内存有关联吗

先说结论：没有啥关联。

程序运行时会创建进程，进程有自己的内存，往往称为进程地址空间。

堆（heap）和栈（stack）是两种内存的管理形式

• stack内存按次序排放，大小明确
• heap结构不故宫，是一种可动态分配和释放的内存

简单来说，数据基本存放规则是：局部的，占用空间确定的数据，一般都放在stack中，反之就放在heap中。

可以看出，stack内存与数据结构栈确实比较相似；而heap内存，更像是数据结构链表，而不是上面提到的数据结构堆。