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--)
00031 perc_down(a,i,j);
00032 i = 1;
00033 for (j=n; j>=2; j--) {
00034 swapItem(&a[i],&a[j]);
00035 perc_down(a,i,j-1);
00036 }
00037 }