Neste tutorial, você aprenderá o que é fila prioritária. Além disso, você aprenderá sobre suas implementações em Python, Java, C e C ++.
Uma fila de prioridade é um tipo especial de fila em que cada elemento está associado a uma prioridade e é servido de acordo com sua prioridade. Se ocorrerem elementos com a mesma prioridade, eles serão atendidos de acordo com sua ordem na fila.
Geralmente, o valor do próprio elemento é considerado para atribuir a prioridade.
Por exemplo, o elemento com o valor mais alto é considerado o elemento de maior prioridade. No entanto, em outros casos, podemos assumir o elemento com o valor mais baixo como o elemento de maior prioridade. Em outros casos, podemos definir prioridades de acordo com nossas necessidades.
Removendo o elemento de maior prioridade
Diferença entre fila prioritária e fila normal
Em uma fila, a regra do primeiro a entrar, primeiro a sair é implementada, ao passo que, em uma fila de prioridade, os valores são removidos com base na prioridade . O elemento com a prioridade mais alta é removido primeiro.
Implementação de fila prioritária
A fila de prioridade pode ser implementada usando uma matriz, uma lista vinculada, uma estrutura de dados heap ou uma árvore de pesquisa binária. Entre essas estruturas de dados, a estrutura de dados heap fornece uma implementação eficiente de filas de prioridade.
Portanto, usaremos a estrutura de dados do heap para implementar a fila de prioridade neste tutorial. Um heap máximo é implementado nas seguintes operações. Se você quiser saber mais sobre isso, visite max-heap e mean-heap.
Uma análise comparativa de diferentes implementações de fila de prioridade é fornecida abaixo.
| Operações | olhadinha | inserir | excluir |
|---|---|---|---|
| Lista Ligada | O(1) | O(n) | O(1) |
| Pilha Binária | O(1) | O(log n) | O(log n) |
| Árvore de pesquisa binária | O(1) | O(log n) | O(log n) |
Operações de fila prioritárias
As operações básicas de uma fila prioritária são inserir, remover e exibir elementos.
Antes de estudar a fila de prioridade, consulte a estrutura de dados do heap para uma melhor compreensão do heap binário conforme é usado para implementar a fila de prioridade neste artigo.
1. Inserindo um elemento na fila de prioridade
A inserção de um elemento em uma fila de prioridade (heap máximo) é feita pelas etapas a seguir.
- Insira o novo elemento no final da árvore.
Insira um elemento no final da fila - Heapify a árvore.
Heapify após inserção
Algoritmo para inserção de um elemento na fila de prioridade (heap máximo)
Se não houver nenhum nó, crie um novo nó. senão (um nó já está presente) insira o novo nó no final (último nó da esquerda para a direita). heapify a matriz
Para Min Heap, o algoritmo acima é modificado para que parentNodeseja sempre menor que newNode.
2. Excluindo um elemento da fila de prioridade
A exclusão de um elemento de uma fila de prioridade (heap máximo) é feita da seguinte maneira:
- Selecione o elemento a ser excluído.
Selecione o elemento a ser excluído - Troque-o pelo último elemento.
Trocar com o último elemento de nó de folha - Remova o último elemento.
Remova a última folha do elemento - Heapify a árvore.
Heapify a fila de prioridade
Algoritmo para exclusão de um elemento na fila de prioridade (heap máximo)
Se nodeToBeDeleted for leafNode, remova o nó Else swap nodeToBeDeleted com lastLeafNode remove noteToBeDeleted heapify a matriz
Para Min Heap, o algoritmo acima é modificado para que ambos childNodessejam menores que currentNode.
3. Espreitar da fila de prioridade (Encontrar máx. / Mín.)
A operação Peek retorna o elemento máximo de Max Heap ou o elemento mínimo de Min Heap sem excluir o nó.
Para heap máximo e heap mínimo
return rootNode
4. Extrair-Max / Min da Fila de Prioridade
Extract-Max retorna o nó com valor máximo após removê-lo de um Heap Máx, enquanto Extract-Min retorna o nó com valor mínimo após removê-lo de Min Heap.
Implementações de fila prioritária em Python, Java, C e C ++
Python Java C C ++ # Priority Queue implementation in Python # Function to heapify the tree def heapify(arr, n, i): # Find the largest among root, left child and right child largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r # Swap and continue heapifying if root is not largest if largest != i: arr(i), arr(largest) = arr(largest), arr(i) heapify(arr, n, largest) # Function to insert an element into the tree def insert(array, newNum): size = len(array) if size == 0: array.append(newNum) else: array.append(newNum) for i in range((size // 2) - 1, -1, -1): heapify(array, size, i) # Function to delete an element from the tree def deleteNode(array, num): size = len(array) i = 0 for i in range(0, size): if num == array(i): break array(i), array(size - 1) = array(size - 1), array(i) array.remove(size - 1) for i in range((len(array) // 2) - 1, -1, -1): heapify(array, len(array), i) arr = () insert(arr, 3) insert(arr, 4) insert(arr, 9) insert(arr, 5) insert(arr, 2) print ("Max-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(arr))
// Priority Queue implementation in Java import java.util.ArrayList; class Heap ( // Function to heapify the tree void heapify(ArrayList hT, int i) ( int size = hT.size(); // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); ) ) // Function to insert an element into the tree void insert(ArrayList hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.add(newNum); ) else ( hT.add(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) // Function to delete an element from the tree void deleteNode(ArrayList hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; j--) ( heapify(hT, j); ) ) // Print the tree void printArray(ArrayList array, int size) ( for (Integer i : array) ( System.out.print(i + " "); ) System.out.println(); ) // Driver code public static void main(String args()) ( ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println("Max-Heap array: "); h.printArray(array, size); h.deleteNode(array, 4); System.out.println("After deleting an element: "); h.printArray(array, size); ) )
// Priority Queue implementation in C #include int size = 0; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) // Function to heapify the tree void heapify(int array(), int size, int i) ( if (size == 1) ( printf("Single element in the heap"); ) else ( // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l array(largest)) largest = l; if (r array(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&array(i), &array(largest)); heapify(array, size, largest); ) ) ) // Function to insert an element into the tree void insert(int array(), int newNum) ( if (size == 0) ( array(0) = newNum; size += 1; ) else ( array(size) = newNum; size += 1; for (int i = size / 2 - 1; i>= 0; i--) ( heapify(array, size, i); ) ) ) // Function to delete an element from the tree void deleteRoot(int array(), int num) ( int i; for (i = 0; i = 0; i--) ( heapify(array, size, i); ) ) // Print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) printf("%d ", array(i)); printf(""); ) // Driver code int main() ( int array(10); insert(array, 3); insert(array, 4); insert(array, 9); insert(array, 5); insert(array, 2); printf("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); )
// Priority Queue implementation in C++ #include #include using namespace std; // Function to swap position of two elements void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) // Function to heapify the tree void heapify(vector &hT, int i) ( int size = hT.size(); // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT(largest)) largest = l; if (r hT(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&hT(i), &hT(largest)); heapify(hT, largest); ) ) // Function to insert an element into the tree void insert(vector &hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.push_back(newNum); ) else ( hT.push_back(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) // Function to delete an element from the tree void deleteNode(vector &hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; i--) ( heapify(hT, i); ) ) // Print the tree void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) // Driver code int main() ( vector heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); )
Aplicativos de fila prioritários
Algumas das aplicações de uma fila prioritária são:
- Algoritmo de Dijkstra
- para implementar pilha
- para balanceamento de carga e tratamento de interrupção em um sistema operacional
- para compressão de dados em código Huffman
