Uma fila de prioridade é um tipo abstrato de dado (ADT) que funciona de maneira semelhante a uma fila ou pilha, mas com uma diferença fundamental. Como você já deve saber, filas padrão seguem uma abordagem FIFO (First-in, First-out), onde o primeiro elemento adicionado à fila é o primeiro a ser removido da fila. Pilhas seguem uma abordagem LIFO (Last-in, First-out), onde o último elemento adicionado à pilha é o primeiro a ser removido da pilha. Filas e pilhas consideram apenas a ordem de inserção dos elementos. No entanto, filas de prioridade levam em conta a "prioridade" dos elementos. A prioridade é usada para determinar qual elemento deve ser removido em seguida. Normalmente, o elemento com a maior prioridade é removido primeiro, mas algumas implementações também podem escolher remover o elemento com a menor prioridade primeiro. Isso dependerá dos requisitos do seu programa. Filas de prioridade são muito úteis para aplicações práticas como encontrar o caminho mais curto entre dois locais, agendar tarefas em sistemas operacionais, simular tráfego, comprimir dados e gerenciar redes. Na prática, filas de prioridade são comumente implementadas usando uma estrutura de dados heap. Uma heap é uma estrutura de dados em árvore com uma propriedade muito específica chamada heap property. Essa propriedade determina a relação entre cada nó e seus filhos, com base no tipo de heap. Existem dois tipos principais de heaps: * Heap máximo * Min-heap Em uma max-heap, o valor de cada nó é maior ou igual ao valor de seus filhos. Neste exemplo, você pode ver uma estrutura de árvore com os nós 8, 7, 5, 2 e 1. Note que o nó 7 é maior que o nó 2 e o nó 1, seguindo a propriedade heap. Isso é verdade para todos os outros nós também. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-priority-queues-and-heaps-work-1.png" alt="A max-heap tree structure showing nodes with values 8 at the root, 7 and 5 as children of 8, and 2 and 1 as children of 7, demonstrating that each parent node is greater than its children."> Em contraste, em uma min-heap, o valor de cada nó é menor ou igual ao valor de seus filhos. Neste exemplo, temos nós com valores 4, 7, 9, 12 e 15. Por exemplo, o nó 7 é menor que o nó 12 e o nó 15, seguindo a propriedade do heap. Isso também é verdade para todos os outros nós. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-priority-queues-and-heaps-work-2.png" alt="A min-heap tree structure showing nodes with values 4 at the root, 7 and 9 as children of 4, and 12 and 15 as children of 7, demonstrating that each parent node is less than its children."> A propriedade heap é fundamental porque garante que o elemento máximo (ou mínimo) (dependendo do tipo de heap) esteja sempre no topo, o que facilita muito a remoção. Na prática, heaps são tipicamente implementados como arrays para acessar nós pai e filhos de forma eficiente. Usar arrays simplifica a lógica para acessar esses valores ou "nós" porque nos bastidores, se o heap mantém a estrutura de uma árvore binária completa, a implementação em array requer apenas operações matemáticas simples baseadas em seus índices para encontrar onde os elementos estão localizados na memória. JavaScript não possui um módulo de heap embutido, mas você pode implementar um min-heap usando um array. Aqui está uma implementação básica de min-heap em JavaScript:

class MinHeap {
  constructor(compare = (a, b) => a - b) {
    this.data = [];
    this.compare = compare;
  }

  peek() {
    return this.data[0];
  }

  push(value) {
    this.data.push(value);
    this.#bubbleUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) return undefined;

    const top = this.data[0];
    const last = this.data.pop();

    if (this.data.length > 0) {
      this.data[0] = last;
      this.#bubbleDown(0);
    }

    return top;
  }

  pushPop(value) {
    if (this.data.length === 0) return value;

    if (this.compare(this.data[0], value) < 0) {
      const top = this.data[0];
      this.data[0] = value;
      this.#bubbleDown(0);
      return top;
    }

    return value;
  }

  heapify(arr) {
    this.data = arr.slice();
    for (let i = Math.floor(this.data.length / 2) - 1; i >= 0; i--) {
      this.#bubbleDown(i);
    }
  }

