Heaps

Playlists

1 Heaps

1.1 O que são?

  • Conjuntos ou dicionários (como o que implementamos com as árvores binárias) tipicamente permitem que tenhamos acessos a elementos arbitrários de maneira eficiente.
  • Algumas vezes, contudo, queremos ter acesso apenas ao elemento mínimo (ou máximo).
  • Heaps ou filas de prioridades são estruturas de dados especializadas neste tipo de tarefa.

1.2 Pra que servem?

Heaps são utilizados, por exemplo, para:

  • Ordenar um vetor (Heapsort);
  • Implementação de simuladores de eventos discretos (DES);
  • Cálculo de caminhos mínimos (Algoritmo de Djikstra);
  • Cálculo de árvores geradoras de custo mínimo (Algoritmos de Kruskal e Prim);
  • Compressão de arquivos (Algoritmo de Huffman por exemplo).

1.3 Como se usa?

  • Existem diversas maneiras de se implementar um heap. Em geral, um heap deve permitir as seguintes operações (se possível eficientemente):

    • empty - Cria e devolve um novo heap vazio
    • insert x h - Insere um elemento no heap e devolve o novo heap
    • head h - Devolve o elemento mínimo do heap
    • tail h - Remove o elemento máximo do heap e devolve o novo heap
  • Estamos interessados em heaps intercaláveis (_ mergeable _) que além das operações anteriores também oferecem:

    • merge h1 h2 - cria e devolve um novo heap que contém todos os elementos de h1 e h2

1.4 Uma typeclass para heaps

class (Show h, Ord a) => Heap h a where
  empty     :: h a
  null      :: h a -> Bool

  head      :: h a -> a
  tail      :: h a -> h a

  merge     :: h a -> h a -> h a

  insert    :: a -> h a -> h a
  insert a h = merge h (singleton a)

  singleton :: a -> h a
  singleton x = insert x empty

  -- Constrói um heap binário de uma lista qualquer.
  fromList  :: [a] -> h a
  fromList [] = empty
  fromList l =
    mergeList (map singleton l)
    where
      -- merge a lista até que tenha um único elemento
      mergeList [a] = a
      mergeList x = mergeList (mergePairs x)
      -- merge par a par da lista de heaps
      mergePairs (a:b:c) = merge a b : mergePairs c
      mergePairs x = x


  -- Quase um HeapSort
  toList :: h a -> [a]
  toList h
    | null h = []
    | otherwise = head h : toList (tail h)

1.5 Heaps binários

Heaps são frequentemente implementados como árvores binárias, onde o valor contido por qualquer um dos seus nós não é maior que qualquer um dos valores armazenados por seus filhos. Em linguagens imperativas eles são tipicamente implementados com vetores.

Já, num contexto funcional, não temos vetores com endereçamento em tempo constante. A nossa definição será muito parecida com a que utilizamos em árvores binárias. Utilizaremos, em nossa primeira implementação o conceito de árvores esquerdistas .

2 Árvores esquerdistas

Árvores esquerdistas foram criadas por Clark Allen Crane na década de 70:

  • São árvores binárias que obedecem a propriedade de (min) heap: um nó não é maior que qualquer um de seus filhos diretos e indiretos.
    • Não são de árvores de busca!
  • Utilizar uma árvore esquerdista garante que tenhamos bons tempos de execução (constante para o mínimo e logarítmicos para as demais operações).

Antes de definirmos o que são árvores esquerdistas, vamos definir:

  • O _ rank _ de um nó \(x\) é o comprimento do caminho de \(x\) até o nó não nulo mais à direita.
    • Consideramos que o rank de um nó nulo é \(-1\).
    • No contexto funcional fala-se em espinha direita . O termo espinha será reutilizado quando falarmos de finger trees

