build

    pub fn build(
        freqs: []const u16,
        out_codes: []u16,
        out_bits: []u4,
        max_bits: u4,
        incomplete_allowed: bool,
    ) struct { u32, u16 } {
        assert(out_codes.len - 1 >= @intFromBool(!incomplete_allowed));
        // freqs and out_codes are in the loop to assert they are all the same length
        for (freqs, out_codes, out_bits) |_, _, n| assert(n == 0);
        assert(out_codes.len <= @as(u16, 1) << max_bits);

        // Indexes 0..freqs are leafs, indexes max_leafs.. are internal nodes.
        var tree_nodes: [max_nodes]Node = undefined;
        var tree_parent_nodes: [max_nodes]Node.Index = undefined;
        var nodes_end: u16 = max_leafs;
        // Dual-purpose buffer. Nodes are ordered by least frequency or when equal, least depth.
        // The start is a min heap of level-zero nodes.
        // The end is a sorted buffer of nodes with the greatest first.
        var node_buf: [max_nodes]Node.Index = undefined;
        var heap_end: u16 = 0;
        var sorted_start: u16 = node_buf.len;

        for (0.., freqs) |n, freq| {
            tree_nodes[n] = .{ .freq = freq, .depth = 0 };
            node_buf[heap_end] = @intCast(n);
            heap_end += @intFromBool(freq != 0);
        }

        // There must be at least one code at minimum,
        node_buf[heap_end] = 0;
        heap_end += @intFromBool(heap_end == 0);
        // and at least two if incomplete must be avoided.
        if (heap_end == 1 and incomplete_allowed) {
            @branchHint(.unlikely); // LLVM 21 optimizes this branch as the more likely without

            // Codes must have at least one-bit, so this is a special case.
            out_bits[node_buf[0]] = 1;
            out_codes[node_buf[0]] = 0;
            return .{ freqs[node_buf[0]], node_buf[0] };
        }
        const last_nonzero = @max(node_buf[heap_end - 1], 1); // For heap_end > 1, last is not be 0
        node_buf[heap_end] = @intFromBool(node_buf[0] == 0);
        heap_end += @intFromBool(heap_end == 1);

        // Heapify the array of frequencies
        const heapify_final = heap_end - 1;
        const heapify_start = (heapify_final - 1) / 2; // Parent of final node
        var heapify_i = heapify_start;
        while (true) {
            heapSiftDown(&tree_nodes, node_buf[0..heap_end], heapify_i);
            if (heapify_i == 0) break;
            heapify_i -= 1;
        }

        // Build optimal tree. `max_bits` is not enforced yet.
        while (heap_end > 1) {
            const a = node_buf[0];
            heapRemoveRoot(&tree_nodes, node_buf[0..heap_end]);
            heap_end -= 1;
            const b = node_buf[0];

            sorted_start -= 2;
            node_buf[sorted_start..][0..2].* = .{ b, a };

            tree_nodes[nodes_end] = .{
                .freq = tree_nodes[a].freq + tree_nodes[b].freq,
                .depth = @max(tree_nodes[a].depth, tree_nodes[b].depth) + 1,
            };
            defer nodes_end += 1;
            tree_parent_nodes[a] = nodes_end;
            tree_parent_nodes[b] = nodes_end;

            node_buf[0] = nodes_end;
            heapSiftDown(&tree_nodes, node_buf[0..heap_end], 0);
        }
        sorted_start -= 1;
        node_buf[sorted_start] = node_buf[0];

        var bit_counts: [16]u16 = @splat(0);
        buildBits(out_bits, &bit_counts, &tree_parent_nodes, node_buf[sorted_start..], max_bits);
        return .{ buildValues(freqs, out_codes, out_bits, bit_counts), last_nonzero };
    }