Y a-t-il un tas stable?

32

Existe-t-il une structure de données de file d'attente prioritaire qui prend en charge les opérations suivantes?

  • Insérer (x, p) : ajouter un nouvel enregistrement x avec la priorité p
  • StableExtractMin () : Renvoie et supprime l'enregistrement avec une priorité minimale, rompant les liens par ordre d'insertion .

Ainsi, après Insert (a, 1), Insert (b, 2), Insert (c, 1), Insert (d, 2), une séquence de StableExtractMin retournerait a, puis c, puis b, puis d.

Évidemment, on pourrait utiliser n'importe quelle structure de données de file d'attente prioritaire en stockant la paire comme priorité réelle, mais je suis intéressé par les structures de données qui ne stockent pas explicitement les temps d'insertion (ou l'ordre d'insertion), par analogie avec un tri stable .(p,time)

De manière équivalente (?): Existe-t-il une version stable de heapsort qui ne nécessite pas d' espace supplémentaire ?Ω(n)

Jeffε
la source
Je pense que vous voulez dire "a, puis c, puis b, puis d"?
Ross Snider
Un tas avec une liste d'enregistrements liés + un arbre binaire équilibré basé sur la priorité pointant vers la liste liée correspondante ne fonctionnera pas? Qu'est-ce que je rate?
Aryabhata
Moron: C'est le stockage explicite de l'ordre d'insertion, c'est précisément ce que je veux éviter. J'ai clarifié l'énoncé du problème (et corrigé la faute de frappe de Ross).
Jeffε

Réponses:

16

La méthode Bently-Saxe donne une file d'attente prioritaire stable assez naturelle.

Stockez vos données dans une séquence de tableaux triés . a une taille . Chaque tableau maintient également un compteur . Les entrées de tableau contiennent des données.A i 2 i c i A i [ c i ] , , A i [ 2 i - 1 ]A0,,AkAi2iciAi[ci],,Ai[2i1]

Pour chaque , tous les éléments de ont été ajoutés plus récemment que ceux de et au sein de chaque éléments sont classés par valeur, les liens étant rompus en plaçant les éléments plus anciens devant les éléments plus récents. Notez que cela signifie que nous pouvons fusionner et et conserver cet ordre. (En cas d'égalité lors de la fusion, prenez l'élément de .)A i A i + 1 A i A i A i + 1 A i + 1iAiAi+1AiAiAi+1Ai+1

Pour insérer une valeur , recherchez le plus petit tel que contienne 0 élément, fusionnez et , stockez-le dans et définissez manière appropriée.i A i A 0 , , A i - 1 x A i c 0 , , c ixiAiA0,,Ai1xAic0,,ci

Pour extraire le min, trouver le plus grand indice tel que le premier élément dans soit minimum sur tout et incrémenter .A i [ c i ] i c iiAi[ci]ici

Par l'argument standard, cela donne temps amorti par opération et est stable en raison de l'ordre décrit ci-dessus.O(logn)

Pour une séquence de insertions et extractions, cela utilise n entrées de tableau (ne conservez pas de tableaux vides) plus O ( log n ) mots de données de comptabilité. Cela ne répond pas à la version de Mihai de la question, mais cela montre que la contrainte stable ne nécessite pas beaucoup d'espace au-dessus. En particulier, cela montre qu'il n'y a pas de borne inférieure Ω ( n ) sur l'espace supplémentaire nécessaire.nnO(logn)Ω(n)

Mise à jour: Rolf Fagerberg souligne que si nous pouvons stocker des valeurs nulles (non-données), alors toute cette structure de données peut être compressée dans un tableau de taille , où n est le nombre d'insertions jusqu'à présent.nn

Tout d'abord, notez que nous pouvons regrouper les dans un tableau dans cet ordre (avec A k en premier, suivi de A k - 1 s'il n'est pas vide, etc.). La structure de ceci est complètement codée par la représentation binaire de n , le nombre d'éléments insérés jusqu'à présent. Si la représentation binaire de n a un 1 à la position i , alors A i occupera 2 i emplacement de tableau, sinon il n'occupera aucun emplacement de tableau.Ak,,A0AkAk1nniAi2i

