Как сохранить порядок элементов с одинаковым приоритетом в очереди приоритетов, реализованной в виде двоичной кучи?
Я создал двоичную кучу, которая представляет приоритетную очередь. Это просто классический известный алгоритм. Эта куча планирует хронологическую последовательность различных событий (ключ сортировки - время).
Он поддерживает 2 операции: вставить и удалить. Ключ каждого узла кучи больше или равен каждому из его дочерних элементов. Однако добавление событий с одним и тем же ключом не сохраняет порядок, в котором они были добавлены, поскольку каждый раз после вызова Remove или Insert процедуры heap-up и heap-down нарушают порядок.
Мой вопрос: что нужно изменить в классическом алгоритме, чтобы сохранить порядок узлов с одинаковым приоритетом?
3 ответа
Одним из решений является добавление атрибута времени вставки к вставленному элементу. Это может быть просто простой счетчик, увеличиваемый каждый раз, когда новый элемент вставляется в кучу. Затем, когда два элемента равны по приоритету, сравните время вставки.
Насколько я знаю, кучи никогда не создаются для сохранения порядка (поэтому "сортировка кучи" отличается нестабильной сортировкой).
Я понимаю, что вы спрашиваете, может ли небольшой алгоритмический трюк изменить это (это не старое, надежное и надежное решение с отметкой времени). Я не думаю, что это возможно.
То, что я предложил бы, является некоторой версией этого:
сохраняйте ту же "вставку";
измените "удалить", чтобы обеспечить определенный порядок элементов с заданным приоритетом.
Чтобы сделать это, в heap-down, вместо того чтобы менять элементы вниз, пока не сохранится порядок: меняйте элемент вниз до тех пор, пока он не станет концом древовидности элементов с одинаковым значением, всегда выбирая вправо, когда это возможно.
К сожалению, проблема в том, что вы не знаете, куда вставка добавит элемент с заданным приоритетом: он может оказаться в любом месте дерева. Я полагаю, что изменить это будет больше, чем просто изменить структуру.
Если элементы вставлены в хронологическом порядке, и этот порядок поддерживается (например, с помощью "append" вместо "insert" и "remove_and_pack" вместо "delete"), вы можете использовать адрес памяти (приведенный к беззнаковому 32- или 64-разрядное целое число в зависимости от среды) элемента в качестве последнего шага сравнения. Ранние элементы будут иметь меньшие адреса, чем более поздние.