Как сохранить порядок элементов с одним и тем же приоритетом в очереди приоритетов, реализованной как двоичная куча?

Я создал двоичную кучу, которая представляет очередь приоритетов. Это просто классический известный алгоритм. Эта куча описывает хронологическую последовательность различных событий (ключ сортировки - время).

Он поддерживает 2 операции: Вставка и удаление. Каждый ключ node кучи больше или равен каждому из его дочерних элементов. Однако добавление событий с одним и тем же ключом не сохраняет порядок, в который они были добавлены, потому что каждый раз после удаления или вставки были вызваны процедуры кучи и кучи, нарушающие порядок.

Мой вопрос: что следует изменить в классическом алгоритме, чтобы сохранить порядок узлов с одинаковым приоритетом?

Ответ 1

Одним из решений является добавление времени атрибута вставки к вставленному элементу. Это может быть просто простой счетчик, приращенный каждый раз, когда новый элемент вставляется в кучу. Затем, когда два элемента равны по приоритету, сравните время вставки.

Ответ 2

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

Я понимаю, что вы спрашиваете, может ли небольшой алгоритмический трюк изменить это (это не хорошее старое надежное решение "timestamp" ). Я не думаю, что это возможно.

Я бы предложил следующую версию:

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

Чтобы сделать это, в куче-вниз, вместо того, чтобы менять элементы до тех пор, пока порядок не будет сохранен: замените элемент до тех пор, пока он не станет концом arborescence элементов с одинаковым значением, всегда выбирая идти вправо, когда вы можете.

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

Ответ 3

Если элементы вставляются в хронологическом порядке, и этот порядок поддерживается (например, путем добавления "append", а не "insert" и "remove_and_pack", а не просто "remove" ), вы можете использовать адрес памяти (отбрасывать на беззнаковое 32- или 64-битное целое число в зависимости от среды) элемента как конечного этапа сравнения. Ранние элементы будут иметь числовые адреса ниже, чем более поздние.