[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
value: 10 20 30 25 40 35 \

Representa esta árvore:
         10          <- root = melhor
       /    \
     20      30      <- criança de 0
    /  \    /
   25  40  35         <- criança 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.