Fila de prioridade na estrutura de dados: características, tipos e implementação

Publicados: 2021-05-02

Índice

Introdução

A fila de prioridade na estrutura de dados é uma extensão da fila “normal”. É um tipo de dados abstrato que contém um grupo de itens. É como a fila “normal”, exceto que os elementos de desenfileiramento seguem uma ordem de prioridade. A ordem de prioridade desenfileira primeiro os itens que têm a prioridade mais alta. Este blog lhe dará uma compreensão mais profunda da fila de prioridade e sua implementação na linguagem de programação C.

O que é uma fila prioritária?

É um tipo de dados abstrato que fornece uma maneira de manter o conjunto de dados. A fila “normal” segue um padrão de primeiro a entrar, primeiro a sair. Ele desenfileira os elementos na mesma ordem seguida no momento da operação de inserção. No entanto, a ordem do elemento em uma fila de prioridade depende da prioridade do elemento nessa fila. A fila de prioridade move os elementos de prioridade mais alta no início da fila de prioridade e os elementos de prioridade mais baixa na parte de trás da fila de prioridade.

Ele suporta apenas os elementos que são comparáveis. Portanto, uma fila de prioridade na estrutura de dados organiza os elementos em ordem crescente ou decrescente.

Você pode pensar em uma fila prioritária como vários pacientes esperando na fila de um hospital. Aqui, a situação do paciente define a ordem de prioridade. O paciente com a lesão mais grave seria o primeiro da fila.

Quais são as características de uma fila prioritária?

Uma fila é denominada fila prioritária se tiver as seguintes características:

  • Cada item tem alguma prioridade associada a ele.
  • Um item com a prioridade mais alta é movido para a frente e excluído primeiro.
  • Se dois elementos compartilharem o mesmo valor de prioridade, a fila de prioridade seguirá o princípio do primeiro a entrar, primeiro a sair para a operação da fila.

Quais são os tipos de fila prioritária?

Uma fila de prioridade é de dois tipos:

  • Fila de Prioridade de Ordem Crescente
  • Fila de prioridade de ordem descendente

Fila de Prioridade de Ordem Crescente

Uma fila de prioridade de ordem crescente dá a prioridade mais alta ao número mais baixo nessa fila. Por exemplo, você tem seis números na fila de prioridade que são 4, 8, 12, 45, 35, 20. Primeiro, você organizará esses números em ordem crescente. A nova lista é a seguinte: 4, 8, 12, 20. 35, 45. Nesta lista, 4 é o menor número. Portanto, a fila de prioridade de ordem crescente trata o número 4 como a prioridade mais alta.

4 8 12 20 35 45

Na tabela acima, 4 tem a prioridade mais alta e 45 tem a prioridade mais baixa.

Fila de prioridade de ordem descendente

Uma fila de prioridade de ordem descendente dá a prioridade mais alta ao número mais alto nessa fila. Por exemplo, você tem seis números na fila de prioridade que são 4, 8, 12, 45, 35, 20. Primeiro, você organizará esses números em ordem crescente. A nova lista é a seguinte: 45, 35, 20, 12, 8, 4. Nesta lista, 45 é o número mais alto. Portanto, a fila de prioridade de ordem descendente trata o número 45 como a prioridade mais alta.

45 35 20 12 8 4

Na tabela acima, 4 tem a prioridade mais baixa e 45 tem a prioridade mais alta.

Implementação da Fila de Prioridade na Estrutura de Dados

Você pode implementar as filas de prioridade de uma das seguintes maneiras:

  • Lista vinculada
  • Heap binário
  • Matrizes
  • Árvore de pesquisa binária

O heap binário é o método mais eficiente para implementar a fila de prioridade na estrutura de dados .

As tabelas abaixo resumem a complexidade de diferentes operações em uma fila de prioridade.

Operação Matriz não ordenada Matriz ordenada Heap Binário Árvore de pesquisa binária
Inserir 0(1) 0(N) 0(log(N)) 0(log(N))
Olhadinha 0(N) 0(1) 0(1) 0(1)
Excluir 0(N) 0(1) 0(log(N)) 0(log(N))

Heap Binário

Uma árvore de heap binária organiza todos os nós pai e filho da árvore em uma ordem específica. Em uma árvore de heap binária, um nó pai pode ter no máximo 2 nós filhos. O valor do nó pai pode ser:

  • igual ou menor que o valor de um nó filho.
  • igual ou maior que o valor de um nó filho.

