A nearly optimal randomized algorithm for explorable heap selection

Sander Borst, Daniel Dadush, Sophie Huiberts +1

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 b…