// Huffman code using a minHeap with handles (index-heap-based priority queue). // Heap routines are adapted from "Algorithms in C, Third Edition", and // "Algorithms in Java, Third Edition", Robert Sedgewick // This is a prototype for demonstration purposes only. // Minimally, the heap/priority queue implementation should // be in a different source file. #include #include int N, // Number of items in queue *pq, // Priority queue *qp, // Table of handles (for tracking) maxQueued; // Capacity of priority queue double *a; // Pointer to user's table int parent(int i) { return i/2; } int left(int i) { return 2*i; } int right(int i) { return 2*i+1; } void exch(int i, int j) { // Swaps parent with child int t; t = pq[i]; pq[i] = pq[j]; pq[j] = t; qp[pq[i]] = i; qp[pq[j]] = j; } void minHeapInit(double *items,int n,int m) { int i; a = items; // Save reference to index table maxQueued=m; N = 0; pq=(int*) malloc((maxQueued+1)*sizeof(int)); // Contains subscripts to a[] qp=(int*) malloc(n*sizeof(int)); // Inverse of pq, allows changing priorities if (!pq || !qp) { printf("malloc failed %d\n",__LINE__); exit(0); } // Set all handles to unused for (i=0;i1 && less(k,parent(k))) { exch(k, parent(k)); k = parent(k); } } void minHeapify(int *pq,int k, int N) // AKA sink { int j; while (left(k) <= N) { j = left(k); if (j < N && less(j+1, j)) j=right(k); if (!less(j, k)) break; exch(k, j); k = j; } } void minHeapInsert(int k) { qp[k] = ++N; pq[N] = k; fixUp(pq, N); } int heapExtractMin() { exch(1, N); minHeapify(pq, 1, --N); qp[pq[N+1]]=(-1); // Set to unused return pq[N+1]; } void minHeapChange(int k) { fixUp(pq, qp[k]); minHeapify(pq, qp[k], N); } // main implements Huffman code. // Index is just a table of priorities whose // subscripts are used in the PQ. int main() { int n,m,op,i,j,val; double *priority,probSum,expected=0.0; int *left,*right; // Links for Huffman code tree, root is subscript m-1 int *parent; // For printing the codes int *length; char *outString; printf("Enter alphabet size\n"); scanf("%d",&n); m=2*n-1; // Number of nodes in tree priority=(double*) malloc(m*sizeof(double)); left=(int*) malloc(m*sizeof(int)); right=(int*) malloc(m*sizeof(int)); parent=(int*) malloc(m*sizeof(int)); outString=(char*) malloc((n+1)*sizeof(char)); length=(int*) malloc(m*sizeof(int)); if (!priority || !left || !right || !parent || !outString || !length) { printf("malloc problem %d\n",__LINE__); exit(0); } minHeapInit(priority,m,n); for (i=0;i=n;i--) length[left[i]]=length[right[i]]=length[i]+1; // Print the leaves, i.e. for the alphabet symbols printf(" i prob parent bits product code\n"); for (i=0;i