1 /* heap.c 2007-09-05 */
3 /* Copyright 2007 Vincent Lefort */
5 /* This file is part of the R-package `ape'. */
6 /* See the file ../COPYING for licensing issues. */
10 int *initPerm(int size)
14 p = (int *) malloc(size*sizeof(int));
20 void permInverse(int *p, int *q, int length)
27 /*swaps two values of a permutation*/
28 void swap(int *p, int *q, int i, int j)
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
43 /*p goes from heap to array, q goes from array to heap*/
45 void heapify(int *p, int *q, double *HeapArray, int i, int n)
53 if ((left <= n) && (HeapArray[p[left]] < HeapArray[p[i]]))
57 if ((right <= n) && (HeapArray[p[right]] < HeapArray[p[smallest]]))
60 swap(p,q,i, smallest);
61 /*push smallest up the heap*/
62 i = smallest; /*check next level down*/
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)*/
73 void reHeapElement(int *p, int *q, double *v, int length, int i)
78 if ((up > 0) && (v[p[here]] < v[p[up]]))
79 while ((up > 0) && (v[p[here]] < v[p[up]])) /*we push the new
87 heapify(p,q,v,i,length);
90 void popHeap(int *p, int *q, double *v, int length, int i)
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*/
96 void pushHeap(int *p, int *q, double *v, int length, int i)
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*/
104 int makeThreshHeap(int *p, int *q, double *v, int arraySize, double thresh)
108 for(i = 1; i < arraySize;i++)
110 pushHeap(p,q,v,heapsize++,i);