仿写react优先队列

最小堆结构示意图#

NOTE
最小堆是一种特殊的完全二叉树，其中每个节点的值都小于或等于其子节点的值。

         1
       /   \
      3     2
     / \   / \
    6   5 4   7

层级说明：
第1层：根节点 1
第2层：左子节点 3，右子节点 2
第3层：3的子节点(6,5)，2的子节点(4,7)

TIP
图中展示了一个具有7个节点的最小堆：
根节点1是整个堆中的最小值
每个父节点都小于其子节点
兄弟节点之间没有大小顺序要求

最小堆的特点#

结构性质：是一个完全二叉树
堆序性质：任一节点的值小于或等于其子节点值
根节点：始终是堆中的最小元素
应用场景：优先队列、堆排序等算法

TavaScript 实现#

NOTE
本实现参考了React v19的调度器中的最小堆实现。React团队在性能关键型代码中采用了高效的数据结构设计，值得学习。
源码链接：React Scheduler MinHeap

`peek`#

export function peek<T extends Node>(heap: Heap<T>) {
  if (heap.length > 0) {
    return heap[0]
  }
  return null;
}

通用比较函数#

首先介绍一个核心的比较函数，用于确定两个节点之间的优先级关系：

function compare<T extends Node>(l: T, r?: T) {
  if (!r) {
    return l;
  }
  return l.sortIndex < r.sortIndex ? l : r
}

`push`#

export function push<T extends Node>(heap: Heap<T>, node: T) {
  heap.push(node);
  // 上浮
  siftUp(heap, node, heap.length - 1);
}

`siftUp`#

function siftUp<T extends Node>(heap: Heap<T>, node: T, idx: number) {
  const parentIdx = ((idx - 1) >> 1); // 计算父节点索引
  const parentNode = heap[parentIdx];
  
  // 如果没有父节点或已经满足堆的性质，则将节点放在当前位置
  if (!parentNode) {
    heap[idx] = node;
    return;
  } else if (compare(node, parentNode) === parentNode) {
    heap[idx] = node;
    return;
  }
  
  // 否则，将父节点下移，并继续向上调整
  heap[idx] = parentNode;
  siftUp(heap, node, parentIdx);
}

`pop`#

export function pop<T extends Node>(heap: Heap<T>): T | null {
  if (heap.length === 0) {
    return null;
  }
  const first = heap[0]; // 获取堆顶元素
  const last = heap.pop()!; // 移除并获取最后一个元素
  
  // 如果堆中只有一个元素，直接返回
  if (first === last) {
    return first;
  }
  
  // 将最后一个元素放到堆顶，然后进行下沉操作
  heap[0] = last;
  siftDown(heap, last, 0);
  return first;
}

`siftDown`#

function siftDown<T extends Node>(heap: Heap<T>, node: T, idx: number) {
  const length = heap.length;
  const leftChildIdx = 2 * idx + 1; // 左子节点索引
  
  // 如果没有子节点，将节点放在当前位置
  if (leftChildIdx >= length) {
    heap[idx] = node;
    return;
  }
  
  const leftChild = heap[leftChildIdx];
  const rightChild = heap[leftChildIdx + 1]; // 右子节点索引
  const minChild = compare(leftChild, rightChild); // 找出较小的子节点
  
  // 如果当前节点已经小于等于最小的子节点，则满足堆的性质
  if (node === compare(minChild, node)) {
    heap[idx] = node;
    return;
  }
  
  // 否则，将较小的子节点上移，并继续向下调整
  heap[idx] = minChild;
  if (leftChild === minChild) {
    siftDown(heap, node, leftChildIdx);
  } else {
    siftDown(heap, node, leftChildIdx + 1);
  }
}

可视化展示#

我们可以使用 React 组件来可视化展示最小堆的结构和操作过程：

这个可视化组件提供了以下功能：

动态插入：可以通过输入框添加新的节点，并自动维护最小堆性质
提取最小值：点击按钮移除堆顶元素，同时重新调整堆结构
实时更新：每次操作后自动重新计算节点位置并更新视图，直观展示堆的变化
连线展示：通过 Canvas 绘制父子节点之间的连接线，清晰呈现节点关系
自适应布局：节点均匀分布，层次分明，并能根据窗口大小自动调整

TIP
通过这个可视化工具，我们可以：
直观地观察堆的结构变化
理解插入和删除操作的过程
验证最小堆的性质是否始终保持

使用方法#

在输入框中输入一个数字
点击”插入”按钮将数字添加到堆中
点击”提取最小值”按钮删除并返回堆顶元素
观察堆结构的动态变化

这个实现不仅展示了最小堆的基本操作，还通过可视化帮助理解堆的结构特性和操作过程。通过实际操作和观察，可以更好地掌握最小堆这个重要的数据结构。

最小堆结构示意图#

最小堆的特点#

TavaScript 实现#

peek#

通用比较函数#

push#

siftUp#

pop#

siftDown#

可视化展示#

使用方法#

`peek`#

`push`#

`siftUp`#

`pop`#

`siftDown`#