Implementando Fila de Prioridade (Priority Queue) com NodeJS e Javascript

Fila comum é FIFO. Fila de prioridade atende quem tem score maior (ou menor) primeiro — fila de hospital, tarefas críticas, agendador. Aqui montamos em cima do min-heap do ep. 9.

O que você vai aprender:

• enqueue / dequeue por prioridade, não por ordem de chegada
• Reaproveitar heap em array
• Min-heap vs max-heap na regra de negócio
• Onde isso aparece fora de SO

Pré-requisitos: heaps (ep. 9). Se pulou árvores, revise árvores (ep. 6).

Priority queue: heap com prioridade explícita

No post anterior falamos sobre Heaps, e agora vamos falar sobre Filas de Prioridade, que são uma estrutura de dados que se baseia em Heaps, então se você não viu o post sobre Heaps, recomendo dar uma olhada antes de continuar por aqui, vamos usar muito do que vimos em Heaps aqui.

Se Filas de Prioridade são baseadas nos Heaps, então imagino que você já sacou, que as Filas de Prioridade usam uma estrutura de árvores (Trees), no caso árvores binárias, lembra? Se não lembra, dá uma olhada no post sobre Árvores, que vai te ajudar a entender melhor o que é uma árvore binária. Mas em resumo as árvores binárias são aquelas que todos os elementos menores que o primeiro nó da árvore (root) vão pra um lado, e todos os maiores vão para outro lado, e aqui no caso das Filas de Prioridade isso vai seguir da mesma forma, mas não pelo valor do elemento em si, e sim pelo valor da prioridade desse elemento.

Aqui nas Filas de Prioridade vamos seguir a mesma linha, onde o nó principal, ou a raiz, é o elemento de maior ou o menor prioridade com base na prioridade dos outros elementos, da mesma forma que os Heaps aqui a gente pode escolher ter o elemento de maior prioridade no topo (root), ou de menor prioridade, basta mudarmos a implementação seguindo uma estrutura de max heap ou min heap.

Mão na Massa

Bora fazer uma estrutura inicial de Fila de Prioridade, vamos usar muito do que vimos no post anterior sobre Heaps, então se você leu, vai lembrar de muita coisa, e se não leu, recomendo dar uma olhada antes de continuar por aqui.

Agora a Prática

Agora abre aí o seu VSCode ou sua IDE favorita e vamos lá, crie um arquivo chamado priority-queue.js e cola o código abaixo:

class PriorityQueue {
  constructor() {
    this.heap = []
  }
 
  getParentIndex(i) {
    return Math.floor((i - 1) / 2)
  }
  getLeftChildIndex(i) {
    return 2 * i + 1
  }
  getRightChildIndex(i) {
    return 2 * i + 2
  }
 
  enqueue(element, priority) {
    this.heap.push({ element, priority })
    this.heapifyUp() //vamos adicionar essa função em breve
  }
 
  dequeue() {
    const min = this.heap[0]
    this.heap[0] = this.heap.pop()
    this.heapifyDown() //vamos adicionar essa função em breve
    return min.element
  }
 
  isEmpty() {
    return this.heap.length === 0
  }
}

Explicando o que temos até agora:

• Temos a classe PriorityQueue e a gente inicia o nosso heap como um array vazio (lembra é uma Fila de Prioridade, mas a estrutura é de Heap).
• Temos os métodos getParentIndex, getLeftChildIndex e getRightChildIndex que são os mesmos métodos que usamos no post sobre Heaps, então se você leu, vai lembrar deles.
• Temos o método enqueue em vez do insert que é o método que vai adicionar um elemento na nossa Fila de Prioridade, e ele recebe o element que é o elemento que queremos adicionar e a priority que é a prioridade desse elemento.
• Temos o método dequeue que é o método que vai remover o elemento (seria processar no caso, mas aqui vamos só remover) de maior prioridade da nossa Fila de Prioridade, e ele retorna o elemento pra nós.
• Temos o método isEmpty que é o método que vai verificar se a nossa Fila de Prioridade está vazia ou não.

