En este tutorial, aprenderá qué es la cola de prioridad. Además, aprenderá sobre sus implementaciones en Python, Java, C y C ++.
Una cola de prioridad es un tipo especial de cola en la que cada elemento está asociado con una prioridad y se sirve de acuerdo con su prioridad. Si se producen elementos con la misma prioridad, se sirven según su orden en la cola.
Generalmente, el valor del propio elemento se considera para asignar la prioridad.
Por ejemplo, el elemento con el valor más alto se considera como el elemento de mayor prioridad. Sin embargo, en otros casos, podemos asumir el elemento con el valor más bajo como el elemento de mayor prioridad. En otros casos, podemos establecer prioridades según nuestras necesidades.
Eliminación del elemento de máxima prioridad
Diferencia entre cola prioritaria y cola normal
En una cola, se implementa la regla de primero en entrar, primero en salir , mientras que, en una cola de prioridad, los valores se eliminan en función de la prioridad . El elemento con la prioridad más alta se elimina primero.
Implementación de cola de prioridad
La cola de prioridad se puede implementar utilizando una matriz, una lista vinculada, una estructura de datos de pila o un árbol de búsqueda binaria. Entre estas estructuras de datos, la estructura de datos del montón proporciona una implementación eficiente de las colas de prioridad.
Por lo tanto, usaremos la estructura de datos del montón para implementar la cola de prioridad en este tutorial. Un montón máximo se implementa en las siguientes operaciones. Si desea obtener más información al respecto, visite max-heap y mean-heap.
A continuación se ofrece un análisis comparativo de diferentes implementaciones de cola de prioridad.
| Operaciones | ojeada | insertar | Eliminar |
|---|---|---|---|
| Lista enlazada | O(1) | O(n) | O(1) |
| Montón binario | O(1) | O(log n) | O(log n) |
| Árbol de búsqueda binaria | O(1) | O(log n) | O(log n) |
Operaciones de cola prioritarias
Las operaciones básicas de una cola de prioridad son insertar, eliminar y observar elementos.
Antes de estudiar la cola de prioridad, consulte la estructura de datos del montón para comprender mejor el montón binario que se utiliza para implementar la cola de prioridad en este artículo.
1. Insertar un elemento en la cola de prioridad
La inserción de un elemento en una cola de prioridad (max-heap) se realiza mediante los siguientes pasos.
- Inserte el nuevo elemento al final del árbol.
Insertar un elemento al final de la cola - Apila el árbol.
Heapify después de la inserción
Algoritmo para la inserción de un elemento en la cola de prioridad (max-heap)
Si no hay ningún nodo, cree un newNode. else (un nodo ya está presente) inserte el newNode al final (último nodo de izquierda a derecha).
Para Min Heap, el algoritmo anterior se modifica para que parentNodesiempre sea menor que newNode.
2. Eliminar un elemento de la cola de prioridad
La eliminación de un elemento de una cola de prioridad (max-heap) se realiza de la siguiente manera:
- Seleccione el elemento a eliminar.
Seleccione el elemento a eliminar - Cámbielo por el último elemento.
Intercambiar con el último elemento del nodo hoja - Quite el último elemento.
Retire la última hoja del elemento - Apila el árbol.
Apila la cola de prioridad
Algoritmo para la eliminación de un elemento en la cola de prioridad (max-heap)
Si nodeToBeDeleted es leafNode eliminar el nodo Else swap nodeToBeDeleted con lastLeafNode eliminar noteToBeDeleted heapify la matriz
Para Min Heap, el algoritmo anterior se modifica para que ambos childNodessean más pequeños que currentNode.
3. Mirando desde la cola de prioridad (encontrar máximo / mínimo)
La operación Peek devuelve el elemento máximo de Max Heap o el elemento mínimo de Min Heap sin eliminar el nodo.
Para Max heap y Min Heap
devolver rootNode
4. Extraer-Max / Min de la cola de prioridad
Extract-Max devuelve el nodo con el valor máximo después de eliminarlo de un montón máximo, mientras que Extract-Min devuelve el nodo con el valor mínimo después de eliminarlo del montón mínimo.
Implementaciones de cola de prioridad en Python, Java, C y 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); )
Aplicaciones de cola de prioridad
Algunas de las aplicaciones de una cola prioritaria son:
- Algoritmo de Dijkstra
- para implementar la pila
- para el equilibrio de carga y el manejo de interrupciones en un sistema operativo
- para la compresión de datos en código Huffman