Lors de l'insertion, et la longueur de notre tableau, augmentez de 1 et nous pouvons fusionner A 0 , , A i plus le nouvel élément en utilisant des algorithmes de fusion stables en place existants.nA0,,Ai

Maintenant, où nous utilisons des valeurs nulles, c'est pour se débarrasser des compteurs . Dans A i , nous stockons la première valeur, suivie de c i valeurs nulles, suivie des 2 i - c i - 1 valeurs restantes . Lors d'une extraction-min, on peut toujours trouver la valeur à extraire en temps O ( log n ) en examinant A 0 [ 0 ] , , A k [ 0 ] . Lorsque nous trouvons cette valeur dans A i [ 0ciAici2ici1O(logn)A0[0],,Ak[0] nous définissons A i [ 0 ] sur null puis effectuons une recherche binaire sur A i pour trouver la première valeur non nulle A i [ c i ] et permutons A i [ 0 ] et A i [ c i ] .Ai[0]Ai[0]AiAi[ci]Ai[0]Ai[ci]

Le résultat final: la structure entière peut être implémentée avec un tableau dont la longueur est incrémentée à chaque insertion et un compteur, , qui compte le nombre d'insertions.n

Pat Morin
la source
1
Cela utilise potentiellement O (n) espace supplémentaire à un instant donné après les extractions O (n), non? À ce stade, vous pourriez aussi bien enregistrer la priorité ...
Mehrdad
10

Je ne sais pas quelles sont vos contraintes; les éléments suivants sont-ils admissibles? Stockez les données dans un tableau, que nous interprétons comme un arbre binaire implicite (comme un tas binaire), mais avec les éléments de données au niveau inférieur de l'arbre plutôt qu'à ses nœuds internes. Chaque nœud interne de l'arbre stocke la plus petite des valeurs copiées de ses deux enfants; en cas d'égalité, copiez l'enfant de gauche.

Pour trouver le minimum, regardez la racine de l'arbre.

Pour supprimer un élément, marquez-le comme supprimé (suppression paresseuse) et propagez l'arborescence (chaque nœud sur le chemin d'accès à la racine qui contenait une copie de l'élément supprimé doit être remplacé par une copie de son autre enfant). Conservez un décompte des éléments supprimés et si jamais il devient trop grand une fraction de tous les éléments, puis reconstruisez la structure en préservant l'ordre des éléments au niveau inférieur - la reconstruction prend du temps linéaire, donc cette partie n'ajoute qu'un temps amorti constant à la complexité de l'opération.

Pour insérer un élément, ajoutez-le à la position libre suivante sur la ligne inférieure de l'arborescence et mettez à jour le chemin d'accès à la racine. Ou, si la ligne du bas devient pleine, doublez la taille de l'arborescence (à nouveau avec un argument d'amortissement; notez que cette partie n'est pas différente de la nécessité de reconstruire lorsqu'un tas binaire standard dépasse son tableau).

Ce n'est pas une réponse à la version plus stricte de la question de Mihai, car elle utilise deux fois plus de mémoire qu'une véritable structure de données implicite, même si nous ignorons le coût d'espace de gestion des suppressions paresseusement.

David Eppstein
la source
J'aime ça. Tout comme avec un min-tas d'arbre implicite normal, l'arborescence implicite à 3 ou 4 espaces sera probablement plus rapide en raison des effets de cache (même si vous avez besoin de plus de comparaisons).
Jonathan Graehl
8

Est-ce une interprétation valide de votre problème:

Vous devez stocker N clés dans un tableau de A [1..N] sans informations auxiliaires telles que vous pouvez prendre en charge: * insérer la clé * supprimer min, qui sélectionne l'élément inséré le plus tôt s'il existe plusieurs minima

Cela semble assez difficile, étant donné que la plupart des structures de données implicites jouent le rôle de codage des bits dans l'ordre local de certains éléments. Ici, si plusieurs gars sont égaux, leur ordre doit être préservé, donc de telles astuces ne sont pas possibles.

Intéressant.

