当前位置：首页 > JavaScript

js堆实现

2026-02-01 14:09:05JavaScript

堆的概念与特点

堆（Heap）是一种特殊的完全二叉树，分为最大堆和最小堆。最大堆中，父节点的值大于或等于子节点的值；最小堆中，父节点的值小于或等于子节点的值。堆常用于实现优先队列。

堆的存储结构

堆通常使用数组存储，利用完全二叉树的性质：

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

堆的基本操作实现

插入元素（上浮操作）

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

js堆实现

function insert(heap, value) {
  heap.push(value);
  let index = heap.length - 1;
  while (index > 0) {
    const parentIndex = Math.floor((index - 1) / 2);
    if (heap[index] <= heap[parentIndex]) break;
    [heap[index], heap[parentIndex]] = [heap[parentIndex], heap[index]];
    index = parentIndex;
  }
}

删除堆顶元素（下沉操作）

删除堆顶元素后，将数组末尾元素移到堆顶，然后通过“下沉”调整堆结构：

function extractMax(heap) {
  if (heap.length === 0) return null;
  const max = heap[0];
  heap[0] = heap.pop();
  let index = 0;
  while (true) {
    const leftChild = 2 * index + 1;
    const rightChild = 2 * index + 2;
    let largest = index;
    if (leftChild < heap.length && heap[leftChild] > heap[largest]) {
      largest = leftChild;
    }
    if (rightChild < heap.length && heap[rightChild] > heap[largest]) {
      largest = rightChild;
    }
    if (largest === index) break;
    [heap[index], heap[largest]] = [heap[largest], heap[index]];
    index = largest;
  }
  return max;
}

堆的构建

可以通过“堆化”操作将无序数组构建为堆：

js堆实现

function buildHeap(arr) {
  const heap = [...arr];
  for (let i = Math.floor(heap.length / 2) - 1; i >= 0; i--) {
    heapify(heap, i);
  }
  return heap;
}

function heapify(heap, index) {
  const left = 2 * index + 1;
  const right = 2 * index + 2;
  let largest = index;
  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);
  }
}

堆排序实现

利用堆的性质可以实现堆排序算法：

function heapSort(arr) {
  const heap = buildHeap(arr);
  const sorted = [];
  while (heap.length > 0) {
    sorted.unshift(extractMax(heap));
  }
  return sorted;
}

优先队列实现

基于堆可以轻松实现优先队列：

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

  enqueue(value) {
    insert(this.heap, value);
  }

  dequeue() {
    return extractMax(this.heap);
  }

  peek() {
    return this.heap[0];
  }

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