PAA 2007.1 - Projeto 1 - ABB e Leftist Heap

Nesta questão foram projetadas as estruturas de dados que serão utilizadas nos algoritmos de Árvore Geradora Mínima na questão 1. A complexidade e, consequentemente, os resultados obtidos pelos algoritmos na próxima questão são determinados diretamente pelas estruturas aqui descritas. O relato da complexidade de cada estrutura é fundamental para compreensão da próxima questão.

Parte 1: Árvore Binária Balanceada

Árvores binárias balanceadas (ABBs) são árvores binárias de busca que se auto-ajustam mantendo um limite na altura máxima da árvore. Como a maioria das operações em ABBs dependem da altura da árvore, a estrutura realiza transformações na árvore para tentar manter a altura sempre próxima do mínimo possível de $\log n$. As operações mais comuns em uma ABB e suas respectivas complexidades em relação ao número de nós da árvore são:

Operação Complexidade
Inserção $O(\log n)$
Remoção $O(\log n)$
Busca por elemento $O(\log n)$
Atualizar chave de elemento $O(\log n)$
Inicialização da estrutura
a partir de uma lista de elementos
$O(n \log n)$

Implementação

Para o projeto, escolheu-se utilizar a estrutura set da biblioteca padrão da linguagem C++. Ela é implementada sob forma de uma árvore rubro-negra e provê as operações acima com as complexidades mencionadas, além de permitir acesso em tempo constante ao menor elemento da árvore. Os seguintes métodos da estrutura foram utilizados:

Método Significado Complexidade
c.insert( x ) Insere o elemento x no conjunto c e retorna um iterador para a posição do elemento na árvore $O(\log n)$
c.begin() Retorna um iterador para o primeiro (e menor) elemento presente no conjunto c $O(1)$
c.erase( e ) Remove do conjunto c o elemento apontado pelo iterador e $O(\log n)$

Parte 2: Leftist heaps (lazy e non-lazy)

Heaps são estruturas de dados normalmente utilizadas para implementar filas de prioridade - acesso rápido ao menor elemento do conjunto e construção rápida a partir de um conjunto de elementos quaisquer. Além disso, as heaps binárias costumam ser bastante simples de implementar. Os custos das operações em uma heap são, normalmente:

Operação Complexidade
Inserção $O(\log n)$
Remover mínimo $O(\log n)$
Remoção arbitrária $O(\log n)$
Busca por elemento $O(n)$
Atualizar chave de elemento $O(\log n)$
Inicialização da estrutura
a partir de uma lista de elementos
$O(n)$
Unir duas heaps $O(n)$

Os leftist heaps são heaps binárias em que, diferente das heaps mais comuns, a árvore não necessariamente é completa. As leftist heaps têm a propriedade de "pender" para a esquerda, tendo sub-árvores esquerdas "maiores" do que as direitas. Para definir mais formalmente as leftist heaps, primeiro vamos definir o conceito de caminho nulo:

  • O caminho nulo de uma árvore é definido como o tamanho do menor caminho entre a raiz da árvore e um nó externo, ou seja, caso estejamos fora da árvore o caminho nulo é 0, caso contrário é igual a:

minimo( caminho(no->esquerda), caminho(no->direita) ) + 1

As leftist heaps mantêm, então, a seguinte propriedade:

  • Em uma leftist heap T, o caminho nulo da sub-árvore esquerda têm de ser maior ou igual ao caminho nulo da sub-árvore direita.

Mantendo essa propriedade, os leftist heaps mantêm sempre uma altura de no máximo $\log n$ na sua sub-árvore direita. Podemos então definir as seguintes operações:

