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

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

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

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

Мои первоначальные мысли были:

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

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


iterator heap binary-heap
person Ahmed Hammad    schedule 11.05.2019    source источник
comment
Думаю, это тот же вопрос, что и заголовок stackoverflow.com/questions/7650917/ - вам не нужно тратить O (i) на операции с отсортированной вспомогательной структурой.   -  person Nickolay    schedule 15.05.2019
comment
Вам нужно, чтобы ваш итератор оставался действующим при изменении кучи?   -  person Jeff    schedule 20.05.2019
comment
@ Джефф Нет, не обязательно.   -  person Ahmed Hammad    schedule 20.05.2019

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

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

person ShapeOfMatter    schedule 21.05.2019