A nearly optimal randomized algorithm for explorable heap selection
提出一种随机算法，在二叉堆中选取第n小的值，运行时间O(n log^3 n)，空间O(log n)，显著改进先前随机算法，并证明该空间下运行时间的下界，表明算法近乎最优。
Abstract Explorable heap selection is the problem of selecting the n th smallest value in a binary heap. The key values can only be accessed by traversing through the underlying infinite binary tree, and the complexity of the algorithm is measured by the total distance traveled in the tree (each edge has unit cost). This problem was originally proposed as a model to study search strategies for the branch-and-bound algorithm with storage restrictions by Karp, Saks and Widgerson (FOCS ’86), who gave deterministic and randomized $$n\cdot \exp (O(\sqrt{\log {n}}))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>·</mml:mo> <mml:mo>exp</mml:mo> <mml:mo>(</mml:mo> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msqrt> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msqrt> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> time algorithms using $$O(\log (n)^{2.5})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mn>2.5</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and $$O(\sqrt{\log n})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msqrt> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msqrt> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> space respectively. We present a new randomized algorithm with running time $$O(n\log (n)^3)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>log</mml:mo> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mn>3</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> against an oblivious adversary using $$O(\log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> space, substantially improving the previous best randomized running time at the expense of slightly increased space usage. We also show an $$\Omega (\log (n)n/\log (\log (n)))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> <mml:mi>n</mml:mi> <mml:mo>/</mml:mo> <mml:mo>log</mml:mo> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> lower bound for any algorithm that solves the problem in the same amount of space, indicating that our algorithm is nearly optimal.