algorithm - 使用优先级队列的基于比较的排序 - 绑定(bind)在队列比较上

Question

我需要证明你不能有一个基于比较的 PQ 算法，其中 insert 和 deleteMax 使用少于 lg(N)/3 + O(1) 比较操作，其中 N 是队列的当前长度。

我知道它与基于比较的排序绑定(bind) Nlog(N) 有关，但不能完全达到所需的值。

请帮忙!

Answer 1

这几乎来自 standard analysis of the decision tree bound on comparison-based sorting .

有n!个排列，也就是决策树的叶子数。树的高度至少为 log(n!) - O(1)。

相反，如果您实际上可以使用问题中的比较次数进行操作，则高度最多为

2 ∑_{i = 1}ⁿ[log(i)/3 + O(1)]

(乘以 2 是因为同时存在插入和删除最大值)。

但是，

2 ∑_{i = 1}ⁿ[log(i)/3 + O(1)] = 2/3 log(n!) + Θ (n).

很明显，通过 Stirling's approximation ,

lim_{n → ∞} [(2/3 log(n!) + Θ(n))/(log(n!) - O(1)] = 2/3 .

这表明，渐近地，树的高度是不够的 - 它大约是所需高度的 2/3。