为什么 PriorityQueue 执行 (k - 1) >>> 1？

Question

我在 Java 学习 PriorityQueue。
当我查看 offer 方法时，无法找出为什么在 siftUpComparable 方法中使用 (k - 1) >>> 1。
这是源代码：

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1; // what's the purpose of this line?
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

Answer 1

既然可以保证 k > 0，那条线也可以是 (k - 1) >> 1。 >> 和 >>> 运算符向右移动作为 right-hand 操作数给出的位数。移位 1 与除以 2 完全相同，因此这是计算 parent = (k - 1) / 2（使用整数截断），但速度更快。

>> 和 >>> 之间的区别在于负数会发生什么：>> 在左侧填充符号位的当前值，而 >>> 总是用零填充。

Answer 2

获取k-th元素的父元素在二叉堆中的索引。

这是bit-shifting表达

的方式

int parent = (k-1)/2

为什么 PriorityQueue 执行 (k - 1) >>> 1？

Why does PriorityQueue do (k - 1) >>> 1?

java

bit-manipulation

priority-queue