percolate.c
Go to the documentation of this file.
00001 #include <stdio.h>
00002 #include "percolate.h"
00003 
00004 
00005 void swapItem(TAsoc *a, TAsoc *b){
00006         TAsoc c;
00007 
00008         c=*a;
00009         *a=*b;
00010         *b=c;
00011 }
00012 
00013 void perc_down(TAsoc a[], int i, int n) {
00014   int child; TAsoc tmp;
00015   for (tmp=a[i]; i*2 <= n; i=child) {
00016     child = i*2;
00017     if ((child != n) && (a[child+1].dist > a[child].dist))
00018       child++;
00019     if (tmp.dist < a[child].dist)
00020       a[i] = a[child];
00021     else
00022       break;
00023   }
00024   a[i] = tmp;
00025 }
00026 
00027 void heapsort(TAsoc a[], int n) {
00028   int i, j;
00029   j = n;
00030   for (i=n/2; i>0; i--)  /* BuildHeap */
00031     perc_down(a,i,j);
00032   i = 1;
00033   for (j=n; j>=2; j--) {
00034     swapItem(&a[i],&a[j]);   /* DeleteMax */
00035     perc_down(a,i,j-1);
00036   }
00037 }


csm
Author(s): Andrea Censi
autogenerated on Mon Jan 16 2017 03:48:29