src/heap.c

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