Кодирование по частотности

class HuffmanTree(Dictionary<char, int> freq_table)
{
    TreeNode treeRoot = BuildHuffmanTree(freq_table);
    
    /// <summary>
    /// Returns binary representation in string format
    /// </summary>
    /// <param name="text"></param>
    /// <returns></returns>
    public Dictionary<char, string> GetEncodings()
    {
        var dict = new Dictionary<char, string>();
        TraverseTree(treeRoot.Left!, dict, "0", 1);
        TraverseTree(treeRoot.Right!, dict, "1", 1);
        return dict;
    }
    
    /// <summary>
    /// 
    /// </summary>
    /// <param name="node"></param>
    /// <param name="dict"></param>
    /// <param name="code">String representation of binary code</param>
    private void TraverseTree(TreeNode node, Dictionary<char, string> dict, string code, int level)
    {
        if (node.IsLeaf)
        {
            dict.Add(node.Letter!.Value.Letter, code);
        }
        else
        {
            TraverseTree(node.Left!, dict, string.Concat(code, "0"),  level + 1);
            TraverseTree(node.Right!, dict, string.Concat(code, "1"), level + 1);
        }
    }
 
    static TreeNode BuildHuffmanTree(Dictionary<char, int> freq_table)
    {
        var nodes = freq_table.Select(x => new TreeNode(new LetterData(x.Key, x.Value))).ToArray();
        var heap = new MinBinaryHeap<int, TreeNode>(nodes, n => n.Freq);
    
        while (heap.Length > 1)
        {
            // logN per operation
            var min1 = heap.DeleteMin();
            var min2 = heap.DeleteMin();
            heap.Insert(new TreeNode(min1, min2));
        }
 
        return heap.DeleteMin();
    }
    
}
 
 
public class TreeNode
{
    public TreeNode(LetterData data)
    {
        Freq = data.Freq;
        Letter = data;
    }
    
    public TreeNode(TreeNode left, TreeNode right)
    {
        Freq = left.Freq + right.Freq;
        Left = left;
        Right = right;
    }
    
    public LetterData? Letter { get; }
 
    public TreeNode? Left { get; }
 
    public TreeNode? Right { get; }
 
    public int Freq { get; }
    
    //IsLeaf == true means not meta node and vice versa
    public bool IsLeaf => Left is null && Right is null;
 
    public override string ToString() =>  $"Letter: {Letter?.Letter.ToString() ?? "NULL"}; IsLeaf: {IsLeaf};  {Freq}";
}
 
 
public readonly struct LetterData(char letter, int freq)
{
    public char Letter { get; } = letter;
 
    public int Freq { get; } = freq;
}

using System.Collections;
using System.Runtime.CompilerServices;
 
namespace ConsoleApp2.HuffmanCodes;
 
/// <summary>
/// Port from https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/MinPQ.java
/// </summary>
/// <typeparam name="TKey"></typeparam>
/// <typeparam name="TNode"></typeparam>
// todo: rethink enumeration?
public class MinBinaryHeap<TKey, TNode> : IEnumerable<TNode>
{
    #region Fields
 
    private readonly Func<TNode, TKey> _keySelector;
    private TNode[] _nodes;
    private readonly Comparer<TKey> _comparer;
 
    #endregion
 
    #region Constructors
 
    public MinBinaryHeap(int capacity, Func<TNode, TKey> keySelector, Comparer<TKey>? comparer = null)
    {
        ArgumentNullException.ThrowIfNull(keySelector);
        ArgumentOutOfRangeException.ThrowIfLessThan(capacity, 0, nameof(capacity));
        _nodes = new TNode[capacity + 1];
        _comparer = comparer ?? Comparer<TKey>.Default;
        _keySelector = keySelector;
        Length = 0;
    }
 
 
    public MinBinaryHeap(Func<TNode, TKey> keySelector) : this(4, keySelector, Comparer<TKey>.Default)
    {
    }
 
    public MinBinaryHeap(TNode[] nodes, Func<TNode, TKey> keySelector, Comparer<TKey>? comparer = null)
    {
        ArgumentNullException.ThrowIfNull(keySelector);
        ArgumentNullException.ThrowIfNull(nodes);
        _keySelector = keySelector;
        _comparer = comparer ?? Comparer<TKey>.Default;
 
        Length = nodes.Length;
        _nodes = new TNode[nodes.Length + 1];
        for (var i = 0; i < Length; i++)
            _nodes[i + 1] = nodes[i];
 
        for (var k = Length / 2; k >= 1; k--)
            Sink(k);
    }
 
    internal MinBinaryHeap(MinBinaryHeap<TKey, TNode> original)
    {
        _keySelector = original._keySelector;
        _comparer = original._comparer;
        Length = original.Length;
        _nodes = new TNode[original._nodes.Length];
        for (var i = 0; i < _nodes.Length; i++)
            _nodes[i] = original._nodes[i];
    }
 
    #endregion
 
    #region Public API
 
    public int Length { get; private set; }
 
    public bool IsEmpty => Length == 0;
 
    public void Insert(TNode x)
    {
        // double size of array if necessary
        if (Length == _nodes.Length - 1) Resize(2 * _nodes.Length);
        // add x, and percolate it up to maintain heap invariant
        _nodes[++Length] = x;
        Swim(Length);
        // assert isMinHeap();
    }
 
    public TNode DeleteMin()
    {
        if (IsEmpty)
            throw new InvalidOperationException("BinaryHeap is empty");
 
        var min = _nodes[1];
        Exchange(1, Length--);
        Sink(1);
        _nodes[Length + 1] = default!; // to avoid loitering and help with garbage collection
        if ((Length > 0) && (Length == (_nodes.Length - 1) / 4))
            Resize(_nodes.Length / 2);
        // assert isMinHeap();
        return min;
    }
    
    public IEnumerator<TNode> GetEnumerator() => new MinHeapEnumerator(this);
    
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 
    #endregion
 
    #region Implementation details
 
    private void Sink(int k)
    {
        while (2 * k <= Length)
        {
            var j = 2 * k;
            if (j < Length && Greater(j, j + 1)) j++;
            if (!Greater(k, j)) break;
            Exchange(k, j);
            k = j;
        }
    }
 
    private void Swim(int k)
    {
        while (k > 1 && Greater(k / 2, k))
        {
            Exchange(k / 2, k);
            k /= 2;
        }
    }
 
    private void Resize(int capacity)
    {
        TNode[] temp = new TNode[capacity];
        for (var i = 1; i <= Length; i++)
        {
            temp[i] = _nodes[i];
        }
 
        _nodes = temp;
    }
 
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private void Exchange(int i, int j) => (_nodes[i], _nodes[j]) = (_nodes[j], _nodes[i]);
 
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private bool Greater(int i, int j) => _comparer.Compare(_keySelector(_nodes[i]), _keySelector(_nodes[j])) > 0;
 
    private class MinHeapEnumerator(MinBinaryHeap<TKey, TNode> heap) : IEnumerator<TNode>
    {
        private TNode? _current;
        private MinBinaryHeap<TKey, TNode> _clone = new(heap);
 
        public bool MoveNext()
        {
            if (_clone.IsEmpty)
                return false;
            
            _current = _clone.DeleteMin();
            return true;
        }
 
        public void Reset() => throw new NotSupportedException("Reset state is not supported in heap enumerators");
 
        TNode IEnumerator<TNode>.Current => _current;
 
        object? IEnumerator.Current => _current;
 
        public void Dispose()
        {
            _current = default!;
            _clone._nodes = null!;
            _clone = null!;
        }
    }
 
    #endregion
}