最小堆添加元素时向上转换的问题

Question

问题1：看老师的文档，堆是一个二叉树，但是在push函数里，老师计算父节点时，直接用数组的索引来获取，heap[parentIndex]， 这样能获取到吗？参数中传过来的数组数据，不需要先转化为树结构吗？
问题2： const parentIndex = (index - 1) >>> 1; 这个位运算不太理解，能再详细说一下吗？
问题3：heap这个数组，是已经转为最小堆的一维数组吗？

function siftUp<T extends Node>(heap: Heap<T>, node: T, i: number): void {
  let index = i;
  while (index > 0) {
    const parentIndex = (index - 1) >>> 1;
    const parent = heap[parentIndex];
    if (compare(parent, node) > 0) {
      // node子节点更小，和根节点交换
      heap[parentIndex] = node;
      heap[index] = parent;
      index = parentIndex;
    } else {
      return;
    }
  }
}

Answer 1

高少云 2024-12-27 13:33:21

1. 可以获取到的，因为这是一个最小堆，也就是一个完全二叉树。所以它的特征就是：

根据子节点下标推算父节点下标：parentIndex = (childIndex - 1) >>> 1

根据父节点下标推算子节点下标：

*leftIndex = (index +1 )2 - 1,

rightIndex = leftIndex + 1

参数中传过来的数组数据，不需要先转化为树结构吗？--在初始化的时候，这个数组就是最小堆的结构，后续每次push和pop都会再次维持这个最小堆的结构。因此，这个数组始终是最小堆结构。

2. >>> 这是个二进制运算，就是把所有位向右边移动一位，最左边用0补充，最右边抹掉一位。你可以自己试试，比如9的二进制是1001，往右边移动一位，就是0100，就是十进制的4。这不就是9/2取整嘛~

3. 是的，参考第一个回答~