Mihai
la source
1
Je pense que cela devrait être un commentaire, pas une réponse, car il ne répond pas vraiment à la question d'origine. (Vous pouvez le supprimer et l'ajouter en tant que commentaire.)
Jukka Suomela
5
Ouais, ce site est un peu ridicule. Nous avons des réputations, des bonus, des récompenses, toutes sortes de façons de commenter que je ne peux pas comprendre. Je souhaite que cela ressemble moins à un jeu pour enfants.
Mihai
1
Je pense qu'il a besoin de plus de représentants pour poster un commentaire. c'est le problème.
Suresh Venkat
@Suresh: Oh, c'est vrai, je ne m'en souvenais pas. Comment sommes-nous réellement censés gérer ce genre de situation (c'est-à-dire qu'un nouvel utilisateur doit demander des clarifications avant de répondre à une question)?
Jukka Suomela
2
pas de sortie facile. Je l'ai vu souvent sur MO. Mihai n'aura aucun mal à se faire repérer, si c'est le Mihai je pense que c'est :)
Suresh Venkat
4

Réponse courte: vous ne pouvez pas.

Réponse légèrement plus longue:

Ω(n)Ω(n)

addr(X)<addr(Y)


Réponse très longue avec des pseudo-mathématiques floues inexactes:

Remarque: la toute fin de la deuxième partie est sommaire, comme mentionné. Si un mathématicien pouvait fournir une meilleure version, je lui en serais reconnaissant.

P

(a,1)<(a,2)(a,1)=(a,1)(a,1)(b,1)

X<YXY

(?,1)?

  • Xlog2(P)2X
  • P

Xlog2(P)O(n)n

Maintenant, combien de bits d'informations chaque «cellule» de mémoire nous fournit-elle?

  • WW
  • X

P1Xlog2(P)<X

Ainsi, pour stocker toutes nos informations, nous avons deux possibilités:

  • Stockez l'ordre d'insertion dans l'adresse et la charge utile en mémoire.
  • Stockez les deux en mémoire et laissez l'adresse libre pour une autre utilisation.

Évidemment, pour éviter le gaspillage, nous utiliserons la première solution.


Maintenant pour les opérations. Je suppose que vous souhaitez avoir:

  • Insert(task,priority)O(logn)
  • StableExtractMin()O(logn)

StableExtractMin()

L'algorithme vraiment vraiment général se présente comme suit:

  1. O(logn)
  2. O(logn)
  3. Rends le.

0(1)O(1)O(1)

O(logn)2(Xlog2(P))

Xlog2(P)O(logn)O(logn)

O(logn)

O(logn)Xlog2(P)

O(logn)

Xlog2(P)O(logn)

L'algorithme d'insertion a généralement juste besoin de mettre à jour une partie de ces informations, je ne pense pas que cela coûtera plus cher (en termes de mémoire) de le faire fonctionner rapidement.


Xlog2(P)

  • Xlog2(P)
  • P
  • Xlog2(P)

Ω(n)

Suzanne Dupéron
la source
aviez-vous vraiment l'intention de faire votre réponse CW?
Suresh Venkat
Oui. Ma réponse n'est pas 100% correcte, comme indiqué à l'intérieur, et ce serait bien si quelqu'un pouvait la corriger même si je ne suis plus sur SO ou quoi que ce soit. Les connaissances devraient être partagées, les connaissances devraient être modifiables. Mais j'ai peut-être mal compris l'utilisation de CW, si c'est le cas, dites-le moi :). EDIT: whoops, en effet je viens de découvrir que je ne recevrai aucun représentant des articles CW et que le contenu est sous licence CC-wiki de quelque manière que ce soit ... Dommage :).
Suzanne Dupéron
3

Si vous implémentez votre file d'attente prioritaire en tant qu'arbre binaire équilibré (un choix populaire), il vous suffit de vous assurer que lorsque vous ajoutez un élément à l'arborescence, il est inséré à gauche de tous les éléments de priorité égale.
De cette façon, l'ordre d'insertion est codé dans la structure de l'arbre lui-même.

TonyK
la source
1
Mais cela ajoute de l'espace O (n) pour les pointeurs, ce qui, à mon avis, est ce que le questionneur veut éviter?
Jeremy
-1

Je ne pense pas que ce soit possible

cas concret:

       x
    x    x
  x  x  1  x
1  x  

tas minimum avec tous les x> 1

heapifying donnera finalement quelque chose comme un choix

       x
    1    1
  x  x  x  x
x  x  

maintenant lequel 1 se propager à root?

monstre à cliquet
la source