O processo acima divide o heap binário em dois tipos: heap máximo e heap mínimo.

Pilha Máxima

O heap máximo é um heap binário no qual um nó pai tem um valor igual ou maior que o valor do nó filho. O nó raiz da árvore tem o valor mais alto.

Inserindo um elemento em uma árvore binária de heap máximo

Você pode executar as etapas a seguir para inserir um elemento/número na fila de prioridade na estrutura de dados .

  1. O algoritmo varre a árvore de cima para baixo e da esquerda para a direita para encontrar um slot vazio. Em seguida, insere o elemento no último nó da árvore.
  2. Após inserir o elemento, a ordem da árvore binária é alterada. Você deve trocar os dados entre si para classificar a ordem da árvore binária de heap máximo. Você deve continuar embaralhando os dados até que a árvore satisfaça a propriedade max-heap.

Algoritmo para inserir um elemento em uma árvore binária de heap máximo

Se a árvore estiver vazia e não contiver nenhum nó,

crie um novo nó pai newElement.

else (um nó pai já está disponível)

insira o newElement no final da árvore (ou seja, último nó da árvore da esquerda para a direita).

max-heapify a árvore

Excluindo um elemento em uma árvore binária de heap máximo

  1. Você pode executar as etapas a seguir para eliminar um elemento na fila de prioridade na estrutura de dados .
  2. Escolha o elemento que você deseja excluir da árvore binária.
  3. Desloque os dados no final da árvore trocando-os com os dados do último nó.
  4. Remova o último elemento da árvore binária.
  5. Após excluir o elemento, a ordem da árvore binária é alterada. Você deve classificar a ordem para satisfazer a propriedade de heap máximo. Você deve continuar embaralhando os dados até que a árvore atenda à propriedade max-heap.

Algoritmo para excluir um elemento em uma árvore binária de heap máximo

Se o elementUpForDeletion for o lastNode,

exclua o elementoUpForDeletion

senão substitua elementUpForDeletion pelo lastNode

exclua o elementoUpForDeletion

max-heapify a árvore

Encontre o elemento máximo ou mínimo em uma árvore binária de heap máximo

Em uma árvore binária de heap máximo, a operação find retorna o nó pai (o elemento mais alto) da árvore.

Algoritmo para encontrar o máximo ou mínimo em uma árvore binária de heap máximo

retornar ParentNode

Implementação do Programa da Fila de Prioridades usando a Árvore Binária Max Heap

#include <stdio.h>

int árvore_binária = 10;

int max_heap = 0;

teste int const = 100.000;

void swap(int *x, int *y) {

int um;

a = *x;

*x= *y;

*y = a;

}

//Código para encontrar o pai na árvore de heap máximo

int findParentNode(int node[], int root) {

if ((raiz > 1) && (raiz < árvore_binária)) {

retornar raiz/2;

}

retornar -1;

}

void max_heapify(int node[], int root) {

int leftNodeRoot = findLeftChild(nó, raiz);

int rightNodeRoot = findRightChild(nó, raiz);

// encontrando o maior entre raiz, filho esquerdo e filho direito

int mais alto = raiz;

if ((leftNodeRoot <= max_heap) && (leftNodeRoot >0)) {

if (node[leftNodeRoot] > node[highest]) {

mais alto = leftNodeRoot;

}

}

if ((rightNodeRoot <= max_heap) && (rightNodeRoot >0)) {

if (node[rightNodeRoot] > node[highest]) {

mais alto = rightNodeRoot;

}

}

if (maior != raiz) {

swap(&node[root], &node[highest]);

max_heapify(nó, mais alto);

}

}

void create_max_heap(int node[]) {

int d;

for(d=max_heap/2; d>=1; d–) {

max_heapify(nó, d);

}

}

int máximo(int nó[]) {

retornar nó[1];

}

int find_max(int ​​node[]) {

int maxNode = node[1];

nó[1] = nó[max_heap];

max_heap–;

max_heapify(nó, 1);

return maxNode;

}

void descend_key(int node[], int node, int key) {

A[raiz] = chave;

max_heapify(nó, raiz);

}

void incrementa_key(int node[], int root, int key) {

nó[raiz] = chave;

while((raiz>1) && (nó[findParentNode(nó, raiz)] < nó[raiz])) {

swap(&node[root], &node[findParentNode(node, root)]);

raiz = findParentNode(nó, raiz);

}

}

