[c ansi] tas (priority queue)

Commenter

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

S'inscrire maintenant

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.

Du même auteur (coucou747)