Поиск элемента в куче

Question

Я вспомнил, что куча может использоваться для поиска, находится ли элемент в нем или нет с O (logN) сложностью по времени. Но вдруг я не могу получить детали. Я могу найти только getmin delete add и т. Д.

Кто-нибудь может дать подсказку?

Answer 1

Вам необходимо выполнить поиск по каждому элементу в куче, чтобы определить, находится ли элемент внутри.

Однако возможна одна оптимизация (здесь мы предполагаем максимальную кучу). Если вы достигли узла с более низким значением, чем элемент, который вы ищете, вам не нужно искать дальше от этого узла. Однако даже при такой оптимизации поиск по-прежнему составляет O (N) (в среднем необходимо проверить N / 2 узлов).

Answer 2

Я думаю, что вы ищете BST (дерево двоичного поиска).