Árvores esquerdistas , carinhosamente chamadas de canhotinhas 😛, são árvores binárias nas quais vale a propriedade esquerdista :

  • Para todo nó \(x\) da árvore vale:

    \(\text{rank}(E(x)) >= \text{rank}(D(x))\),

    onde \(D\) e \(E\) são, respectivamente, os filhos direito e esquerdo de \(x\).

2.1 Identificando árvores esquerdistas

Os valores indicam o suposto rank dos nós.

  • Exemplo 01:

É esquerdista?

Não!

  • Exemplo 02:

É esquerdista?

Sim!

  • Exemplo 03:

É esquerdista?

Não!

  • Exemplo 04:

É esquerdista?

Sim!

Árvores esquerdistas:
\(\cdot\) Não são balanceadas.
\(\cdot\) Não são completas.
\(\cdot\) Qualquer subárvore de uma árvore esquerdista é esquerdista.
\(\cdot\) A espinha direita da árvore esquerdista é sempre o caminho mais curto até um nó vazio.
\(\cdot\) O comprimento da espinha direita é no máximo \(\lfloor\text{lg} (n + 1)\rfloor\).

Proposição: Se a espinha direita de uma árvore esquerdista com raiz em \(x\) tem \(r\) nós, então a árvore tem ao menos \(2^r - 1\) nós.

  • A prova é por indução em \(r\)
    • Caso base: \(r = 1\). A árvore tem ao menos \(2^1 - 1 = 1\) nó.
    • Passo de indução: assuma que vale para \(r - 1\), vamos provar que vale para \(r\).
      • A espinha direita da subárvore direita de \(x\), \(D(x)\) tem \(r - 1\) nós. Pela H.I. \(D(x)\) tem \(2^{r -1}-1\) nós.
      • A espinha direita da subárvore esquerda de \(x\), \(E(x)\) também tem pelo menos \(r - 1\) nós (Pq?), logo pela H.I. \(E(x)\) tem \(2^{r -1}-1\) nós.
      • Assim, \(n\) o número total de nós da árvore esquerdista com raiz em \(x\), é: \(n \ge (2^{r-1}-1) + (2^{r-1}-1) + 1 = 2^r - 1\)
  • Corolário: \(r = O(\lg n)\)

3 Heaps esquerdistas

Por que árvores esquerdistas nos interessam?

  • Temos a garantia que o número de nós na espinha direita é curta em comparação com o número de nós da árvore
  • Vamos concentrar o trabalho na espinha direita!

Heaps esquerdistas são árvores esquerdistas com a propriedade de heap.

  • Ou seja, se os filhos à esquerda (\(E(x)\)) e à direita (\(D(x)\)) do nó \(x\) existirem, então \(V(x) \le V(E(x))\) e \(V(x) \le V(D(x))\)
  • Tudo gira em torno da operação merge.

  • Exemplo com a sequência: \(0, 28, 1, 8, 10, 4, 2, 12\)

3.1 Implementando heaps esquerdistas

data LeftistHeap a where
  LLeaf :: Ord a => LeftistHeap a -- Nó nulo
  LNode :: Ord a => {
    rank   :: Int,
    key    :: a,
    _left  :: LeftistHeap a,
    _right :: LeftistHeap a
  } -> LeftistHeap a

Uma instância de Heap para LeftistHeap

instance Ord a => Heap LeftistHeap a where
  -- O(1). Devolve um heap vazio.
  empty = LLeaf

  -- O(1). Devolve um heap com um único elemento.
  singleton x = LNode 0 x LLeaf LLeaf

  -- O(1). True caso heap vazio, False cc.
  null LLeaf = True
  null _     = False

  --  O(1). Devolve o elemento mínimo no heap
  head LNode {key = v} = v
  head _ = error "LeftistHeap vazio"

  --  O(lg n). Descarta a raiz e devolve o heap resultante.
  tail (LNode _ _ h1 h2) = merge h1 h2
  tail _ = error "LeftistHeap vazio"

  -- Exercício: qual a complexidade de merge?
  merge LLeaf h = h
  merge h LLeaf = h
  merge h1@(LNode _ v1 e1 d1) h2@(LNode _ v2 e2 d2)
    | v1 <= v2  = makeNode v1 e1 (merge d1 h2)
    | otherwise = makeNode v2 e2 (merge h1 d2)
    where
      rk LLeaf = -1
      rk LNode {rank = r} = r
      makeNode x a b
	| rk a >= rk b = LNode (rk b + 1) x a b
	| otherwise    = LNode (rk a + 1) x b a

