Playlists
Heaps são utilizados, por exemplo, para:
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 vazioinsert x h
- Insere um elemento no heap e devolve o novo heaphead h
- Devolve o elemento mínimo do heaptail h
- Remove o elemento máximo do heap e devolve o novo heapEstamos 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 h2class (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)
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 .
Árvores esquerdistas foram criadas por Clark Allen Crane na década de 70:
Antes de definirmos o que são árvores esquerdistas, vamos definir:
Á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\).
Os valores indicam o suposto rank dos nós.
É esquerdista?
Não!
É esquerdista?
Sim!
É esquerdista?
Não!
É 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.
Por que árvores esquerdistas nos interessam?
Heaps esquerdistas são árvores esquerdistas com a propriedade de heap.
Tudo gira em torno da operação merge
.
Exemplo com a sequência: \(0, 28, 1, 8, 10, 4, 2, 12\)
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
Experimente o código dessa seção no Repl.it abaixo:
Heaps binomiais :
Árvores binomiais são definidas como:
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:
newtype BinomialHeap a = BinomialHeap [BinomialTree a]
O pulo do gato!
newtype BinomialHeap a = BinomialHeap [BinomialTree a]
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.
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)\)
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')
head
e tail
head
quanto tail
se utilizam de uma função auxiliar
(removeMinTree
) que encontra a árvore com a raiz mínima e a
retira da listaremoveMinTree :: 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
Experimente o código dessa seção no Repl.it abaixo:
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.