Continuando nossa série de posts sobre fundamentos em ciências da computação, gostaríamos de apresentar duas estruturas de dados, extremamente relevantes,  que não possuem, até onde sabemos, implementações padrões em .NET: Heap e Binary Heap.

NOTA: A estrutura de dados Heap, apresentada aqui, não tem qualquer relação com a heap (free store). Se você tem interesse em entender mais sobre a heap (free store), recomendamos o post que escrevemos especificamente sobre esse tema.

O que são as estruturas Heap e Binary Heap?

Vejamos a definição de heap disponível na Wikipedia:

In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete^[1] tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C.^[2] The node at the “top” of the heap (with no parents) is called the root node.

Abaixo, a representação gráfica de uma max heap.

Agora, a definição para Binary Heap, também da Wikipedia:

A binary heap is defined as a binary tree with two additional constraints:^[3]

• Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
• Heap property: the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node’s children, according to some total order.

Por que a Binary Heap é importante?

Binary Heap é uma estrutura de dados que permite que construção e manutenção de filas com prioridade (ordenadas), de forma extremamente eficaz (algorítmos de inserção de elementos e de retirada com complexidades extremamente baixas), ocupando muito pouca memória.

Binary Heaps são a base da implementação de um algoritmo de ordenação extremamente interessante, chamado HeapSort, que, nos cenários ruins, é mais eficiente que o QuickSort.

Uma implementação de Binary Heap em C#

A partir das definições apresentada acima, vamos a implementação de uma Binary Heap em C#:

public class Heap<T>
{
    private readonly Func<T, T, int> _priorityCriteria;
    private readonly T[] _data;
    private int _cursor;

    public Heap(int maxCapacity, Func<T, T, int> priorityCriteria)
    {
        _priorityCriteria = priorityCriteria;
        _data = new T[maxCapacity];
        _cursor = 0;
    }

    public void Insert(T value)
    {
        if (_cursor == _data.Length)
        {
            throw new InvalidOperationException("Insert exceeds heap capacity.");
        }

        _data[_cursor++] = value;
        BubbleUp(_cursor - 1);
    }

    public T Peek()
    {
        if (_cursor == 0)
        {
            throw new InvalidOperationException("The heap is empty.");
        }

        return _data[0];
    }

    public T Pop()
    {
        var result = Peek();
        _cursor--;
        _data[0] = _data[_cursor];
        BubbleDown(0);
        return result;
    }

    private void BubbleUp(int position)
    {
        if (!HasParent(position))
        {
            return;
        }

        var parent = Parent(position);
        if (_priorityCriteria(_data[position], _data[parent]) != -1)
        {
            return;
        }

        Swap(position, parent);
        BubbleUp(parent);
    }

    private void BubbleDown(int position)
    {
        if (!HasYoungerChild(position))
            return;

        var c = YoungerChild(position);
        var minIndex = position;

        for (var i = 0; i <= 1; i++)
        {
            if ((c + i) < _cursor)
            {
                if (_priorityCriteria(_data[minIndex], _data[c + i]) == 1)
                {
                    minIndex = c + i;
                }
            }
        }

        if (minIndex != position)
        {
            Swap(position, minIndex);
            BubbleDown(minIndex);
        }
    }

    private void Swap(int i, int j)
    {
        var cache = _data[i];
        _data[i] = _data[j];
        _data[j] = cache;
    }

    private bool HasParent(int position)
    {
        return Parent(position) != -1;
    }

    private static int Parent(int position)
    {
        if (position == 0) return -1;
        var parent = ((position + 1) / 2);
        return parent - 1;
    }

    private bool HasYoungerChild(int position)
    {
        return (YoungerChild(position) < _cursor);
    }

    private static int YoungerChild(int position)
    {
        var result = (position + 1) * 2;
        return result - 1;
    }

    public bool HasValue => _cursor > 0;
}

public class MinHeap<T> : Heap<T> where T : IComparable<T>
{
    public MinHeap(int maxCapacity) : base(
        maxCapacity, (a, b) => a.CompareTo(b)
        )
    { }
}

public class MaxHeap<T> : Heap<T> where T : IComparable<T>
{
    public MaxHeap(int maxCapacity) : base(
        maxCapacity, (a, b) => -a.CompareTo(b)
        )
    { }
}

Perceba que, internamente, Binary Heap é tão econômica quanto a List. Afinal, internamente, usamos um simples array unidimensional para manter os dados.

O principal atrativo é que o elemento com maior/menor chave é determinado em O(1). Afinal, será sempre o nodo raiz da árvore que, por sua vez, estará sempre localizado na primeira posição do vetor.

A adição de um elemento tem complexidade O(log n).  A dinâmica é simples: o item novo sempre é adicionado na primeira posição mais a direita disponível na árvore. Depois, ele vai “subindo” enquanto o elemento pai tiver uma chave de menor prioridade.

A remoção do elemento raiz (a única implementada aqui) também tem complexidade O(log n). Nesse caso, o elemento mais a direita é movido para a raiz (o último elemento do array é copiado para a primeira posição) e vai “descendo” enquanto tiver prioridade menor.

Usando Binary Heap para mesclar coleções ordenadas

Além de facilitar a construção de listas com prioridade, Binary Heaps são excelentes alternativas para mesclar listas ordenadas de maneira ótima. Segue um exemplo rudimentar:

static void Main(string[] args)
{
    var inputs = new List<int[]>
    {
        new[] {1, 4, 5, 7},
        new[] {3, 9, 10},
        new[] {2, 6, 8}
    };
    var merged = MergeOrderedArrays(inputs);

    for (int i = 0; i < merged.Length; i++)
    {
        Console.WriteLine(merged[i]);
    }
}

public static T[] MergeOrderedArrays(IList<T[]> inputs)
    where T : IComparable
{
    var heap = new Heap<ValueTuple<T, int>>(
        inputs.Count,
        (a, b) => a.Item1.CompareTo(b.Item1)
    );

    var indices = new int[inputs.Count];
    var capacity = 0;
    for (var i = 0; i < inputs.Count; i++)
    {
        heap.Insert(new ValueTuple<T, int>(inputs[i][0], i));
        capacity += inputs[i].Length;
    }

    var result = new List(capacity);
    while (heap.HasValue)
    {
        var current = heap.Pop();
        result.Add(current.Item1);
        if (indices[current.Item2] < (inputs[current.Item2].Length - 1))
        {
            indices[current.Item2]++;
            heap.Insert(new ValueTuple<T, int>(inputs[current.Item2][indices[current.Item2]], current.Item2));
        }
    }

    return result.ToArray();
}

Palavras finais

Como dissemos em um post anterior, estranhamos muito que a maioria dos códigos que encontramos em nossos clientes usem apenas List<T> ou Dictionary<K, V>. Imaginemos que muitos programadores não utilizem outras estruturas porque não vêem motivos, o que é grave. Sabemos, porém, que muitos programadores não utilizam outras estruturas porque nem sabem que estas existem, o que é ainda mais grave.

Talvez você não tenha uso direto para Binary Heaps nesse momento. Talvez você ache todo o código que compartilhamos nesse post complexo demais. Entretanto, gostaríamos de salientar que o “conhecimento” dessa estrutura já nos ajudou a resolver problemas críticos em produção.

Compartilhe suas impressões nos comentários.