home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c019 / 3.ddi / AR001 / MAKETREE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-04-22  |  1.6 KB  |  66 lines
  1. /***********************************************************
  2.     maketree.c -- make Huffman tree
  3. ***********************************************************/
  4. #include "ar.h"
  5.  
  6. static short n, heapsize, heap[NC + 1];
  7. static ushort *freq;
  8. static uchar *len;
  9.  
  10. static void make_len(short i)  /* call with i = root */
  11. {
  12.     static uchar depth = 0;
  13.  
  14.     if (i < n) len[i] = depth;
  15.     else {
  16.         depth++;
  17.         make_len(left [i]);
  18.         make_len(right[i]);
  19.         depth--;
  20.     }
  21. }
  22.  
  23. static void downheap(short i)
  24.     /* priority queue; send i-th entry down heap */
  25. {
  26.     short j, k;
  27.  
  28.     k = heap[i];
  29.     while ((j = 2 * i) <= heapsize) {
  30.         if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
  31.              j++;
  32.         if (freq[k] <= freq[heap[j]]) break;
  33.         heap[i] = heap[j];  i = j;
  34.     }
  35.     heap[i] = k;
  36. }
  37.  
  38. short make_tree(short nparm, ushort freqparm[], uchar lenparm[])
  39.     /* make tree, calculate len[], return root */
  40. {
  41.     short i, j, k, avail;
  42.  
  43.     n = nparm;  freq = freqparm;  len = lenparm;
  44.     avail = n;  heapsize = 0;  heap[1] = 0;
  45.     for (i = 0; i < n; i++) {
  46.         len[i] = 0;
  47.         if (freq[i]) heap[++heapsize] = i;
  48.     }
  49.     if (heapsize < 2) return heap[1];
  50.     for (i = heapsize / 2; i >= 1; i--)
  51.         downheap(i);  /* make priority queue */
  52.     do {  /* while queue has at least two entries */
  53.         i = heap[1];  /* take out least-freq entry */
  54.         heap[1] = heap[heapsize--];
  55.         downheap(1);
  56.         j = heap[1];  /* next least-freq entry */
  57.         k = avail++;  /* generate new node */
  58.         freq[k] = freq[i] + freq[j];
  59.         heap[1] = k;  downheap(1);  /* put into queue */
  60.         left[k] = i;  right[k] = j;
  61.     } while (heapsize > 1);
  62.     for (i = 0; i < n; i++) len[i] = 0;
  63.     make_len(k);
  64.     return k;  /* return root */
  65. }
  66.