Estruturas de dados Heap e Binary Heap (em C#)

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.

Compartilhe este insight:

Comentários

Participe deixando seu comentário sobre este artigo a seguir:

Subscribe
Notify of
guest
0 Comentários
Inline Feedbacks
View all comments

AUTOR

Elemar Júnior
Fundador e CEO da EximiaCo atua como tech trusted advisor ajudando empresas e profissionais a gerar mais resultados através da tecnologia.

NOVOS HORIZONTES PARA O SEU NEGÓCIO

Nosso time está preparado para superar junto com você grandes desafios tecnológicos.

Entre em contato e vamos juntos utilizar a tecnologia do jeito certo para gerar mais resultados.

Insights EximiaCo

Confira os conteúdos de negócios e tecnologia desenvolvidos pelos nossos consultores:

Arquivo

Pós-pandemia, trabalho remoto e a retenção dos profissionais de TI

CTO Consulting e Especialista em Execução em TI
0
Queremos saber a sua opinião, deixe seu comentáriox
Masterclass

O Poder do Metamodelo para Profissionais Técnicos Avançarem

Nesta masterclass aberta ao público, vamos explorar como o Metamodelo para a Criação, desenvolvido por Elemar Júnior, pode ser uma ferramenta poderosa para alavancar sua carreira técnica em TI.

A sua inscrição foi realizada com sucesso!

O link de acesso à live foi enviado para o seu e-mail. Nos vemos no dia da live.

Muito obrigado!

Deu tudo certo com seu envio!
Logo entraremos em contato

Estruturas de dados Heap e Binary Heap (em C#)

Para se candidatar nesta turma aberta, preencha o formulário a seguir:

Estruturas de dados Heap e Binary Heap (em C#)

Para se candidatar nesta turma aberta, preencha o formulário a seguir:

Condição especial de pré-venda: R$ 14.000,00 - contratando a mentoria até até 31/01/2023 e R$ 15.000,00 - contratando a mentoria a partir de 01/02/2023, em até 12x com taxas.

Tenho interesse nessa capacitação

Para solicitar mais informações sobre essa capacitação para a sua empresa, preencha o formulário a seguir:

Tenho interesse em conversar

Se você está querendo gerar resultados através da tecnologia, preencha este formulário que um de nossos consultores entrará em contato com você:

O seu insight foi excluído com sucesso!

O seu insight foi excluído e não está mais disponível.

O seu insight foi salvo com sucesso!

Ele está na fila de espera, aguardando ser revisado para ter sua publicação programada.

Tenho interesse em conversar

Se você está querendo gerar resultados através da tecnologia, preencha este formulário que um de nossos consultores entrará em contato com você:

Tenho interesse nessa solução

Se você está procurando este tipo de solução para o seu negócio, preencha este formulário que um de nossos consultores entrará em contato com você:

Tenho interesse neste serviço

Se você está procurando este tipo de solução para o seu negócio, preencha este formulário que um de nossos consultores entrará em contato com você:

× Precisa de ajuda?