void build_tree(Deflate s){
    short[] tree=dyn_tree;
    short[] stree=stat_desc.static_tree;
    int elems=stat_desc.elems;
    int n, m;          // iterate over heap elements
    int max_code=-1;   // largest code with non zero frequency
    int node;          // new node being created

    // Construct the initial heap, with least frequent element in
    // heap[1]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
    // heap[0] is not used.
    s.heap_len = 0;
    s.heap_max = HEAP_SIZE;

    for(n=0; n<elems; n++) {
      if(tree[n*2] != 0) {
	s.heap[++s.heap_len] = max_code = n;
	s.depth[n] = 0;
      }
      else{
	tree[n*2+1] = 0;
      }
    }

    // The pkzip format requires that at least one distance code exists,
    // and that at least one bit should be sent even if there is only one
    // possible code. So to avoid special checks later on we force at least
    // two codes of non zero frequency.
    while (s.heap_len < 2) {
      node = s.heap[++s.heap_len] = (max_code < 2 ? ++max_code : 0);
      tree[node*2] = 1;
      s.depth[node] = 0;
      s.opt_len--; if (stree!=null) s.static_len -= stree[node*2+1];
      // node is 0 or 1 so it does not have extra bits
    }
    this.max_code = max_code;

    // The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
    // establish sub-heaps of increasing lengths:

    for(n=s.heap_len/2;n>=1; n--)
      s.pqdownheap(tree, n);

    // Construct the Huffman tree by repeatedly combining the least two
    // frequent nodes.

    node=elems;                 // next internal node of the tree
    do{
      // n = node of least frequency
      n=s.heap[1];
      s.heap[1]=s.heap[s.heap_len--];
      s.pqdownheap(tree, 1);
      m=s.heap[1];                // m = node of next least frequency

      s.heap[--s.heap_max] = n; // keep the nodes sorted by frequency
      s.heap[--s.heap_max] = m;

      // Create a new node father of n and m
      tree[node*2] = (short)(tree[n*2] + tree[m*2]);
      s.depth[node] = (byte)(Math.max(s.depth[n],s.depth[m])+1);
      tree[n*2+1] = tree[m*2+1] = (short)node;

      // and insert the new node in the heap
      s.heap[1] = node++;
      s.pqdownheap(tree, 1);
    }
    while(s.heap_len>=2);

    s.heap[--s.heap_max] = s.heap[1];

    // At this point, the fields freq and dad are set. We can now
    // generate the bit lengths.

    gen_bitlen(s);

    // The field len is now set, we can generate the bit codes
    gen_codes(tree, max_code, s.bl_count, s.next_code);
  }