n 个元素的 d 元堆的高度，以 n 和 d 表示

Question

我通过以下方法解决了这个问题：-

1. n <= 1+d+d²+…….+d^h
2. n >= 1+d+d²+……..+d^h-1+1

这两个等式使我得出以下 h 范围：-

log_d((n(d-1)+1)/2) <= h <= log_d(( n-1)(d-1)+1)

但我不知道如何从这个不等式进一步推导出 h = big-theta(log_dn)?

Answer 1

一个完整的n层d堆中的项目数是(1-dⁿ)/(1-d)。七级二叉堆包含 127 个项目。七层 4 堆将包含 5,461 (16383/3) 个项目。

一点代数告诉我们，在 d 堆中容纳 n 个项目所需的层数是 log_d(n*(d - 1) + 1)。因此，具有 21 个项目的 4 堆需要 log₄(20*(4 - 1)+1)，或 2.96 个级别。我们不能有部分级别，所以我们四舍五入到 3。

有关详细信息，请参阅我的博客 post、The d-ary heap。

Answer 2

我在 math.stackexchange.com 中的问题提供了更数学正确的解决方案。 请参考下面link看证明：

https://math.stackexchange.com/questions/2318306/height-of-a-d-ary-heap-of-n-elements-in-terms-of-n-and-d

谢谢。