[c ansi] tas (priority queue)

Soyez le premier à donner votre avis sur cette source.

Snippet vu 4 928 fois - Téléchargée 17 fois

Contenu du snippet

On voit souvent ici des "programmes" qui mettent en oeuvre uniquement une liste chainee, ou une liste doublement chainee. Ici, je vous propose une structure particuliere d'arbre binaire complet ordonnee de la facon suivante :

chaque pere a une valeur plus elevee que ses deux enfants.
si il manque des enfants, c'est forcement "en bas a droite".
toutes les branches ont la meme hauteur (sauf eventuellement, tout en bas a droite)

sur une telle structure, on s'appercoit que si on les numerote :

0
1 2
3 4 5 6
7 8 9 10 11 12 13 14

alors si un pere est numerote : i, ses enfants sont : 2i et 2i+1

a partir de la, on peut faire une structure de tableau, et on evite ainsi le triple chainage (et on y gagne un random acces, meme si avant l'acces etait logarithmique, c'est toujours mieux.)

Bref, sur cette structure, on peut ajouter des elements, supprimer des elements (de preference, on supprime celui du dessus) en O(log(n)).
sur une liste non triee, on aurait l'insertion en O(1) et la suppression (ainsi que la recherche) du plus grand element en O(n)
sur une liste triee, c'est l'insertion qui serait en O(n), la suppression et la recherche du plus grand element serait en O(1)

c'est donc une bonne structure pour une file de priorites (priority queue), meme si elle ne permet pas le "merge" de deux tas en O(log(n)) mais seulement en O(n).

certaines fonctions sont plutot la pour la decoration (to_2_exp, ln2, spaces servent uniquement pour pouvoir faire draw_tas)

mon exemple est avec une file d'int, mais on peut l'adapter pour n'importe quel type, voir carement en faire une classe Cpp avec des templates.

il existe une methode de tri qui se base sur l'insertion dans une liste comme ceci, ca fait un tres bon tri en O(n log(n)), a peu pres entre le merge sort et le quick sort.

Source / Exemple :


#include <stdio.h>
#include <stdlib.h>

void swap(int *v1, int *v2){
  int v3 = *v1;

  • v1 = *v2;
  • v2 = v3;
} int to_2_exp(int i){ if (i==0) return 0; if (i==1) return 1; return 2 * to_2_exp( i / 2); } int ln2(int i){ if (i==0) return 0; if (i==1) return 1; return 1 + to_2_exp( i / 2); } void spaces(int n){ int i; for (i=0; i<n; i++) putchar(' '); } typedef int * tas; tas new_tas(size_t s){ return malloc(s * sizeof(int)); } void fixup(tas t, size_t n){ if (n == 0) return; else{ int n2 = (n-1)/2; if (t[n] > t[n2]){ swap(&t[n], &t[n2]); fixup(t, n2); } } } void fixdown(tas t, size_t n, size_t max){ int n2 = n*2+1; if (n2 >= max) return; if (n2 + 1 < max && t[n2+1] > t[n2] ) n2++; if (t[n] < t[n2]){ swap(&t[n], &t[n2]); fixdown(t, n2, max); } } void draw_tas(tas t, size_t n){ int i; int k = 1; int k_max = to_2_exp(n); int v; for (i=0; i<n; i++){ if (i == k - 1){ k *= 2; if (i) putchar('\n'); v = 2* (k_max * 2 / k ) - 1; spaces(v); } printf("%2d", t[i]); spaces(2 * v); } putchar('\n'); } size_t add_tas(tas t, int value, size_t n){ t[n] = value; fixup(t, n); return n+1; } size_t pop_tas(tas t, size_t n){ t[0] = t[--n]; fixdown(t, 0, n); return n; } int main(){ /* exemple d'utilisation d'un tas */ int s = 0; tas t = new_tas(15); add_tas(t, 12, s++); add_tas(t, 24, s++); add_tas(t, 48, s++); add_tas(t, 15, s++); add_tas(t, 23, s++); add_tas(t, 49, s++); add_tas(t, 19, s++); add_tas(t, 54, s++); add_tas(t, 29, s++); add_tas(t, 18, s++); add_tas(t, 53, s++); add_tas(t, 92, s++); add_tas(t, 90, s++); add_tas(t, 64, s++); add_tas(t, 22, s++); draw_tas(t, s); s = pop_tas(t, s); s = pop_tas(t, s); draw_tas(t, s); free(t); return 0; }

Conclusion :


voici le rendu de mon programme :
apres les insertions :
92
90 53
64 24 49 54
22 12 18 23 29 15 48 19

apres les suppressions :
64
54 53
48 24 49 19
22 12 18 23 29 15

ca compile sous linux, avec juste les options suivantes :
gcc tas.c -g -Wall -ansi --pedantic

A voir également

Ajouter un commentaire Commentaires
Messages postés
215
Date d'inscription
dimanche 20 février 2005
Statut
Membre
Dernière intervention
10 mars 2014

oki mais les commentaires c pour expliquer, meme si le nom des fonctions sont assez explicites
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
41
en fait, le 2i+1 ou 2i+2, ca depend si tu comptes a partir de 0 ou a partir de 1 :) dans mon explication, je commence a partir de 1, alors que dans mon code, a partir de 0 (normal)

pop correspond tres bien a ce qu'on fait : on supprime l'element du sommet (qui etait le plus grand), on reordonne le tas, et on le renvoie.

par contre pour le push, on imaginerait qu'on place qqch au dessus (or c'est pas une stack )

mais euh... le nomage, c'est du detail...

s, c'est la taille du tas, j'aurais pu faire un tas sous forme de :
struct tas {
int * tas;
size_t n;
}

pour inclure le "tas" dedans, sauf que ca m'aurait pose quelques problemes pour pouvoir faire un heapsort (qui se fait sur un foo*).

sinon, pour les commentaires... je n'ai que 5 fonctions...

fixup permet de faire remonter un element si il est superieur a son pere
fixdown fait l'inverse : il fait descendre un element quand il est inferieur a un de ses enfants

push et add, c'est pas trop dur de deviner ce que ca fait

draw_tas affiche un tas de nombres a un ou deux chiffres

to_exp2(n) renvoie l'exposant de deux directement superieur a n ( exemple to_exp2(12) = 16 )
ln2(n) renvoie le nombre de bits utilises pour coder n.
Messages postés
215
Date d'inscription
dimanche 20 février 2005
Statut
Membre
Dernière intervention
10 mars 2014

slt,
quelques remarques :
- dans ton explication :
#alors si un pere est numerote : i, ses enfants sont : 2i et 2i+1

c'est faux, c'est 2i+1 et 2i+2

- tu définis une fonction pop_tas, alors pourquoi tu mettrais pas push_tas à la place de add_tas

- de plus tu utilise un paramètre s++ dans ta fonction add, pourquoi ne pas faire en sorte de supprimer ce paramètre??

- quelques commentaires sur la source peuvent aider ...

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.