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

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

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

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