当前位置：首页 > JavaScript

js堆实现

2026-04-06 06:56:10JavaScript

JavaScript 堆实现

堆是一种特殊的完全二叉树，分为最大堆和最小堆。最大堆的父节点值大于或等于子节点值，最小堆的父节点值小于或等于子节点值。以下是 JavaScript 中堆的实现方法。

堆的基本结构

堆通常用数组表示，利用数组的索引关系模拟树结构。对于索引 i 的节点：

父节点索引：Math.floor((i - 1) / 2)
左子节点索引：2 * i + 1
右子节点索引：2 * i + 2

class Heap {
  constructor(comparator = (a, b) => a > b) {
    this.heap = [];
    this.comparator = comparator;
  }
}

插入元素

插入元素时，先将元素放到数组末尾，然后通过“上浮”操作调整堆结构。

js堆实现

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.comparator(this.heap[index], this.heap[parentIndex])) {
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      index = parentIndex;
    } else {
      break;
    }
  }
}

删除堆顶元素

删除堆顶元素时，将堆尾元素移到堆顶，然后通过“下沉”操作调整堆结构。

extract() {
  if (this.heap.length === 0) return null;
  const top = this.heap[0];
  this.heap[0] = this.heap.pop();
  this.sinkDown(0);
  return top;
}

sinkDown(index) {
  const length = this.heap.length;
  while (true) {
    const leftChild = 2 * index + 1;
    const rightChild = 2 * index + 2;
    let swapIndex = null;

    if (leftChild < length && this.comparator(this.heap[leftChild], this.heap[index])) {
      swapIndex = leftChild;
    }
    if (rightChild < length && this.comparator(this.heap[rightChild], this.heap[swapIndex === null ? index : swapIndex])) {
      swapIndex = rightChild;
    }

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

获取堆顶元素

直接返回数组的第一个元素。

js堆实现

peek() {
  return this.heap.length > 0 ? this.heap[0] : null;
}

堆的大小

返回数组的长度。

size() {
  return this.heap.length;
}

示例用法

以下是一个最大堆的示例用法：

const maxHeap = new Heap();
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.insert(8);
maxHeap.insert(1);
console.log(maxHeap.extract()); // 8
console.log(maxHeap.extract()); // 5

以下是一个最小堆的示例用法：

const minHeap = new Heap((a, b) => a < b);
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(8);
minHeap.insert(1);
console.log(minHeap.extract()); // 1
console.log(minHeap.extract()); // 3