3.3 Experimente no Repl.it

Experimente o código dessa seção no Repl.it abaixo:

Código no Repl.it




4 Heaps binomiais

Heaps binomiais :

  • Criados no final da década de 70.
  • Complexidades iniciais iguais às do heap esquerdistas.
    • Código mais complexo \(\rightarrow\) mas é possível melhorar a inserção e merge para executarem em tempo amortizado \(O(1)\).
  • Assim como os heaps esquerdistas, heaps binomiais são baseados em uma estrutura mais simples chamada de árvore binomial .

4.1 Árvores binomiais

Árvores binomiais são definidas como:

  • Uma árvore binomial de rank \(0\) é um único nó.
  • Uma árvore binomial de rank \(r + 1\) é formada através da conexão de duas árvores binomiais de rank \(r\), fazendo de uma árvore a filha mais à esquerda da outra.

Uma maneira alternativa de definir as árvores binomiais é: uma árvore binomial de rank \(r\) é um nó com \(r\) filhos, \(t_1 \ldots t_r\) onde cada \(t_i\) é uma árvore binomial de rank \(r - i\).

A partir da definição é fácil ver que uma árvore binomial de rank \(r\) contém exatamente \(2^r\) nós.

Implementando uma árvore binomial

data BinomialTree a where
  BinomialTreeNode :: Ord a => {
    rnk       :: Int,
    root      :: a,
    _children :: [BinomialTree a] -- length _children == rnk
    } -> BinomialTree a

A lista com os filhos é mantida em ordem decrescente de rank e os elementos são armazenados satisfazem a propriedade de heap

Conectando (linking) duas árvores

linkTree :: BinomialTree a -> BinomialTree a -> BinomialTree a
linkTree t1@(BinomialTreeNode r1 x1 c1) t2@(BinomialTreeNode _ x2 c2)
  | x1 <= x2  = BinomialTreeNode (r1 + 1) x1 (t2 : c1)
  | otherwise = BinomialTreeNode (r1 + 1) x2 (t1 : c2)

A propriedade de heap é mantida pois sempre conectamos árvores com raízes maiores abaixo das árvores com raízes menores.

Apenas conectamos árvores com o mesmo rank.

O heap binomial nada mais é que:

  • Uma lista de árvores binomiais que obedecem a propriedade de heap.
  • A lista é mantida em ordem crescente de ranks.
  • Não há ranks repetidos.

newtype BinomialHeap a = BinomialHeap [BinomialTree a]

O pulo do gato!

newtype BinomialHeap a = BinomialHeap [BinomialTree a]
  • Como cada árvore contém \(2^r\) elementos, e nenhuma árvore tem rank repetido, os ranks das árvores de um heap de tamanho \(n\). correspondem exatamente aos bits \(1\) da representação binária de \(n\).
    • Por exemplo: heap de tamanho \(21\).
      • \(21\) em base \(2\): 10101
      • é armazenado como árvores de rank \(0\), \(2\), \(4\) (de tamanhos \(1\), \(4\) e \(16\) respectivamente).
  • Consequentemente, assim como a representação de um número \(n\) em binário usa \(\lfloor\lg (n + 1)\rfloor\) bits, um heap binomial de tamanho \(n\) usa no máximo \(\lfloor\lg (n + 1)\rfloor\) árvores.

Agora estamos prontos para definir as operações no heap. A maneira mais fácil de compreender o funcionamento das operações é imaginar que estamos fazendo operações de soma em números binários.

