Conjuntos disjuntos
Numa estrutura de dados para conjuntos disjuntos queremos suportar as seguintes operações:
- dado um elemento, determinar em que conjunto ocorrer;
- dados dois elementos em conjunto diferentes, unir os dois conjuntos a que pertencem.
Assumamos que temos $n$ elementos e que cada elemento é representado por um inteiro de $0\leq i < n$.
Exemplos com $n=9$:
- suponhamos que temos os conjuntos $\{0\}$, $\{1\}$, $\{2, 3, 9\}$, $\{7\}$, $\{4, 8\}$ e $\{5, 6\}$;
- os objectos $2$ e $9$ estão no mesmo conjunto, mas o $3$ e $8$ não estão;
- a união dos conjuntos com os elementos $3$ e $8$ resulta nos conjuntos $\{0\}$, $\{1\}$, $\{2, 3, 4, 8, 9\}$, $\{7\}$ e $\{5, 6\}$.
Questão: como é que conseguimos suportar estas operações de forma eficiente? data/netdyn/visitors.log O número de elementos pode ser grande, mas o número de procuras e o número de uniões pode ainda ser muito maior. Denotemos o número de uniões por $m$. Portanto, como é podemos suportar de forma eficiente $m >> n$ uniões? Notar que numa união temos de fazer duas procuras para determinar em que conjunto estão os elementos.
É claro que podemos representar os conjuntos com listas ligadas, caso em que as operações de procura terão um custo elevado (qual é o tempo de procura numa lista?), ou com árvores binárias binárias, caso em que as uniões podem não ser triviais se quisermos manter as árvores balanceadas (mas é possível, como?).
No que se segue vamos utilizar apenas vectores e, na prática, vamos considerar árvores n-árias. O vector pi representa essa árvore guardando em pi[i] o pai de i na árvore. Desta forma, representado cada conjunto com a raiz da árvore, a união de dois conjuntos consiste em dizer que o pai da raiz de um dos conjuntos é raiz do outro conjunto, o que na prática é uma atribuição e tem custo $O(1)$.
Mas temos um problema, as árvores podem não estar balanceadas e a procura pode demorar muito tempo. Vamos então utilizar a seguinte heurística, na união de dois conjuntos seleccionamos para raiz do novo conjunto a raiz cujo conjunto tiver maior profundidade.
Vamos ainda considerar uma segunda heurística: dado um elemento, uma vez que na procura queremos sempre saber quem é a raiz desse conjunto, se o pai de um elemento não for a raiz desse conjunto, vamos "aproximá-lo" da raiz através da compressão rápida do caminho até à raiz.
Através da utilização destas duas heurísticas, assumindo que temos $n$ elementos e $m$ operações de união, conseguimos realizar todas estas operações em tempo $O(m\ \alpha(m,n))$ em que $\alpha$ é a inversa da função de Ackermann. Vamos notar apenas que para qualquer valor realista de $n$ e $m$, a função $\alpha$ toma um valor inferior a 5 e, portanto, podemos assumir na prática que as $m$ operações ocorrem em tempo linear. É importante no entanto ter em conta que estamos a contabilizar o custo conjunto das $m$ operações, e não o custo individual de cada operação. Este tipo de análise de complexidade denomina-se por análise amortizada e será objecto de estudo em disciplinas mais avançadas, pelo que não detalharemos aqui a demonstração deste limite que pode ser encontrada, por exemplo, no livro Introduction to Algorithms de T. Cormen, C. Leiserson, R. Rivest e C. Stein.
Vejamos uma possível implementação em C. Ficheiro unfnd.h:
#ifndef UNFND_H #define UNFND_H typedef struct _disjoint_set *disjoint_set; disjoint_set make_set(int); void union_set(disjoint_set, int, int); int same_set(disjoint_set, int, int); int find_set(disjoint_set, int); #endif /* UNFND_H */
Ficheiro unfnd.c:
#include <limits.h>
#include <stdlib.h>
#include "unfnd.h"
struct _disjoint_set {
int sz;
struct { int pi, rank; } my[1];
};
disjoint_set
make_set(int sz)
{
disjoint_set set;
int i;
if (sz == 0)
return NULL;
set = malloc(sizeof(int) + 2 * sizeof(int) * sz);
if (set == NULL)
return NULL;
set->sz = sz;
for (i = 0; i < sz; i++) {
set->my[i].pi = i;
set->my[i].rank = 0;
}
return set;
}
int
find_set(disjoint_set set, int i)
{
if (set == NULL || i < 0 || i >= set->sz)
return UINT_MAX;
for (; i != set->my[i].pi; i = set->my[i].pi)
set->my[i].pi = set->my[set->my[i].pi].pi;
return i;
}
int
same_set(disjoint_set set, int i, int j)
{
int i_root, j_root;
if (set == NULL || i < 0 || j < 0 || i >= set->sz || j >= set->sz)
return 0;
return find_set(set, i) == find_set(set, j);
}
void
union_set(disjoint_set set, int i, int j)
{
int i_root, j_root;
if (set == NULL || i < 0 || j < 0 || i >= set->sz || j >= set->sz)
return;
i_root = find_set(set, i);
j_root = find_set(set, j);
if (i_root == j_root)
return;
if (set->my[i_root].rank > set->my[j_root].rank)
set->my[j_root].pi = i_root;
else if (set->my[i_root].rank < set->my[j_root].rank)
set->my[i_root].pi = j_root;
else { /* set->my[i_root].rank == set->my[j_root].rank */
set->my[i_root].pi = j_root;
set->my[j_root].rank ++;
}
}Filas com prioridade
Uma fila com prioridade é um estrutura de dados que suporta pelo menos as seguintes operações:
- inserir um elemento na fila com uma dada prioridade associada;
- retirar o elemento na fila com maior prioridade.
Em geral queremos também suportar a actualização da prioridade de um dado elemento e que, por norma, corresponde a aumentar a prioridade do mesmo.
Ainda que possamos implementar filas com prioridade de muitas formas diferentes, utilizando por exemplo listas ligadas ou vectores, muitas vezes recorremos a amontoados. De facto a utilização de amontoados na implementação de filas com prioridade garante em geral a melhor eficiência para as operações acima e, no que se segue, vamos ver como implementar uma fila com prioridade com base em amontoados binários. Notar no entanto que, dependendo do problema, pode ser preferível utilizar outra estratégia de implementação não envolvendo sequer amontoados.
Tal como vimos no estudo do algoritmo Heap sort, a extração do elemento com maior chave de um amontoado binário pode ser efectuada em $O(\log n)$ tempo. Vimos também que as operações de correcção do amontoado, por exemplo quando mudamos uma chave, pode ser também ser feita em $O(\log n)$ com as operações fixDown e fixUp. Por outro lado, podemos ignorar a natureza das chaves, ou seja, não nos interessa se são inteiros ou reais ou sequências de caracteres, desde que tenhamos definida uma ordem total sobre os elementos.
Na implementação que se segue vamos gerir um conjunto de elementos de forma indirecta, assumindo que a colecção de elementos a gerir está guardada num vector definido pelo utilizador da nossa implementação e que vamos apenas gerir os índices desse vector tendo em conta uma função de comparação. Desta forma não nos temos de preocupar com o tipo dos elementos que estamos a gerir.
Nesta implementação utilizamos um vector map que nos indica a posição map[i] no amontoado onde está localizado o elemento com o índice i, e o vector heap que representa o amontoado e é tal que heap[i] guarda o índice do elemento no vector original. O vector original key é dado pelo cliente e denota o vector onde estão guardados os elementos. O número máximo n de elementos é definido na inicialização e não pode ser alterado depois. No entanto, os n elementos não precisam de existir logo no vector key (ver macro BINHEAP_MAKE).
Nesta implementação disponibilizamos as operações como macros que invocam as funções que operam sobre o amontoado.
Ficheiro binheap.h:
#ifndef _BINHEAP_H_
#define _BINHEAP_H_
#include <limits.h>
#include <stdlib.h>
#include <string.h>
struct binheap {
size_t size;
size_t max_size;
size_t *heap;
size_t *map;
void *key;
size_t ksz;
int (*cmp)(const void *,const void *);
};
#define LEFT(x) ((((x) + 1) << 1) - 1)
#define RIGHT(x) (((x) + 1) << 1)
#define PARENT(x) ((((x) + 1) >> 1) - 1)
#define BINHEAP_INIT(q, type, k, n, c) do { \
(q) = malloc(sizeof(struct binheap)); \
(q)->max_size = (n); \
(q)->size = 0; \
(q)->heap = malloc(sizeof(size_t)*(n)); \
memset((q)->heap, 0xFF, sizeof(size_t)*(n)); \
(q)->map = malloc(sizeof(size_t)*(n)); \
memset((q)->map, 0xFF, sizeof(size_t)*(n)); \
(q)->key = (k); \
(q)->ksz = sizeof(type); \
(q)->cmp = (c); \
} while (/*CONSTCOND*/0)
#define BINHEAP_FREE(q) do { \
free((q)->heap); \
free((q)->map); \
free(q); \
} while (/*CONSTCOND*/0)
#define BINHEAP_EMPTY(q) ((q)->size == 0)
#define BINHEAP_HAS(q, id) ((q)->map[id] < (q)->size)
#define BINHEAP_TOP(q) ((q)->heap[0])
#define BINHEAP_RESET(q) do { \
(q)->size = 0; \
memset((q)->heap, 0xFF, sizeof(size_t)*(q)->max_size); \
memset((q)->map, 0xFF, sizeof(size_t)*(q)->max_size); \
} while (/*CONSTCOND*/0)
#define BINHEAP_PUSH(q, id) do { \
if ((q)->map[id] >= ULONG_MAX) { \
if ((q)->size >= (q)->max_size) \
abort(); \
\
(q)->map[id] = (q)->size; \
(q)->heap[(q)->size] = (id); \
(q)->size ++; \
} \
binheap_siftup((q)->key, (q)->heap, (q)->map, (q)->size, \
(q)->ksz, (q)->map[id], (q)->cmp); \
binheap_siftdown((q)->key, (q)->heap, (q)->map, (q)->size, \
(q)->ksz, (q)->map[id], (q)->cmp); \
} while (/*CONSTCOND*/0)
#define BINHEAP_UPDATE(q, id) BINHEAP_PUSH(q, id)
#define BINHEAP_DEL(q, id) do { \
register size_t aux = (q)->map[id]; \
q->size--; \
if (q->size != aux) { \
binheap_exchange((q)->heap, (q)->map, (q)->size, aux); \
binheap_siftup((q)->key, (q)->heap, (q)->map, (q)->size, \
(q)->ksz, aux, (q)->cmp); \
binheap_siftdown((q)->key, (q)->heap, (q)->map, (q)->size, \
(q)->ksz, aux, (q)->cmp); \
} \
q->heap[q->size] = ULONG_MAX; \
q->map[id] = ULONG_MAX; \
} while (/*CONSTCOND*/0)
#define BINHEAP_POP(q) do { \
register size_t aux = q->heap[0]; \
q->size--; \
binheap_exchange((q)->heap, (q)->map, (q)->size, 0); \
binheap_siftdown((q)->key, (q)->heap, (q)->map, (q)->size, \
(q)->ksz, 0, (q)->cmp); \
q->heap[q->size] = ULONG_MAX; \
q->map[aux] = ULONG_MAX; \
} while (/*CONSTCOND*/0)
#define BINHEAP_MAKE(q, n) do { \
(q)->size = (n); \
binheap_make((q)->key, (q)->heap, (q)->map, \
(q)->size, (q)->ksz, (q)->cmp); \
} while (/*CONSTCOND*/0)
void binheap_exchange(size_t *heap, size_t *map, size_t i, size_t j);
void binheap_make(void *key, size_t *heap, size_t *map, size_t n,
size_t size, int(*cmp)(const void *, const void *));
void binheap_siftdown(void *key, size_t *heap, size_t *map, size_t n,
size_t size, size_t i, int(*cmp)(const void *, const void *));
void binheap_siftup(void *key, size_t *heap, size_t *map, size_t n,
size_t size, size_t i, int(*cmp)(const void *, const void *));
#endif /* _BINHEAP_H_ */Ficheiro binheap.c:
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define LEFT(x) ((((x) + 1) << 1) - 1)
#define RIGHT(x) (((x) + 1) << 1)
#define PARENT(x) ((((x) + 1) >> 1) - 1)
void
binheap_exchange(size_t *heap, size_t *map, size_t i, size_t j)
{
size_t v;
assert(map[heap[i]] == i && map[heap[j]] == j);
map[heap[i]] = j;
map[heap[j]] = i;
v = heap[i];
heap[i] = heap[j];
heap[j] = v;
assert(map[heap[i]] == i && map[heap[j]] == j);
}
void
binheap_siftdown(void *key, size_t *heap, size_t *map, size_t n, size_t size,
size_t i, int(*cmp)(const void *, const void *))
{
size_t l = LEFT(i), r = RIGHT(i), m = i;
if (l < n && cmp(((char *) key) + heap[l]*size,
((char *) key) + heap[m]*size) < 0)
m = l;
if (r < n && cmp(((char *) key) + heap[r]*size,
((char *) key) + heap[m]*size) < 0)
m = r;
if (m == i) return;
binheap_exchange(heap, map, i, m);
binheap_siftdown(key, heap, map, n, size, m, cmp);
}
void
binheap_siftup(void *key, size_t *heap, size_t *map, size_t n, size_t size,
size_t i, int(*cmp)(const void *, const void *))
{
size_t p = PARENT(i);
if (p >= ULONG_MAX || cmp(((char *) key) + heap[p]*size,
((char *) key) + heap[i]*size) <= 0) {
return;
}
binheap_exchange(heap, map, i, p);
binheap_siftup(key, heap, map, n, size, p, cmp);
}
void
binheap_make(void *key, size_t *heap, size_t *map, size_t n,
size_t size, int(*cmp)(const void *, const void *))
{
int i;
for (i = 0; i < n; i++)
heap[i] = map[i] = i;
for (i = PARENT(n - 1); i >= 0; i--)
binheap_siftdown(key, heap, map, n, size, i, cmp);
}Exemplo de utilização (ficheiro binheap_test.c:
#include <stdio.h>
#include <stdlib.h>
#include "binheap.h"
int
doublecmp(const void *ap, const void *bp)
{
double a = * (double *) ap;
double b = * (double *) bp;
if (a < b)
return -1;
if (a > b)
return 1;
return 0;
}
int
main(int argc, char *argv[])
{
struct binheap *q;
double a[7] = {2,1,3,4,6,5,7};
BINHEAP_INIT(q, double, a, 7, doublecmp);
BINHEAP_MAKE(q, 7);
if (BINHEAP_EMPTY(q))
printf("Empty!\n");
a[4] = -0.5;
BINHEAP_UPDATE(q, 4);
a[1] = 100;
BINHEAP_UPDATE(q, 1);
printf("%lu %f\n", BINHEAP_TOP(q), a[BINHEAP_TOP(q)]);
BINHEAP_POP(q);
printf("%lu %f\n", BINHEAP_TOP(q), a[BINHEAP_TOP(q)]);
BINHEAP_POP(q);
a[4] = 10;
BINHEAP_PUSH(q, 4);
printf("--\n");
while (! BINHEAP_EMPTY(q)) {
printf("%lu %f\n", BINHEAP_TOP(q), a[BINHEAP_TOP(q)]);
BINHEAP_POP(q);
}
BINHEAP_FREE(q);
return EXIT_SUCCESS;
}Compilar e executar:
[aplf@darkstar ~]$ gcc -Wall -ansi -pedantic -o binheap_test binheap_test.c binheap.c [aplf@darkstar ~]$ ./binheap_test 4 -0.500000 0 2.000000 -- 2 3.000000 3 4.000000 5 5.000000 6 7.000000 4 10.000000 1 100.000000 [aplf@darkstar ~]$