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

Question

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

Поддерживает 2 операции: вставка и удаление. Ключ каждого узла кучи больше или равен каждому из его дочерних элементов. Однако добавление событий с одним и тем же ключом не сохраняет порядок, в котором они были добавлены, поскольку каждый раз после вызова Remove или Insert процедуры heap-up и heap-down нарушают порядок.

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

Answer 1

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

Answer 2

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

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

Я бы предложил несколько вариантов этого:

• сохранить то же самое "insert";

• изменить «удалить», чтобы обеспечить определенный порядок для элементов с заданным приоритетом.

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

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

Answer 3

Если элементы вставлены в хронологическом порядке, и этот порядок поддерживается (например, с помощью «добавления», а не «вставки» и «удаления_пакета», а не просто «удаления»), вы можете использовать адрес памяти (приведенный к 32-разрядное или 64-разрядное целое число без знака (в зависимости от среды) элемента в качестве последнего этапа сравнения. Ранние элементы будут иметь численно более низкие адреса, чем более поздние.