4.3 Inserção

  • Criamos uma árvore de rank \(0\) que contém o elemento que desejamos inserir.
  • Em seguida, varremos as árvores que já fazem parte do heap (em ordem crescente de ranks) até encontrarmos um rank vazio (um bit zero). Durante a varredura conectamos árvores de mesmo rank \(r\) para criar uma nova árvore de rank \(r+1\). O conectar de árvores é semelhante ao “vai um” (carry) de uma soma binária.
insertTree :: BinomialTree a -> [BinomialTree a] -> [BinomialTree a]
insertTree t [] = [t]
insertTree t ts@(t':ts')
  | rnk t < rnk t' = t:ts
  | otherwise      = insertTree (linkTree t t') ts'

--Inserção fica: insertTree (BinomialTreeNode 0 x []) ts

O pior caso da inserção ocorre quando o heap tem um tamanho da forma \(n = 2^k -1\) (todos os bits acesos), neste caso \(k\) chamadas de linkTree são necessárias: \(O(k) = O(\lg n)\)

  • Exemplo: 0, 28, 1, 8 , 10, 4, 2, 12

4.4 Merging

Para juntar dois heaps, varremos as duas listas de árvores em ordem crescente de rank e conectamos árvores de mesmo rank conforme avançamos.

mergeTrees :: [BinomialTree a] -> [BinomialTree a] -> [BinomialTree a]
mergeTrees ts1 [] = ts1
mergeTrees [] ts2 = ts2
mergeTrees ts1@(t1:ts1') ts2@(t2:ts2')
  | rnk t1 < rnk t2 = t1 : mergeTrees ts1' ts2
  | rnk t2 < rnk t1 = t2 : mergeTrees ts1 ts2'
  | otherwise = insertTree (linkTree t1 t2) (mergeTrees ts1' ts2')

4.5 head e tail

  • Tanto head quanto tail se utilizam de uma função auxiliar (removeMinTree) que encontra a árvore com a raiz mínima e a retira da lista
removeMinTree :: Ord a => [BinomialTree a] -> (BinomialTree a, [BinomialTree a])
removeMinTree [] = error "empty BinomialTree"
removeMinTree [t] = (t, [])
removeMinTree (t:ts)
  | root t < root t' = (t, ts)
  | otherwise        = (t', t:ts')
  where
    (t', ts') = removeMinTree ts

Agora estamos prontos para definir uma instância de Heap para BinomialHeap

Uma instância de Heap para BinomialHeap

instance Ord a => Heap BinomialHeap a where

  empty = BinomialHeap []

  singleton x = BinomialHeap [BinomialTreeNode 0 x []]

  null (BinomialHeap ts) = P.null ts

  head (BinomialHeap ts) = root . fst $ removeMinTree ts

  tail (BinomialHeap ts) =
    BinomialHeap $ mergeTrees (reverse ts1) ts2
    where
      (BinomialTreeNode _ _ ts1, ts2) = removeMinTree ts

  merge (BinomialHeap ts1) (BinomialHeap ts2) =
    BinomialHeap $ mergeTrees ts1 ts2

4.7 Experimente no Repl.it

Experimente o código dessa seção no Repl.it abaixo:

Código no Repl.it




5 Referências

  • [CO]
  • Purely Functional Data Structures
    • Por Chris Okasaki

  • [CLRS]
  • Introduction to Algorithms
    • Por Thomas H. Cormen & Charles E. Leiserson & Ronald L. Rives/t & /Clifford Stein

  • [SW]
  • Algorithms
    • Por Robert Sedgewick & Kevin Wayne

6 Disclaimer

Estes slides foram preparados para os cursos de Paradigmas de Programação e Desenvolvimento Orientado a Tipos na UFABC.

Este material pode ser usado livremente desde que sejam mantidos, além deste aviso, os créditos aos autores e instituições.