src/heap.c

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