Реализуйте итератор в двоичной куче

Question

Я ищу способ реализации итератора в двоичных кучах (максимум или минимум).

То есть, используя i-ый раз функцию nextNode (), можно получить i-й (больший или меньший) элемент в куче.

Обратите внимание, что эта операция происходит без фактического извлечения корня кучи!

Мои первые мысли были:

• Фактически извлеките элементы i, поместите их в стек, а затем вставьте их обратно в кучу после получения значения i. Для каждого вызова функции требуется O (i * log (n)).
• Сохраните вспомогательную структуру отсортированных данных, которая может позволить искать следующее значение в O (1), однако для обновления потребуется O (n).

Я понимаю, что эти подходы исключают преимущества использования куч, поэтому я ищу более подходящий подход.

Answer 1

Не ясно, каков вариант использования для этого, поэтому трудно сказать, что сделало бы решение жизнеспособным или лучше, чем любое другое решение.

Тем не менее, я предлагаю небольшое изменение к общим идеям "извлекать и сортировать", которые уже реализованы: Если мы хорошо вносим изменения в структуру данных, мы можем выполнить нашу сортировку на месте.

Базовая реализация, предложенная в Википедии , представляет собой частично отсортированный список изнутри.Мы можем заплатить (мы надеемся) единовременную O ( n log ( n )) стоимость сортировки нашей кучи при первом вызове next()после чего next равно O (1).Крайне важно, что полностью отсортированный список по-прежнему является действительной кучей .

Более того, если вы рассмотрите алгоритм heapsort , вы можете начать на втором этапе, потому что вы начинаете с правильной кучи.