8 int *initPerm(int size)
12 p = (int *) malloc(size*sizeof(int));
18 void permInverse(int *p, int *q, int length)
25 /*swaps two values of a permutation*/
26 void swap(int *p, int *q, int i, int j)
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
41 /*p goes from heap to array, q goes from array to heap*/
43 void heapify(int *p, int *q, double *HeapArray, int i, int n)
51 if ((left <= n) && (HeapArray[p[left]] < HeapArray[p[i]]))
55 if ((right <= n) && (HeapArray[p[right]] < HeapArray[p[smallest]]))
58 swap(p,q,i, smallest);
59 /*push smallest up the heap*/
60 i = smallest; /*check next level down*/
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)*/
71 void reHeapElement(int *p, int *q, double *v, int length, int i)
76 if ((up > 0) && (v[p[here]] < v[p[up]]))
77 while ((up > 0) && (v[p[here]] < v[p[up]])) /*we push the new
85 heapify(p,q,v,i,length);
88 void popHeap(int *p, int *q, double *v, int length, int i)
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*/
94 void pushHeap(int *p, int *q, double *v, int length, int i)
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*/
102 int makeThreshHeap(int *p, int *q, double *v, int arraySize, double thresh)
106 for(i = 1; i < arraySize;i++)
108 pushHeap(p,q,v,heapsize++,i);