Operação Complexidade Descrição
Unir (merge) duas heaps $O(\log n)$ Operação "básica" das leftist heaps, trabalha somente nas sub-árvores direitas, garantindo assim tempo logarítmico.
Inserção $O(\log n)$ Cria-se um novo heap com o elemento e o juntamos ao heap original
Remover mínimo $O(\log n)$ Remove-se a raiz da árvore e uni-se as sub-árvores esquerda e direita
Remoção arbitrária $O(\log n)$ Junta-se os nós filhos que substituem o nó a ser removido
Busca por elemento $O(n)$ É necessário percorrer todos os elementos
Atualizar chave de elemento $O(n)$ É necessário remover e inserir novamente o elemento (ou então "subir")
Inicialização da estrutura a partir de uma lista de elementos $O(n)$ Cria-se um heap unitário para cada elemento e colocam-se todos em uma fila. Enquanto houver mais de um elemento na fila, retira-se os dois primeiros, junta-os e coloca novamente no fim da fila.

Comparando as complexidades das heaps binárias e das leftist heaps, podemos perceber que a segunda é favorecida quando é necessário fazer uniões entre heaps distintas. Um exemplo deste caso será demonstrado no algoritmo Round Robin da próxima questão.

Lazy leftist heaps

Como alternativa à implementação padrão $O(\log n)$ das operações de remoção (mínimo e arbitrária) e de união, pode-se utilizar funções preguiçosas (lazy), adiando a operação até que ela seja estritamente necessária. Na operação de união de duas leftist heaps, por exemplo, pode-se criar um nó "fantasma" (dummy) que tenha como filhos as duas heaps a serem unidas, trazendo o custo da união para $O(1)$. Procedimento semelhante pode ser feito na operação de remoção - ao invés de remover o nó, marcá-lo como dummy. As operações passam a custar $O(1)$ e são adiadas o máximo possível: até o momento em que é necessário obter o valor do nó que está no topo da heap. Nesse momento, é necessário processar a heap e "coletar" os nós ainda existentes - essa operação custa $O(k$ max $\{1,\log (\frac{n}{k+1}) \} )$ onde $k$ é o número de nós dummy descartados do heap. Essas operações de remoção preguiçosa são especialmente úteis quando existe uma maneira implícita de marcar os nós como deletados - um bom exemplo é o algoritmo Round Robin, visto na próxima questão.

Implementação

A implementação das leftist heaps foi feita toda do zero, com código original dos componentes do grupo. Foram criadas classes genéricas (templates) LeftistHeap e LeftistHeapNode.

LeftistHeapNode

A classe LeftistHeapNode encapsula um nó de uma árvore binária do leftist heap. Armazena a chave do nó, ponteiros para os nós filho e para o pai, o tamanho do caminho nulo daquele nó e uma variável para indicar se ele é ou não um nó dummy.

