Estruturas de Dados

(conteúdo referente à aula de 18(?)/junho/2009 para os calouros, por Eduardo)

Pilha

Talvez a estrutura de dados mais simples. Do tipo LIFO (Last In First Out), esta estrutura possui quatro operações básicas:

  • bool eh_vazia()
  • void insere(int x)
  • int topo()
  • void remove_topo()

Pode ser implementada em C com um vetor, e uma variável que indique a quantidade de elementos na pilha. Esta variável serve também para identificar a posição do topo, agilizando inserções e exclusões. Algo como…

int topo=0, pilha[100];
bool eh_vazia() { return (bool)(topo == 0); }
void insere(int x) { pilha[topo++] = x; }
int topo() { return pilha[topo-1]; }
void remove_topo() { topo--; }

Na STL (C++), temos uma pilha pronta no cabeçalho stack. As funções são análogas:

  • bool empty()
  • void push(int x)
  • int top()
  • void pop()

Fila

A fila é uma estrutura do tipo FIFO (First In First Out). Sua implementação em C é um pouco mais complicada para aproveitar ao máximo o espaço alocado, e não será tratada aqui. Na STL (C++), temos uma fila pronta no cabeçalho queue, e as operações básicas são:

  • bool empty()
  • void push(int x)
  • int front()
  • void pop()

Abaixo um pequeno exemplo de uso de fila e pilha com STL, para ilustrar a diferença:

#include <stdio.h>
#include <queue>
#include <stack>
using namespace std;
 
int main() {
    queue<int> Q;
    stack<int> S;
    for (int i=1; i <= 10; i++) {
        printf("inseri %2d na fila e pilha\n", i);
        Q.push(i);
        S.push(i);
    }
    printf("\n");
    while (!Q.empty()) {
        printf("retirei %2d da fila e %2d da pilha\n", Q.front(), S.top());
        Q.pop();
        S.pop();
    }
 
    return 0;
}

Árvores

(completarei com o conteúdo de árvores (genéricas, binárias e binárias de busca) depois…)

Heap (Fila de prioridades)

Uma heap é uma árvore binária especial. Elas podem ser máximas ou mínimas. Na STL, a implementação de heap é máxima, então por motivos didáticos descreveremos uma heap máxima. Seus níveis são preenchidos da esquerda para direita, não havendo "buracos". Assim, com exceção do último nível, onde todos os nós estão o mais à esquerda possível, todos os seus níveis são completos.

Todo elemento da heap máxima deve atender à seguinte propriedade:

  • o elemento não possui nenhum filho maior do que ele mesmo

Por ter seus níveis completamente preenchidos, podemos representá-la em um vetor de acordo com a seguinte regrinha:

  • a posição 0 representa a raíz
  • o filho esquerdo do nó i está na posição (2*i+1)
  • o filho direito do nó i está na posição (2*i+2)
  • o pai do nó j está na posição ((j-1)/2)

Com isso, é fácil ver que teremos o maior elemento como a raíz da árvore, sendo de acesso imediato (posição 0 do vetor). Quando quisermos remover este elemento, é necessário manter as propriedades da árvore válidas. Assim, uma remoção segue o seguinte pseudo-código:

#define ESQ(i) (2*i+1)
#define DIR(i) (2*i+2)
int heap[100];
void remove_topo_da_heap() {
    remove_elemento_do_topo(); // apenas conceitual
    pega_o_ultimo_elemento_do_vetor_e_coloca_no_topo(); // sobrescreve a posição 0
    int cur = 0;
    while (heap[ESQ(cur)] > heap[cur] || heap[DIR(cur)] > heap[cur]) {
        // este é um pseudo-código, e não estamos testando se existe
        // um nó nas posições ESQ(cur) e DIR(cur)...
        //  em C, esta checagem é necessária
 
        // vamos ter que alternar o nó corrente com seus filhos até que
        // a propriedade seja respeitada
        if (heap[ESQ(cur)] > heap[cur] && heap[DIR(cur)] > heap[cur]) {
            // ambos são maiores, temos que escolher o maior dos dois
            if (heap[ESQ(cur)] > heap[DIR(cur)]) {
                swap(heap[ESQ(cur)], heap[cur]);
                cur = ESQ(cur);
            }
            else {
                swap(heap[DIR(cur)], heap[cur]);
                cur = DIR(cur);
            }
        }
        else if (heap[ESQ(cur)] > heap[cur]) {
            swap(heap[ESQ(cur)], heap[cur]);
            cur = ESQ(cur);
        }
        else { // heap[DIR(cur)] > heap[cur]
            swap(heap[DIR(cur)], heap[cur]);
            cur = DIR(cur);
        }
    }
}

Se o maior elemento era a raíz, o segundo maior elemento era, com certeza, um de seus filhos, embora não seja claro num primeiro momento qual deles. Após a execução do código acima, um dos filhos da raíz assumiu a posição de raíz, e o elemento que colocamos no topo foi sendo movido para uma posição em que não quebre a propriedade.

A inserção segue um processo análogo: o nó é inserido na primeira posição livre do vetor (ou seja, fica como o último nó do último nível da árvore) e vai sendo movido para cima enquanto for maior que seus pais.

Pelas propriedades do heap, os nós serão removidos em ordem decrescente, não importando a ordem em que foram inseridos (diferentemente da pilha e da fila). Segue código de exemplo em C++:

#include <stdio.h>
#include <queue>
using namespace std;
 
int main() {
    priority_queue<int> PQ;
    for (int i=1; i <= 5; i++) {
        printf("inserindo %2d no heap\n", i); PQ.push(i);
        printf("inserindo %2d no heap\n", 10-i+1); PQ.push(10-i+1);
    }
    printf("\n");
    while (!PQ.empty()) {
        printf("removendo %2d do heap\n", PQ.top());
        PQ.pop();
    }
 
    return 0;
}

Union-Find

(falaremos de union-find depois, quando falarmos de árvore geradora mínima em grafos)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License