INF1010 3WB – T3: Implementação de uma lista de prioridades genérica – uso de templates.

Enunciado:

Implemente uma classe template Heap, em C++, respeitando o seguinte:

1. Utilize uma estrutura de Heap (de mínimo) para armazenar os elementos utilizando a ordem numérica das suas chaves (inteiras).
2. Cada elemento tem, além da sua chave que indica a sua prioridade no heap, um dado que pode ser de qualquer tipo (tipos básicos ou outras classes, structs, etc). Este dado não é considerado na prioridade do elemento, é simplesmente armazenado, consultado e removido da estrutura.
3. Somente é possível obter ou remover o elemento de menor chave (do topo).
4. Utilize a interface mostrada no arquivo t3_heap.h para sua classe.
5. É permitido criar funções ou variáveis membro privadas, para facilitar a implementação.
6. ATENÇÃO: Para este trabalho, em que estamos criando uma classe template, implemente todas as funções no .h

t3_heap.h

#ifndef T3_HEAP_H
#define T3_HEAP_H

#include <vector>
#include <string>

template< typename T >
class Heap /* Min-Heap */
{
public:
    //Construtor vazio
    Heap();

    //Constroi o heap a partir de um vetor de elementos
    Heap(const std::vector<int>& chaves, const std::vector<T>& valores);

    //Destroi o heap
    ~Heap();

    //Retorna o numero de elementos atualmente no heap
    unsigned int tamanho();

    //Insere um novo elemento
    void insere(int chave, T valor);

    //Retorna a chave do elemento do topo
    int chaveTopo();

    //Retorna o valor do elemento do topo
    T valorTopo();

    //Remove o elemento do topo
    void remove();

    //Exibe os elementos do heap
    void mostra(const std::string& title);

private:
    struct HeapNo
    {
        int _chave;
        T _valor;
    };

    //Contem os elementos do heap
    std::vector<HeapNo> _elementos;

     /* Funcoes e membros privados que julgar necessarios */
};

#endif // T3_HEAP_H