Heap Aleatório

Um heap aleatório é um heap no qual, através do uso da randomização, permite executar todas as operações em tempo logarítmico.

Um heap mínimo é uma árvore binária na qual o valor de cada vértice é menor ou igual aos valores de seus filhos. Assim, o mínimo da árvore está sempre no vértice raiz.

Um heap máximo pode ser definido de maneira semelhante: substituindo mínimo por máximo.

As operações padrão de um heap são:

Um heap aleatório pode executar todas essas operações no tempo esperado de $O(\log n)$ com uma implementação muito simples.

Estrutura de dados

Podemos descrever imediatamente a estrutura do heap binário:

struct Tree {
    int value;
    Tree * l = nullptr;
    Tree * r = nullptr;
};

No vértice, armazenamos um valor value. Além disso, temos ponteiros para os filhos esquerdo e direito, que são nullptr se o filho correspondente não existir.

Operações

Não é difícil perceber que todas as operações podem ser reduzidas a uma única: mesclar dois heaps em um. De fato, adicionar um novo valor ao heap é equivalente a mesclar o heap com um heap que consiste em um único vértice com esse valor. Encontrar um mínimo não requer nenhuma operação - o mínimo é simplesmente o valor na raiz. Remover o mínimo é equivalente ao resultado da mesclagem dos filhos esquerdo e direito do vértice raiz. E remover um elemento arbitrário é semelhante. Mesclamos os filhos do vértice e substituímos o vértice pelo resultado da mesclagem.

Então, na verdade, precisamos apenas implementar a operação de mesclar dois heaps. Todas as outras operações são reduzidas a esta operação.

Sejam dois heaps $T_1$ e $T_2$. É claro que a raiz de cada um desses heaps contém o mínimo. Portanto, a raiz do heap resultante será o mínimo desses dois valores. Então, comparamos os dois valores e usamos o menor como a nova raiz. Agora temos que combinar os filhos do vértice selecionado com o heap que sobrou. Para isso, selecionamos um dos filhos e o mesclamos com o heap. Assim, temos novamente a operação de mesclar dois heaps. Mais cedo ou mais tarde, esse processo terminará (o número de etapas desse processo é limitado pela soma das alturas dos dois heaps).

Para alcançar a complexidade logarítmica, em média, precisamos especificar um método para escolher um dos dois filhos, para que o comprimento médio do caminho seja logarítmico. Tomaremos essa decisão aleatoriamente :). Portanto, a implementação da operação de mesclagem é a seguinte:

Tree* merge(Tree* t1, Tree* t2) {
    if (!t1 || !t2)
        return t1 ? t1 : t2;
    if (t2->value < t1->value)
        swap(t1, t2);
    if (rand() & 1)
        swap(t1->l, t1->r);
    t1->l = merge(t1->l, t2);
    return t1;
}

Aqui, primeiro verificamos se um dos heaps está vazio e não precisamos executar nenhuma ação de mesclagem. Caso contrário, criamos o heap t1 o que tem o menor valor (trocando t1 e t2 se necessário). Queremos mesclar o filho esquerdo de t1 com t2, portanto, trocamos aleatoriamente os filhos de t1, e executamos a mesclagem.

Complexidade

Introduzimos a variável aleatória $h(T)$ que indicará o comprimento do caminho aleatório da raiz até a folha (o comprimento no número de arestas). O algoritmo merge performa $O(h(T_1) + h(T_2))$ etapas. Portanto, para entender a complexidade das operações, devemos olhar para a variável aleatória $h(T)$.

Valor esperado

Assumimos que a 'expectativa' $h(T)$ possa ser estimada acima pelo logaritmo do número de vértices no heap: $$\mathbf{E} h(T) \le \log(n+1)$$

Isso pode ser comprovado por indução. Seja $L$ e $R$ as subárvores esquerda e direita da raiz $T$, e $n_L$ e $n_R$ o número de vértices nelas ($n = n_L + n_R + 1$).

A seguir, é mostrada a indução:

$$\begin{align} \mathbf{E} h(T) &= 1 + \frac{\mathbf{E} h(L) + \mathbf{E} h(R)}{2} \le 1 + \frac{\log(n_L + 1) \log(n_R + 1)}{2} \\ &= 1 + \log\sqrt{(n_L + 1)(n_R + 1)} = \log 2\sqrt{(n_L + 1)(n_R + 1)} \\ &\le \log \frac{2\left((n_L + 1) + (n_R + 1)\right)}{2} = \log(n_L + n_R + 2) = \log(n+1) \end{align}$$

Excedendo o valor esperado

O valor esperado de $h(T)$ não diz nada sobre o pior caso. Ainda é possível que os caminhos da raiz aos vértices sejam, em média, muito maiores que $\log(n + 1)$ para uma árvore específica.

Vamos provar que o valor excedido é realmente muito pequeno: $$P\{h(T > (c+1) \log n\} < \frac{1}{n^c}$$ para qualquer constante positiva $c$.

Aqui, denotamos por $P$ o conjunto de caminhos da raiz do heap até as folhas em que o comprimento excede $(c+1) \log n$. Observe que, para qualquer caminho $p$ de comprimento $|p|$ a probabilidade de ser escolhido como caminho aleatório é $2^{-|p|}$. Portanto, obtemos: $$P\{h(T > (c+1) \log n\} = \sum_{p \in P} 2^{-|p|} < \sum_{p \in P} 2^{-(c+1) \log n} = |P| n^{-(c+1)} \le n^{-c}$$

Complexidade do algoritmo

Assim, o algoritmo merge, e, portanto, todas as outras operações expressas com ele, podem ser executadas em $O(\log n)$ em média.

Além disso, para qualquer constante positiva $\epsilon$ existe uma constante positiva $c$, de tal forma que a probabilidade de a operação exigir mais que $c \log n$ etapas é menor que $n^{-\epsilon}$ (em certo sentido, isso descreve o comportamento do algoritmo no pior caso).