void insert(int node[], int key) {

max_heap++;

node[max_heap] = -1*teste;

aumentar_key(node, max_heap, chave);

}

void display_heap(int node[]) {

int d;

for(d=1; d<=max_heap; d++) {

printf("%d\n",no[d]);

}

printf(“\n”);

}

int main(){

int nó[binary_tree];

insert(nó, 10);

insert(nó, 4);

insert(nó, 20);

insert(nó, 50);

insert(nó, 1);

insert(nó, 15);

display_heap(nó);

printf(“%d\n\n”, máximo(nó));

display_heap(nó);

printf(“%d\n”, extract_max(nó));

printf(“%d\n”, extract_max(nó));

retornar 0;

}

Pilha Mínima

O heap mínimo é um heap binário no qual um nó pai tem um valor igual ou menor que o valor do nó filho. O nó raiz da árvore tem o valor mais baixo.

Você pode implementar o heap mínimo da mesma maneira que o heap máximo, exceto pela ordem inversa.

Conclusão

Os exemplos dados no artigo são apenas para fins explicativos. Você pode modificar as declarações fornecidas acima de acordo com suas necessidades. Neste blog, aprendemos sobre o conceito de fila de prioridade na estrutura de dados . Você pode experimentar o exemplo para fortalecer seu conhecimento de estrutura de dados.

Se você está curioso para aprender sobre ciência de dados, confira o Programa PG Executivo em Ciência de Dados do IIIT-B & upGrad, que é criado para profissionais que trabalham e oferece mais de 10 estudos de caso e projetos, workshops práticos práticos, orientação com especialistas do setor, 1 -on-1 com mentores do setor, mais de 400 horas de aprendizado e assistência de trabalho com as principais empresas.

Aprenda cursos de ciência de dados online das melhores universidades do mundo. Ganhe Programas PG Executivos, Programas de Certificado Avançado ou Programas de Mestrado para acelerar sua carreira.

Quais são as aplicações de uma fila de prioridade?

A fila de prioridade é uma fila especial onde os elementos são inseridos com base em sua prioridade. Esse recurso vem a ser útil na implementação de várias outras estruturas de dados. A seguir estão algumas das aplicações mais populares da fila de prioridade:
 1. Algoritmo de caminho mais curto de Dijkstra: A fila de prioridade pode ser usada no algoritmo de caminho mais curto de Dijkstra quando o gráfico é armazenado na forma de lista de adjacências.
 2. Algoritmo de Prim: O algoritmo de Prim usa a fila de prioridade para os valores ou chaves dos nós e extrai o mínimo desses valores a cada passo.
 Compressão de dados : Os códigos Huffman usam a fila de prioridade para comprimir os dados.
 Sistemas operacionais: A fila de prioridade é muito útil para sistemas operacionais em vários processos, como balanceamento de carga e tratamento de interrupção.

Qual abordagem é usada na implementação da fila de prioridade usando array?

A abordagem utilizada na implementação da fila de prioridade usando um array é simples. Uma estrutura é criada para armazenar os valores e a prioridade do elemento e então o array dessa estrutura é criado para armazenar os elementos. As seguintes operações estão envolvidas nesta implementação:
 1. enqueue()-Esta função insere os elementos no final da fila.
 2. peek() - Esta função irá percorrer o array para retornar o elemento com a prioridade mais alta. Se encontrar dois elementos com a mesma prioridade, ele retornará o elemento de maior valor entre eles.
 3. dequeue() - Esta função irá deslocar todos os elementos, 1 posição à esquerda do elemento retornado pela função peek() e diminuir o tamanho.

Qual é a diferença entre heap máximo e heap mínimo?

O seguinte ilustra a diferença entre heap máximo e heap mínimo.
 Min Heap - Em um min-heap, a chave do nó raiz deve ser menor ou igual às chaves de seu nó filho. Ele usa prioridade crescente. O nó com a menor chave é a prioridade. O menor elemento é exibido antes de qualquer outro elemento.
 Max Heap - Em um heap máximo, a chave do nó raiz deve ser maior ou igual à chave dos nós filhos. Ele usa prioridade decrescente. O nó com a maior chave é a prioridade. O maior elemento é exibido antes de qualquer outro elemento.