src/heap.c

   1 #include "me.h"
   2
   3 int *initPerm(int size)
   4 {
   5   int *p;
   6   int i;
   7   p = (int *) malloc(size*sizeof(int));
   8   for(i = 0;i<size;i++)
   9     p[i] = i;
  10   return(p);
  11 }
  12
  13 void permInverse(int *p, int *q, int length)
  14 {
  15   int i;
  16   for(i=0;i<length;i++)
  17     q[p[i]] = i;
  18 }
  19
  20 /*swaps two values of a permutation*/
  21 void swap(int *p, int *q, int i, int j)
  22 {
  23   int temp;
  24   temp = p[i];
  25   p[i] = p[j];
  26   p[j] = temp;
  27   q[p[i]] = i;
  28   q[p[j]] = j;
  29 }
  30
  31 /*The usual Heapify function, tailored for our use with a heap of scores*/
  32 /*will use array p to keep track of indexes*/
  33 /*after scoreHeapify is called, the subtree rooted at i
  34   will be a heap*/
  35
  36 /*p goes from heap to array, q goes from array to heap*/
  37
  38 void heapify(int *p, int *q, double *HeapArray, int i, int n)
  39 {
  40   int moreswap = 1;
  41
  42   do {
  43     int left = 2 * i;
  44     int right = 2* i + 1;
  45     int smallest;
  46     if ((left <= n) &&  (HeapArray[p[left]] < HeapArray[p[i]]))
  47       smallest = left;
  48     else
  49       smallest = i;
  50     if ((right <= n) && (HeapArray[p[right]] < HeapArray[p[smallest]]))
  51       smallest = right;
  52     if (smallest != i){
  53       swap(p,q,i, smallest);
  54       /*push smallest up the heap*/
  55       i = smallest;            /*check next level down*/
  56     }
  57     else
  58       moreswap = 0;
  59   } while(moreswap);
  60 }
  61
  62 /*heap is of indices of elements of v,
  63   popHeap takes the index at position i and pushes it out of the heap
  64   (by pushing it to the bottom of the heap, where it is not noticed)*/
  65
  66 void reHeapElement(int *p, int *q, double *v, int length, int i)
  67 {
  68   int up, here;
  69   here = i;
  70   up = i / 2;
  71   if ((up > 0) && (v[p[here]] < v[p[up]]))
  72     while ((up > 0) && (v[p[here]] < v[p[up]])) /*we push the new
  73                                                   value up the heap*/
  74       {
  75         swap(p,q,up,here);
  76         here = up;
  77         up = here / 2;
  78       }
  79   else
  80     heapify(p,q,v,i,length);
  81 }
  82
  83 void popHeap(int *p, int *q, double *v, int length, int i)
  84 {
  85   swap(p,q,i,length); /*puts new value at the last position in the heap*/
  86   reHeapElement(p,q, v,length-1,i); /*put the swapped guy in the right place*/
  87 }
  88
  89 void pushHeap(int *p, int *q, double *v, int length, int i)
  90 {
  91   swap(p,q,i,length+1); /*puts new value at the last position in the heap*/
  92   reHeapElement(p,q, v,length+1,length+1); /*put that guy in the right place*/
  93 }
  94
  95
  96
  97 int makeThreshHeap(int *p, int *q, double *v, int arraySize, double thresh)
  98 {
  99   int i, heapsize;
 100   heapsize = 0;
 101   for(i = 1; i < arraySize;i++)
 102     if(v[q[i]] < thresh)
 103       pushHeap(p,q,v,heapsize++,i);
 104   return(heapsize);
 105 }