Só com isso ainda não conseguimos ver toda a mágica da coisa, então a gente precisa colocar mais algumas funções pra fazer a mágica acontecer, bora lá.

O heapifyUp é a função que vai ajustar a fila de Prioridade pra cima, ou seja, quando a gente inserir algum valor, ele vai subir na árvore de acordo com a prioridade até achar o lugar certo dele, então coloca esse código depois do isEmpty:

  heapifyUp() {
    let index = this.heap.length - 1
    while (
      index !== 0 &&
      this.heap[this.getParentIndex(index)].priority > this.heap[index].priority
    ) {
      ;[this.heap[this.getParentIndex(index)], this.heap[index]] = [
        this.heap[index],
        this.heap[this.getParentIndex(index)],
      ]
      index = this.getParentIndex(index)
    }
  }

O heapifyDown é a função que vai ajustar o Heap pra baixo, ou seja, quando a gente remover algum valor, todos os outros elementos vão "andar uma casa" ou seja, descer na árvore até achar o lugar certo, então coloca esse código depois do heapifyUp:

  heapifyDown() {
    let index = 0
    while (this.getLeftChildIndex(index) < this.heap.length) {
      let smallerChildIndex = this.getLeftChildIndex(index)
      if (
        this.getRightChildIndex(index) < this.heap.length &&
        this.heap[this.getRightChildIndex(index)].priority < this.heap[smallerChildIndex].priority
      ) {
        smallerChildIndex = this.getRightChildIndex(index)
      }
      if (this.heap[index].priority < this.heap[smallerChildIndex].priority) break
      ;[this.heap[index], this.heap[smallerChildIndex]] = [
        this.heap[smallerChildIndex],
        this.heap[index],
      ]
      index = smallerChildIndex
    }
  }

TA QUASE ACABANDO, PROMETO!

Com tudo isso feito, vamos botar uns console.log bem raiz e criar uns itens na Fila pra ver se tá tudo funcionando como a gente espera, bora! Depois da classe PriorityQueue coloca o código abaixo (ou em outro arquivo se você preferir):

const priorityQueue = new PriorityQueue()
 
priorityQueue.enqueue(15, 1)
console.log(`Priority queue (enqueue 15):`, { queue: priorityQueue.heap })
 
priorityQueue.enqueue(10, 2)
console.log(`Priority queue (enqueue 10):`, { queue: priorityQueue.heap })
 
priorityQueue.enqueue(5, 3)
console.log(`Priority queue (enqueue 5):`, { queue: priorityQueue.heap })
 
priorityQueue.enqueue(20, 4)
console.log(`Priority queue (enqueue 20):`, { queue: priorityQueue.heap })
 
priorityQueue.enqueue(7, 5)
console.log(`Priority queue (enqueue 7):`, { queue: priorityQueue.heap })
 
priorityQueue.enqueue(25, 6)
console.log(`Priority queue (enqueue 25):`, { queue: priorityQueue.heap })
 
priorityQueue.enqueue(1, 7)
console.log(`Priority queue (enqueue 1):`, { queue: priorityQueue.heap })

Explicando:

• A gente cria uma nova instância da nossa PriorityQueue.
• A gente adiciona alguns elementos na nossa Fila de Prioridade com a função enqueue, lembrando que aqui, não colocamos só um valor, temos que colocar a prioridade desse valor também, senão a gente não consegue fazer a mágica acontecer.
• A gente dá um console.log pra ver como tá a nossa Fila de Prioridade depois de cada elemento que a gente adiciona.

Agora a última parte pra gente ver se ta tudo certinho, vamos adicionar isso aqui:

console.log(`dequeue 1/3:`, {
  rootValue: priorityQueue.dequeue(),
  heap: priorityQueue.heap,
})
 
console.log(`dequeue 2/3:`, {
  rootValue: priorityQueue.dequeue(),
  heap: priorityQueue.heap,
})
 
