[GUIDE] Heap (priority queue)

Precisaremos de uma priority queue para ordenar os coders esperando para usar um dongle ocupado. Em python isso é bastante fácil, temos bibliotecas como heapq que trazem implementações prontas de priority queue feitas com binary min-heap Mas, aqui, não podemos usar nada disso. Precisamos implementar a priority queue por conta pŕopria.

Heap

Binary heap é a estrutura de dados que usaremos para armazenar a fila num array de forma que inserir e retirar itens seja rápido. A regra das priority queues é que sempre que um nó é retirado ele deve ser o nó de maior prioridade da fila.
Para forçar essa regra, usaremos binary min-heap. Min-heap significa que o menor nó sempre estará no index [0] do array. A invariante desse sistema é todo nó deve ser melhor que suas crianças, ou, nesse caso, menor.

Não iremos armazenar ponteiros para as crianças, mas sim usar aritmética dos indexes, isso é um array afinal de contas. \

O array de exemplo:
index:  0     1     2     3     4     5 
valor:  10    20    30    25    40    35 

Representa esta árvore:
         10          <- root = melhor
       /    \
     20      30      <- crianças de 0
    /  \    /
   25  40  35         <- crianças de 1 e 2.

A árvore existe dentro dos índices do array.

A regra é: criança a esquerda do índice i = 2i + 1 criança a direita do índice i = 2i + 2 pai do índice i = (i-1) / 2

Parece complicado a princípio, mas depois de bater cabeça um pouco faz sentido e fica fácil.

Como são feitas as operações

Após qualquer operação a invariante será quebrada e deverá ser restaurada. Isso significa que em caso de push, iremos inserir o novo nó canto inferior esquerdo, ou seja, no último index. Provavelmente esse nó estará no lugar errado, por isso disse que a invariante foi quebrada.
Para resolver comparamos o novo nó com seu nó pai (que estará em (i-1) / 2) e se a criança, o novo nó, for melhor que seu nó pai, iremos troca-los de lugar.
Nesse ponto é só questão de continuar repetindo esse processo até que novo nó seja pior que seu nó pai. Isso fará com que ele vá subindo a árvore até se encaixar onde deveria estar. Assim, restaurando a invariante da min-heap (todo nó deve ser melhor que suas crianças).

O mesmo acontece em caso de pop, mas nesse caso o nó root, index 0, é retirado e o último nó é colocado no lugar, quebrando a invariante. Daqui em diante é parecido com o push, mas nesse caso o novo root é que irá descer. Iremos comparar as crianças para achar a melhor e então comparar com o root. Se a melhor criança for melhor do que o root, trocam de lugar. E o processo de repete até que o nó seja encaixado no lugar correto, nesse caso quando todas crianças forem piores do que ele.

Ok, mas como comparar os nós?

A heap não decide sozinha qual nó é melhor ou pior, ela delega essa comparação a uma função, que será o comparador.
A função fará o seguinte:

1. Se a->priority < b->priority, então a é melhor (min-heap, menor = melhor)
2. Se a->priority > b->priority, então b é melhor (min-heap, menor = melhor)
3. Se a->priority == b->priority, então teremos que decidir por sequência, é melhor o nó que entrou primeiro na fila.
4. Se a->priority == b->priority e os dois entraram ao mesmo tempo na fila, os nós são equivalentes.