Ein prominentes Problem im Bereich der Algorithmik ist es, aus einer (potenziell unendlich großen) Datenstruktur das n-kleinste Element zu extrahieren. Abhängig vom zugrundeliegenden Maschinenmodell und der betrachteten Datenstruktur kann dies mehr oder weniger effizient erfolgen.

Im Kontext von binären Heaps sind Algorithmen bekannt, welche das Problem in O(n) Zeit lösen und damit optimal sind. Allerdings nur, wenn der Zugriff auf die Knoten in konstanter Zeit möglich ist, das Maschinenmodell also direkten Zugriff (engl. random access) erlaubt. Muss ein Knoten hingegen erst gesucht werden, damit sein Wert ausgelesen werden kann, und wird die Anzahl an Kanten, die dabei traversiert werden, als Einheitskosten festgelegt, so konnte für dieses als "Explorable Heap Selection" bezeichnete Problem eine superlineare obere Schranke bisher noch nicht überwunden werden.

Die Arbeit beschreibt, analysiert und diskutiert verschiedene Algorithmen zur Lösung dieses Problems und beleuchtet außerdem damit verbundene Phänomene wie die Interdependenz zwischen Laufzeit und Speicher sowie das Ausmaß des Einflusses von Zufall.