3 dezembro, 2015 3 Comentários AUTOR: elemarjr CATEGORIAS: Sem categoria

Olá "Binary Heap"!

Tempo de leitura: 4 minutos

Você dá atenção para estruturas de dados? Não? Eu acho que você deveria.

Nesse post, falo um pouco sobre Heap.

O que é um Heap?

Vamos pegar a definição da Wikipedia:

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap. A heap can be classified further as either a "max heap" or a "min heap". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node.

Vamos revisitar, por partes:

In computer science, a heap is a specialized tree-based data structure...

 

Todo mundo, em algum momento escreveu uma árvore de dados.

...that satisfies the heap property: If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap.

Aqui a coisa fica um pouco confusa. Mas, de forma geral:

  • se chave do objeto presente no "nodo raiz" da árvore for menor que a de seus filhos, então, todos os nós deverão ter objetos cujo as chaves sejam também menores que as de seus respectivos filhos.
  • se a chave no "nodo raiz" da árvore for maior que a de seus filhos, então, todos os nós deverão ter objetos cujo as chaves sejam também maiores que as de seus respectivos filhos.

Avancemos,

... A heap can be classified further as either a "max heap" or a "min heap". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node.

Quando a chave do objeto no nodo raiz tiver o valor mais alto da árvore, temos um max heap. Toda vez que o valor for menor, temos um min heap.

Ficou mais claro? Eis um max heap.

501px-Max-Heap.svg

Entendeu?

Binary Heap

Voltando a definição da Wikipedia:

A binary heap is a heap data structure created using a binary tree.  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.

Pegou?

Uma implementação em C#

Até onde eu saiba, .NET não possui Binary Heaps implementadas. Então, vamos a minha:

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&#91;minIndex&#93;, _data&#91;c + i&#93;) == 1)
                {
                    minIndex = c + i;
                }
            }
        }

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

    private void Swap(int i, int j)
    {
        var cache = _data&#91;i&#93;;
        _data&#91;i&#93; = _data&#91;j&#93;;
        _data&#91;j&#93; = 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;
    }

    //private bool HasOlderChild(int position)
    //{
    //    return (OlderChild(position) < _cursor);
    //}
    //
    //private static int OlderChild(int position)
    //{
    //    var result = (position + 1) * 2;
    //    return result;
    //}

    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)
        )
    { }
}

Uma das coisas mais legais da implementação de uma Binary Heap é que podemos usar um vetor normal para armazenar dados.

O principal atrativo é que o elemento com maior/menor chave é determinado em O(1). Afinal, será sempre o nodo raiz que 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 raíz (o último elemento do array é copiado para a primeira posição) e vai "descendo" enquanto tiver prioridade menor.

Quando usar um heap

Heaps são excelentes quando precisamos obter rapidamente valores mínimos e valores máximos de uma coleção consumindo pouca memória (baixa complexidade de armazenamento).

Heapsort: ordenação baseada na estrutura de dados

Implementar ordenação é muito simples usando um heap.

[Test]
public void BasicOrdering()
{
    var heap = new MinHeap<int>(5);
    heap.Insert(5);
    heap.Insert(7);
    heap.Insert(3);
    heap.Insert(8);
    heap.Insert(4);

    heap.Pop().Should().Be(3);
    heap.Pop().Should().Be(4);
    heap.Pop().Should().Be(5);
    heap.Pop().Should().Be(7);
    heap.Pop().Should().Be(8);

    heap.HasValue.Should().Be.False();
}

O teste demonstra que adiciono elementos em ordem aleatória e obtenho a lista de forma ordenada.

public T[] HeapSort<T>(T[] input)
    where T: IComparable<T>
{
    var heap = new MinHeap<T>(input.Length);
    for (var i = 0; i < input.Length; i++)
    {
        heap.Insert(input&#91;i&#93;);
    }

    var result = new T&#91;input.Length&#93;;
    for (var i = 0; i < input.Length; i++)
    {
        result&#91;i&#93; = heap.Pop();
    }
    return result;
}
&#91;/code&#93;

A complexidade desse algoritmo é O(n log n).

<h3>Um exemplo interessante de uso</h3>
Considere que você possua diferentes listas ordenadas que você desejaria mesclar. Como implementar esta "mescla" das listas considerando que você precise usar pouca memória?

Eis uma ideia de implementação usando o poder do heap (inspirada em um exemplo comum):


public static T[] MergeOrderedArrays<T>(List<T&#91;&#93;> inputs)
    where T: IComparable<T>
{
    var heap = new Heap<Tuple<T, int>>(
        inputs.Count,
        (a, b) => a.Item1.CompareTo(b.Item1)
        );

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

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

    return result.ToArray();
}

Um pequeno teste.

[Test]
public void MergeTest()
{
    var inputs = new List<int&#91;&#93;>
    {
        new[] {1, 4, 5, 7},
        new[] {3, 9, 10},
        new[] {2, 6, 8}
    };

    MergeOrderedArrays(inputs).Should().Have.SameSequenceAs(
        new[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
        );
}

Era isso.

3 Comentários

  1. acazsouza 1 ano ago says:

    Muito bom.
    Estava pensando aqui como era o uso dela na memoria HEAP do .Net.
    Parecem ser 8 HEAPs separados por tipo de objetos:

    1 - Loader Heap: contains CLR structures and the type system
    2 - High Frequency Heap: statics, MethodTables, FieldDescs, interface map
    3 - Low Frequency Heap: EEClass, ClassLoader and lookup tables
    4 - Stub Heap: stubs for CAS, COM wrappers, P/Invoke
    5 - Large Object Heap: memory allocations that require more than 85k bytes
    6 - GC Heap: user allocated heap memory private to the app
    7 - JIT Code Heap: memory allocated by mscoreee (Execution Engine) and the JIT compiler for managed code
    8 - Process/Base Heap: interop/unmanaged allocations, native memory, etc

    E no caso seriam MIN HEAPs porque teriam que sempre buscar com maior frequência os objetos de generations mais baixas (generation 0, 1, 2).

    Responder