Java中优先队列的默认大小是多少？

Question

我想知道为什么Java中的PriorityQueue默认大小是11。我查阅了实现方式，但这让我更加困惑。

优先队列是作为堆实现的。它的容量通过以下函数进行调整：

/**
 * Increases the capacity of the array.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = ((oldCapacity < 64)?
                       ((oldCapacity + 1) * 2):
                       ((oldCapacity / 2) * 3));
    if (newCapacity < 0) // overflow
        newCapacity = Integer.MAX_VALUE;
    if (newCapacity < minCapacity)
        newCapacity = minCapacity;
    queue = Arrays.copyOf(queue, newCapacity);
}

我不理解容量的初始值11。我认为容量应该始终是级别数的2倍。有什么澄清吗？

- Dimitris Leventeas

---

11 可能是优先队列比顺序数据结构更具优势的最小大小。 - user207421

Answer 1

11很可能是一个几乎是随意选择的数字，作为内存消耗和CPU消耗之间的权衡（太大的数字会浪费太多内存，而太低的数字需要对队列进行太多的调整大小）。他们可能会对典型用例进行基准测试，以选择这个数字和调整队列的策略。

- JB Nizet

---

如果堆的大小为11，则需要4个连续的插入/删除操作才能改变堆中的层数。因此，在[8, 15]之间，11在这方面是最佳选择。然而，这种思路并不适用于其他值的情况。 - Dimitris Leventeas