堆

详见堆排序章节

在计算机科学中, 一个 堆(heap) 是一种特殊的基于树的数据结构，它满足下面描述的堆属性。

在一个 最小堆(min heap) 中, 如果 P 是 C 的一个父级节点, 那么 P 的key(或value)应小于或等于 C 的对应值.

M最小堆

在一个 最大堆(max heap) 中, P 的key(或value)大于 C 的对应值。

堆

Array Representation

在堆“顶部”的没有父级节点的节点,被称之为根节点。

最小堆

class MinHeap { constructor() { this.heap = []; } // 获取父节点的索引 getParentIndex(index) { return Math.floor((index - 1) / 2); } // 获取左子节点的索引 getLeftChildIndex(index) { return 2 * index + 1; } // 获取右子节点的索引 getRightChildIndex(index) { return 2 * index + 2; } // 交换元素位置 swap(index1, index2) { [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]]; } // 上移操作（向上调整堆） siftUp(index) { if (index === 0) { return; } const parentIndex = this.getParentIndex(index); if (this.heap[parentIndex] > this.heap[index]) { this.swap(parentIndex, index); this.siftUp(parentIndex); } } // 下移操作（向下调整堆） siftDown(index) { const leftChildIndex = this.getLeftChildIndex(index); const rightChildIndex = this.getRightChildIndex(index); let minIndex = index; if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] < this.heap[minIndex]) { minIndex = leftChildIndex; } if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[minIndex]) { minIndex = rightChildIndex; } if (minIndex !== index) { this.swap(index, minIndex); this.siftDown(minIndex); } } // 插入元素到堆中 insert(value) { this.heap.push(value); this.siftUp(this.heap.length - 1); } // 获取堆顶元素（最小值） peek() { if (this.heap.length === 0) { return null; } return this.heap[0]; } // 删除堆顶元素（最小值） remove() { if (this.heap.length === 0) { return null; } const minValue = this.heap[0]; const lastValue = this.heap.pop(); if (this.heap.length > 0) { this.heap[0] = lastValue; this.siftDown(0); } return minValue; } // 获取堆的大小 size() { return this.heap.length; } } 

最大堆

class MaxHeap { constructor() { this.heap = []; } // 获取父节点的索引 getParentIndex(index) { return Math.floor((index - 1) / 2); } // 获取左子节点的索引 getLeftChildIndex(index) { return 2 * index + 1; } // 获取右子节点的索引 getRightChildIndex(index) { return 2 * index + 2; } // 交换元素位置 swap(index1, index2) { [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]]; } // 上移操作（向上调整堆） siftUp(index) { if (index === 0) { return; } const parentIndex = this.getParentIndex(index); if (this.heap[parentIndex] < this.heap[index]) { this.swap(parentIndex, index); this.siftUp(parentIndex); } } // 下移操作（向下调整堆） siftDown(index) { const leftChildIndex = this.getLeftChildIndex(index); const rightChildIndex = this.getRightChildIndex(index); let maxIndex = index; if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] > this.heap[maxIndex]) { maxIndex = leftChildIndex; } if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] > this.heap[maxIndex]) { maxIndex = rightChildIndex; } if (maxIndex !== index) { this.swap(index, maxIndex); this.siftDown(maxIndex); } } // 插入元素到堆中 insert(value) { this.heap.push(value); this.siftUp(this.heap.length - 1); } // 获取堆顶元素（最大值） peek() { if (this.heap.length === 0) { return null; } return this.heap[0]; } // 删除堆顶元素（最大值） remove() { if (this.heap.length === 0) { return null; } const maxValue = this.heap[0]; const lastValue = this.heap.pop(); if (this.heap.length > 0) { this.heap[0] = lastValue; this.siftDown(0); } return maxValue; } // 获取堆的大小 size() { return this.heap.length; } } 

参考

• Wikipedia
• YouTube