(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)