console.log(`dequeue 3/3:`, {
  rootValue: priorityQueue.dequeue(),
  heap: priorityQueue.heap,
})

Explicando:

• A gente vai remover ou "processar" os elementos da nossa Fila de Prioridade com a função dequeue.
• A função dequeue vai remover o elemento de maior prioridade da nossa Fila e vai retornar esse elemento pra gente.
• A gente dá um console.log pra ver como tá a nossa Fila de Prioridade depois de cada elemento que a gente remove.
• Fazemos 3 remoções e esperamos que os elementos sejam removidos na ordem de prioridade deles.

Se tudo deu certo, você deve ver algo parecido com isso no seu terminal quando você executar o código:

dequeue 1/3: {
  rootValue: 10,
  heap: [
    { element: 20, priority: 2 },
    { element: 5, priority: 4 },
    { element: 30, priority: 3 },
    { element: 1, priority: 7 },
    { element: 15, priority: 5 },
    { element: 25, priority: 6 }
  ]
}
dequeue 2/3: {
  rootValue: 20,
  heap: [
    { element: 30, priority: 3 },
    { element: 5, priority: 4 },
    { element: 25, priority: 6 },
    { element: 1, priority: 7 },
    { element: 15, priority: 5 }
  ]
}
dequeue 3/3: {
  rootValue: 30,
  heap: [
    { element: 5, priority: 4 },
    { element: 15, priority: 5 },
    { element: 25, priority: 6 },
    { element: 1, priority: 7 }
  ]
}

Eu não coloquei ali em cima o console.log de cada enqueue porque ia ficar muito grande o post aqui, mas se os logs do dequeue estão certos, você deve ter os mesmos valores que eu aqui certinho.

Nessa Fila de Prioridade, a implementação que seguimos foi de Min-Heap, então a menor prioridade ("1" no caso) será o elemento root, imaginamos nesse caso que o 1 seria o primeiro a ser processado/executado, e depois o 2, e assim por diante. Se você quiser trabalhar com Max-Heap, basta inverter as comparações de prioridade nos métodos heapifyUp e heapifyDown, ai os elementos de maior prioridade vão ser os primeiros a serem processados/executados.

Vou parar o código por aqui e deixar pra você testar, e se você reparou, usamos um Array pra facilitar a estrutura do Heap, o que acha de tentar usar a estrutura de árvore que fizemos uns posts atrás pra montar essa Fila? Será que dá pra fazer? Se fizer, me avisa, quero ver!

Aonde Você Pode Usar/Ver

Gerenciamento de Recursos

Filas de prioridade são perfeitas para gerenciar recursos em sistemas computacionais onde diferentes processos têm diferentes prioridades de acesso a recursos, como CPU e memória, mas aqui estamos falando de casos complexos e voltados para o sistema operacional, então não é algo que você vai usar no seu dia a dia (eu acho).

Simulações e Agendamentos

Falando em casos mais voltados pra apps, sites, etc, podemos usar as Filas de Prioridade em simulações, execução e agendamento de eventos, por exemplo um sistema de Fila online para um restaurante onde idosos/gestantes vão ter uma prioridade na fila, ou também em jogos, onde ações de personagens podem ter prioridades diferentes, ou até mesmo em sistemas de busca, onde a busca de um usuário pode ter prioridade sobre a busca de outro, enfim, são muitas possibilidades.

Edge cases: prioridade dinâmica e empate

Mudar a prioridade de um item no meio da fila exige reordenar o heap (ou remover e reinserir). Não existe “só atualizar um número” sem heapify.

Empate de prioridade: defina desempate (FIFO por timestamp) na comparação — senão a ordem fica imprevisível.

TL;DR — Fila de prioridade

Próximos passos

• BST (ep. 12): coleção ordenada — Árvore de busca binária
• Maps (ep. 11): outro jeito de indexar por chave — Maps e Sets

Antes de fechar

Já priorizou job, alerta ou fila de usuário? Se implementou com árvore em vez de array, quero ver nos comentários.