3 int *initPerm(int size)
7 p = (int *) malloc(size*sizeof(int));
13 void permInverse(int *p, int *q, int length)
20 /*swaps two values of a permutation*/
21 void swap(int *p, int *q, int i, int j)
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
36 /*p goes from heap to array, q goes from array to heap*/
38 void heapify(int *p, int *q, double *HeapArray, int i, int n)
46 if ((left <= n) && (HeapArray[p[left]] < HeapArray[p[i]]))
50 if ((right <= n) && (HeapArray[p[right]] < HeapArray[p[smallest]]))
53 swap(p,q,i, smallest);
54 /*push smallest up the heap*/
55 i = smallest; /*check next level down*/
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)*/
66 void reHeapElement(int *p, int *q, double *v, int length, int i)
71 if ((up > 0) && (v[p[here]] < v[p[up]]))
72 while ((up > 0) && (v[p[here]] < v[p[up]])) /*we push the new
80 heapify(p,q,v,i,length);
83 void popHeap(int *p, int *q, double *v, int length, int i)
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*/
89 void pushHeap(int *p, int *q, double *v, int length, int i)
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*/
97 int makeThreshHeap(int *p, int *q, double *v, int arraySize, double thresh)
101 for(i = 1; i < arraySize;i++)
103 pushHeap(p,q,v,heapsize++,i);