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

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

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

Ответ 1

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

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

Ответ 2

Слишком поздно, но все еще добавляю это для кого-то, кто может споткнуться здесь.

Поиск в куче, как она есть, потребует O (N) времени. Но если вы можете выполнить одноразовую предварительную обработку для выталкивания всех элементов последовательно в массиве, вы получите отсортированный массив в O (N.logN). Эффективно куча сортировки. Теперь ваш новый отсортированный массив можно найти за O (logN).

Ответ 3

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

Ответ 4

Добавление индекса к значениям кучи может решить эту проблему. В Python это можно сделать с помощью словаря. обновляйте индекс узла в словаре каждый раз, когда выполняете операцию в куче min.

Это следует реализовывать только в том случае, если длина вашей минимальной кучи огромна, и вы хотите выполнять поиск в минимальной куче много раз. Для отслеживания индекса потребуются некоторые накладные расходы на код, но это увеличит скорость программы как минимум на 50 - 60%.