Comment conserver l’ordre des éléments de même priorité dans une queue de priorité implémentée en tant que tas binary?

J’ai créé un segment binary, qui représente une queue prioritaire. C’est juste un algorithme classique bien connu. Ce segment planifie une séquence chronologique de différents événements (la clé de sorting est time).

Il supporte 2 opérations: Insérer et Supprimer. La clé du tas de chaque nœud est supérieure ou égale à chacun de ses enfants. Toutefois, l’ajout d’événements avec la même clé ne conserve pas l’ordre dans lequel ils ont été ajoutés, car chaque fois après l’appel de Remove ou de Insert, les procédures heap-up et heap-down cassent l’ordre.

Ma question est la suivante: que faut-il changer dans un algorithme classique pour conserver l’ordre des nœuds avec la même priorité?

Une solution consiste à append un atsortingbut de temps d’insertion à l’élément inséré. Cela peut être juste un simple compteur incrémenté chaque fois qu’un nouvel élément est inséré dans le tas. Ensuite, lorsque deux éléments sont égaux par priorité, comparez le temps d’insertion.

Autant que je sache, les tas ne sont jamais construits pour préserver l’ordre (c’est pourquoi “le type de tas” est remarquable car il ne s’agit pas d’un type stable).

Je comprends que ce que vous demandez est de savoir si une petite astuce algorithmique pourrait être en mesure de changer cela (ce n’est pas la bonne vieille solution fiable “d’horodatage”). Je ne pense pas que ce soit possible.

Ce que j’aurais suggéré est une version de ceci:

  • garder le même “insérer”;

  • modifiez “remove” afin d’assurer un certain ordre sur les éléments d’une priorité donnée.

Pour ce faire, en tas, au lieu d’échanger des éléments jusqu’à ce que l’ordre soit préservé: permutez un élément jusqu’à la fin d’une arborescence d’éléments de même valeur, en choisissant toujours d’aller à droite lorsque vous le pouvez.

Malheureusement, le problème, c’est que vous ne savez pas où insert appenda un élément d’une priorité donnée: il pourrait se retrouver n’importe où dans l’arborescence. Je pense que changer cela serait plus qu’un simple ajustement de la structure.

Si les éléments sont insérés dans l’ordre chronologique et que cet ordre est conservé (par exemple, “add” plutôt que “insert” et “remove_and_pack” plutôt que “remove”), vous pouvez utiliser l’adresse de la mémoire (convertie en un fichier non signé 32- ou un entier 64 bits selon l’environnement) de l’élément lors de la dernière étape de comparaison. Les premiers éléments auront des adresses numériquement plus basses que les suivantes.