template< class T > class LeftistHeapNode {
    // Each tree node contains the key, the lenght of the null path and
    // pointers to the left, right and parent trees
 
public:
    // key that's stored at each node
    T key;
    // pointer to left and right subtree and pointer to parent
    LeftistHeapNode *left, *right, *parent;
    // size of the path to the closest empty node
    int nullPathLenght;
    // is this a dummy node?
    bool dummy;
(...)

LeftistHeap

A classe LeftistHeap encapsula o leftist heap, armazenando em seu interior a raiz da árvore que representa o heap e possuindo métodos para manipulação do heap, como inserção, união, etc.

template< class T > class LeftistHeap
{
    // A leftist heap encapsules a tree: it is composed
    // of one node (the root) and methods to manipulate nodes
public:
    // the node that is the root of the leftist tree
    LeftistHeapNode<T> *root;

Para construir um novo leftist heap temos três opções de construtor: um deles cria um heap vazio, o segundo cria um heap com um único elemento e o terceiro recebe uma lista de elementos e, em complexidade $O(n)$ converte aquela lista em um heap:

    .
    LeftistHeap() {
        // creates a empty heap
        // time O(1)
        root = NULL;
    }
    LeftistHeap(T k) {
        // creates a heap from a single element
        // time O(1)
        root = new LeftistHeapNode<T>(k);
    }
 
    LeftistHeap(const std::vector<T> &v, 
                             std::vector< LeftistHeapNode<T>* > &ptrs) {
        // makes a heap from a set of elements
        // time O( size(v) )
 
        // creates a queue to store all heaps
        std::deque< LeftistHeap<T>* > q;
 
        // puts all the one-size heaps in the queue
        for (std::vector<T>::const_iterator i = v.begin();
               i != v.end(); i++){
            LeftistHeap<T> *newHeap = new LeftistHeap<T>( *i );
            ptrs.push_back( newHeap->root );
            q.push_back( newHeap );
        }
        // transforms the queue in a leftist heap
        makeHeap(q);
    }

A operação de inserção é semelhante para ambas as versões do leftist heap (preguiçosa ou não):

.
    LeftistHeapNode<T>* insert( T k ) {
        // inserts the element k at the heap in time (log n)
        LeftistHeap<T> *n = new LeftistHeap<T>(k);
        this->merge(n);
        return n->root;
    }

O conjunto de funções que difere entre as versões lazy e non-lazy é composto por:

erase( Node n )
remove o nó n da árvore
top()
retorna o menor elemento do heap
pop()
retira o menor elemento do heap
merge( Heap h )
une com o heap h

Primeiro as versões non-lazy destes métodos:

.
    void erase(LeftistHeapNode<T>* n) {
        // removes the node N from the tree
        // PRE-CONDITION: N should be in the tree!
        LeftistHeapNode<T> *p = n->parent;
 
        // if n is the root of the tree, simply pops the top
        if (p == NULL) {
            pop();
            return;
        }
 
        // garantees that this is a right node of someone
        if (p->right != n)
            swap(p->left,p->right);
        assert( p->right == n );
 
        // makes the left subtree of N the right subtree of the parent
        p->right = n->left;
        if (n->left != NULL)
            n->left->parent = p;
 
        LeftistHeapNode<T> *node = p;
        // while not at the top of the tree
        do {
            // calculates the NPL of the left and right subtree
            int l = (node->left == NULL ? 0 : 
                                         node->left->nullPathLenght);
            int r = (node->right == NULL ? 0 :
                                         node->right->nullPathLenght);
 
            // if the left subtree has a lower NPL than
            // the right one, swaps them
            if (l < r)
                swap(node->left,node->right);
 
            // if the null path lenght hasn't changed, stop
            if (node->nullPathLenght == r+1)
                break;
 
            // adjusts the null path length
            node->nullPathLenght = r+1;
 
            // if this is the root node, breaks
            if (node->parent == NULL)
                break;
 
            // moves to the parent node
            node = node->parent;
        } while (1);
 
        mesh(node,n->right);
    }
    T top() {
        // returns the top (minimum) of the priority queue in time O(1)
        return root->key;
    }

    void pop() {
        // removes the top element of the priority queue in time O(log n)
        LeftistHeapNode<T> *tmp = root;

        if (root->left != NULL)
            root->left->parent = NULL;
        if (root->right != NULL)
            root->right->parent = NULL;
        // joins the left and right subtree
        root = mesh(root->left,root->right);
        delete tmp;
    }
    void merge(LeftistHeap<T> *L) {
        // merges the leftistheap L with the current heap in time O(log n)
        root = mesh(root,L->root);
    }

E a versão "preguiçosa"(lazy) dos métodos:

.
    virtual void lazyErase(LeftistHeapNode<T> *n) {
        n->dummy = true;
    }
    virtual T lazyTop() {
        // finds all node that have NOT been deleted and
        // puts them in "heaps"
        std::deque< LeftistHeap<T>* > heaps;
        purgeDeleted(root, heaps);
 
        // creates a single leftist heap merging all heaps
        makeHeap(heaps);
        assert( root != NULL );
        return root->key;
    }
    virtual void lazyPop() {
        // lazily erases the root node
        root->dummy = true;
    }
    virtual void lazyMerge(LeftistHeap<T> *L) {
        // creates a new dummy root that's the
        // parent of both merging trees
        LeftistHeapNode<T> *newRoot = new LeftistHeapNode<T>();
        newRoot->left = root;
        newRoot->right = L->root;
 
        // adjusts the new dummy root and calculates
        // the new null path lenght
        if (newRoot->right != NULL) {
            if (newRoot->left->nullPathLenght <
                         newRoot->right->nullPathLenght)
                swap(newRoot->left, newRoot->right);    
            newRoot->nullPathLenght =
                         newRoot->right->nullPathLenght+1;
        } else {
            newRoot->nullPathLenght = 1;
        }
        root = newRoot;
    }

Restam ainda demonstrar três métodos fundamentais:

Node* mesh(Node *h1, Node *h2)
Talvez o método mais importante desta estrutura de dados. Realiza e retorna a união (merge) das árvores representadas pelos nós h1 e h2 em tempo $O( \log n )$.
makeHeap(fila< Heap* > q)
Cria um novo leftist heap a partir do conjunto de heaps contido na fila q.
purgeDeleted(Node *n, fila< Heap* > q)
Remove os nós dummy da árvore representada pelo nó n e coloca os heaps resultantes na fila q, para que possam posteriormente ser unidos.
    LeftistHeapNode<T>* mesh(LeftistHeapNode<T>* h1, LeftistHeapNode<T>* h2) {
        // if some heap is null, returns the other one
        if (h1 == NULL)
            return h2;
        if (h2 == NULL)
            return h1;
 
        // guarantees that "SmallKey" has a smaller key than "BigKey"
        LeftistHeapNode<T> *SmallKey, *BigKey;
        if (h1->key > h2->key) {
            SmallKey = h2;
            BigKey = h1;
        } else {
            SmallKey = h1;
            BigKey = h2;
        }
 
        // at this point, we have the guarante that "SmallKey"
        // is the heap with the smaller key, so we can merge
        // "BigKey" with the right subtree of "SmallKey"
        if (SmallKey->right == NULL) {
            // if "SmallKey" doesn't have a right subtree,
            // we can just "hang" "BigKey" as the
            // right subtree
            SmallKey->right = BigKey;
            BigKey->parent = SmallKey;
        } else {
            // if "SmallKey" has a right subtree,
            // we join this subtree with "BigKey"
            SmallKey->right = mesh(SmallKey->right,BigKey);
            if (SmallKey->right == BigKey)
                BigKey->parent = SmallKey;
        }
 
        // if there's no left subtree OR if the left subtree
        // is "shorter" than the
        // right one, switch subtrees
        if (SmallKey->left == NULL ||
            SmallKey->left->nullPathLenght <
                       SmallKey->right->nullPathLenght)
            swap(SmallKey->left,SmallKey->right);
 
        // recalculate the null path lenght
        SmallKey->nullPathLenght = (SmallKey->right != NULL ?
            SmallKey->right->nullPathLenght + 1 : 1);
        return SmallKey;
    }
    void makeHeap(std::deque< LeftistHeap<T>* > &q) {
        // while there's still an element at the queue
        while(q.size() > 1) {
            // removes the first two elements from
            // the line and merges them
            LeftistHeap<T> *first = q.front(), *second;
            q.pop_front();
            second = q.front();
            q.pop_front();
            first->merge(second);
            // puts the result of the merge back on the queue
            q.push_back(first);
        }

        // the current object is the last element in the queue
        *this = *q.front();
        delete q.front();
    }
    virtual void purgeDeleted(LeftistHeapNode<T> *n,
                                      std::deque< LeftistHeap<T>* > &q) {
        // if it's an empty node, return the empty list
        if (n == NULL)
            return;

        // if it's not a dummy node, puts the node in the list
        if (n->getDummy() == false) {
            LeftistHeap<T> *h = new LeftistHeap<T>;
            h->root = n;
            q.push_back( h );
        } else {
            // if it's a dummy node, return the
            // purge of it's left and right child
            purgeDeleted(n->left, q);
            purgeDeleted(n->right, q);
        }
    }

Especialização para os algoritmo Prim e Round Robin

No algoritmo Round Robin e Prim que utilizam a estrutura lazy, a remoção "preguiçosa" das arestas é feita de forma implícita - arestas que já estão na mesma árvore são consideradas dummy ou removidas. Por esse motivo, foi necessário especializar a classe LeftistHeap para que as operações lazy possam levar em conta a conexão atual das árvores. Foi criada uma classe LazyLeftistHeap, que herda de LeftistHeap e fixa o gabarito para que a classe armazene arestas. Os métodos purgeDeleted e lazyTop tiveram de ser reescritos e agora recebem como parâmetro um objeto do tipo UnionFind que controla a união das árvores.

class LazyLeftistHeap : public LeftistHeap<edge> {
    (...)
    virtual void purgeDeleted(LeftistHeapNode<edge> *n, UnionFind
                           &uf, std::deque< LeftistHeap<edge>* > &q) {
        // if it's an empty node, return the empty list
        if (n == NULL)
            return;
 
        // the node is considered dummy if it's marked dummy or
        // if it's and edge between two nodes already connected
        if (n->getDummy() == true ||
                uf.sameClass(n->key.second.first,
                                  n->key.second.second)) {
            // if it's a dummy node, return the
            // purge of it's left and right child
            purgeDeleted(n->left,uf,q);
            purgeDeleted(n->right,uf,q);
        } else {
            // if it's not a dummy node, return the node
            LeftistHeap<edge> *h = new LeftistHeap<edge>;
            h->root = n;
            q.push_back( h );
        }
    }
    virtual edge lazyTop(UnionFind &uf) {
        // removes all 
        std::deque< LeftistHeap<edge>* > heaps;
        purgeDeleted(root,uf,heaps);
 
        // creates the heap
        makeHeap(heaps);
        assert( root != NULL );
        return root->key;
    }

Extra: Union-Find

Para a implementação do algoritmo Round Robin foi necessária a implementação de uma estrutura de Union Find, para controlar quais árvores já foram unidas (ou, de outra maneira, quais os componentes conexos que ainda restam). A estrutura foi implementada seguindo as orientações dadas em sala, com as duas heurísticas de compressão de caminho e união por altura. A estrutura de UnionFind prevê as seguintes operações:

Operação Complexidade Descrição
unionClass(a,b) $O(1)$ Realiza a união dos dois conjuntos a e b.
sameClass(a,b) $O(1)$ Os conjuntos a e b são o mesmo?
getClass(a) $O(\alpha(n))$ =~ $O(1)$ Retorna o representante da classe de a.
class UnionFind {
private:
    // father and height
    int *pai, *altura;
    // number of original sets
    int size;
 
public:
    UnionFind(int s) {
        // creates a new union find structure with S disjoint sets
        size = s;
        pai = new int[size];
        altura = new int[size];
        clear();
    }
 
    ~UnionFind() {
        // clears memory
        delete pai;
        delete altura;
    }
 
    bool sameClass(int a, int b) {
        // are A and B in the same class?
        return getClass(a) == getClass(b);
    }
 
    void unionClass(int a, int b) {
        // joins the classes of A and B
        if (a != b) {
            int cl[2] = {getClass(a),getClass(b)};
            if (cl[0] != cl[1]) {
                // always put the smaller one below the
                // bigger one (rank heuristic)
                if (altura[cl[0]] > altura[cl[1]])
                    pai[cl[1]] = cl[0];
                else {
                    pai[cl[0]] = cl[1];
                    // if both sets had the same height,
                    // increment the height
                    if (altura[cl[0]] == altura[cl[1]]) altura[cl[1]]++;
                }
            }
        }
    }
 
    void clear() {
        // clears the structure, reseting all data
        for (int i=0;i<size;i++) {
            pai[i] = i;
            altura[i] = 0;
        }
    }
 
    int getClass(int a) {
        // returns the class of the node "a"
        if (a != pai[a])
            // path compression
            pai[a] = getClass(pai[a]);
        return pai[a];
    }
};
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.