  #bubbleUp(i) {
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.compare(this.data[i], this.data[p]) >= 0) break;
      [this.data[i], this.data[p]] = [this.data[p], this.data[i]];
      i = p;
    }
  }

  #bubbleDown(i) {
    const n = this.data.length;

    while (true) {
      let smallest = i;
      const l = 2 * i + 1;
      const r = 2 * i + 2;

      if (l < n && this.compare(this.data[l], this.data[smallest]) < 0) smallest = l;
      if (r < n && this.compare(this.data[r], this.data[smallest]) < 0) smallest = r;

      if (smallest === i) break;

      [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
      i = smallest;
    }
  }
}

` Para usar este heap, você pode criar um heap vazio. Esta será a estrutura de dados subjacente para o heap:

const myHeap = new MinHeap();

Para adicionar elementos ao heap, você deve chamar push(). Isso adicionará automaticamente o elemento onde ele deve estar, para preservar a propriedade do heap:

myHeap.push(9);

Para obter o elemento com a maior prioridade (neste caso, o menor valor), você faria uma chamada pop():

myHeap.pop();

pushPop() combina ambas as operações em uma única chamada. Isto é mais eficiente do que chamá-los em sequência separadamente, especialmente quando o heap é grande, pois realiza apenas uma operação de reordenação:

myHeap.pushPop(15);

Se você já tem um array e quer transformá-lo em uma heap, você pode chamar heapify():

myHeap.heapify([9, 2, 7, 1]);

Mas atualmente, estamos ordenando os elementos pelos seus valores, certo? E se quisermos ordená-los pela sua "prioridade" em vez disso? Você pode fazer isso armazenando arrays com esta estrutura: [priority, element]. Em JavaScript, arrays não são automaticamente comparados elemento por elemento para ordenação, então você passa uma função de comparação para o heap que compara prioridades primeiro. Observe que, neste caso, valores menores representarão prioridades maiores. Isso significa que um item com prioridade 1 terá uma prioridade maior do que um item com prioridade 3:

const myHeap = new MinHeap((a, b) => a[0] - b[0]);

myHeap.push([3, "A"]);
myHeap.push([2, "B"]);
myHeap.push([1, "C"]);

Se você precisar que elementos com a mesma prioridade sejam removidos na ordem em que foram inseridos, você pode considerar incluir um contador único como o segundo elemento do seu item para desempatar, assim: [priority, counter, element]. Por exemplo, você pode comparar pela prioridade primeiro e depois pelo contador:

let counter = 0;
const myHeap = new MinHeap((a, b) => (a[0] - b[0]) || (a[1] - b[1]));

myHeap.push([3, counter++, "A"]);
myHeap.push([2, counter++, "B"]);
myHeap.push([2, counter++, "C"]);

Agora vamos falar sobre a eficiência dos heaps. As complexidades de tempo média e no pior caso para inserir e extrair o valor mínimo ou máximo de uma heap (dependendo do tipo de heap) são logarítmicas, O(log n), porque o número de trocas necessárias geralmente é proporcional à altura da heap, que é log(n). A complexidade de tempo média e no pior caso para a operação "peek" é tempo constante, O(1). O peek envolve obter o valor mínimo ou máximo (dependendo do tipo de heap) sem removê-lo. A operação "heapify", onde o heap é construído a partir de uma lista não ordenada, tem complexidade de tempo linear, O(n), nos casos médio e pior. De forma semelhante, tanto a busca quanto a exclusão de um elemento arbitrário têm complexidades médias e piores casos lineares de tempo O(n), pois potencialmente exigem percorrer todo o heap. E quanto espaço eles requerem? A complexidade de espaço do heap é linear, O(n), onde n é o número de elementos que ele contém. Ele só precisa armazenar os elementos e uma pequena sobrecarga adicional para o próprio objeto array. Filas de prioridade e heaps são muito importantes em ciência da computação. Eles permitem que você encontre e use rapidamente os elementos mais importantes de uma lista. Essa eficiência é crucial para muitos programas de computador que executam tarefas críticas do mundo real, como encontrar a rota mais rápida em um mapa.