Операция pop на месте для двоичной кучи на основе массива?

У меня есть двоичная куча на основе массива, используемая для поиска по графу (хотя цель не имеет значения).
(Элемент с индексом 0 является вершиной кучи.)

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

Однако мне интересно: есть ли какой-либо эффективный способ сохранить элемент в начале исходного массива, каким-то образом просто изменив границы "активного " часть кучи каким-то образом (т. е. сдвинув начальную границу активной части на один элемент) и продолжать, пока я не закончу?
Это наивно испортит структуру кучи.


algorithm data-structures heap in-place binary-heap
person user541686    schedule 13.07.2014    source источник
comment
Почему вы хотите оставить этот предмет там? В любом случае вам понадобится шаг исправления (какой из других элементов станет новой вершиной? И какой из них займет место новой вершины? и т. д.), поэтому единственное, что вы действительно сэкономите, это... копирование нескольких элементов (которые должны быть за дешевизной) и, возможно, некоторое изменение размера массива.   -  person    schedule 14.07.2014
comment
@delnan: с теоретической точки зрения это бесполезно. С практической точки зрения я делаю это на C++, и отказ от перемещения объектов в отдельный массив помогает снизить требования к типу объекта пользователя. В любом случае, причина не имеет значения, так что не беспокойтесь об этом. Я специально пытаюсь получить ответ на этот конкретный вопрос, а не на что-то другое. Если это невозможно, то это правильный ответ для меня.   -  person user541686    schedule 14.07.2014

Ответы (1)


arrow_upward
0
arrow_downward

Обычная операция "pop" для двоичной кучи на основе массива перемещает удаляемый элемент в конец массива (поэтому размер массива может быть уменьшен для его удаления), поэтому, если это то, что вы хотите, вы можете отслеживать это там. Действительно, используя двоичную кучу на основе массива, где вы сначала вставляете все элементы в кучу с функцией приоритета, так что желаемый последний элемент имеет наивысший приоритет, а затем извлекаете все элементы (оставляя их в конце массива) как работает сортировка кучей.

person Chris Dodd    schedule 14.07.2014
comment
Однако это не работает для меня; если я перемещаю элемент в конец массива, я больше не могу помещать в кучу больше элементов, превышающих размер массива в этот конкретный момент времени. Я пытаюсь сохранить его в начале массива, поэтому мне не нужно ограничивать добавление элементов в конце. - person user541686; 14.07.2014
comment
Что делает пирамидальная сортировка, так это меняет местами элемент с индексом 0 на последний элемент в куче, а затем исправляет его. Это сжимает кучу, но она по-прежнему начинается с 0. Таким образом, в массиве размера N куча всегда будет между 0..k для некоторого k, а элементы массива выше k свободны для вас, чтобы вы могли делать, как хотите, например для хранения предметов, удовлетворяющих критериям. Вы даже можете переиндексировать массив, поместив a[i] в ​​a[N-i-1], и в этом случае куча будет жить между a[N-k-1] и a[N-1], а вершина кучи всегда будет находиться в a[N-i-1]. [N-1] и a[0]..a[k-1] свободны для хранения соответствующих элементов. - person mcdowella; 14.07.2014