Priority Queue es una extensión de la cola con las siguientes propiedades:
- Cada elemento tiene una prioridad asociada.
- Un elemento con prioridad alta se elimina de la cola antes que un elemento con prioridad baja.
- Si dos elementos tienen la misma prioridad, se sirven según su orden en la cola.
Un montón binario es un árbol binario con las siguientes propiedades:
- Es un Árbol Completo . Esta propiedad de Binary Heap los hace aptos para ser almacenados en una array .
- Un montón binario es un montón mínimo o un montón máximo .
- En un montón binario mínimo , la clave en la raíz debe ser mínima entre todas las claves presentes en el montón binario. La misma propiedad debe ser recursivamente verdadera para todos los Nodes en Binary Tree .
- De manera similar, en Max Binary Heap , la clave en la raíz debe ser máxima entre todas las claves presentes en Binary Heap. La misma propiedad debe ser recursivamente verdadera para todos los Nodes en Binary Tree.
Operación en montón binario
- insert(p): Inserta un nuevo elemento con prioridad p .
- extractMax(): Extrae un elemento con máxima prioridad.
- remove(i): Elimina un elemento apuntado por un iterador i.
- getMax(): Devuelve un elemento con máxima prioridad.
- changePriority(i, p): Cambia la prioridad de un elemento apuntado por i a p .
Ejemplo de un montón máximo binario
- Supongamos que a continuación está el Montón binario dado que sigue todas las propiedades del Montón máximo binario.
- Ahora se debe insertar un Node con valor 32 en el montón anterior: para insertar un elemento, adjunte el nuevo elemento a cualquier hoja. Por Ejemplo Se puede agregarun Node con prioridad 32 a la hoja del Node 7 . Pero esto viola la propiedad del montón. Para mantener la propiedad del montón, suba el nuevo Node 32 .
- Shift Up Operación obtener el Node con 32 en la posición correcta: Intercambie el Node colocado incorrectamente con su padre hasta que se cumpla la propiedad del montón. Por ejemplo: como el Node 7 es menor que el Node 32 , intercambie el Node 7 y el Node 32 . Luego, intercambie el Node 31 y el Node 32.
- ExtractMax: el valor máximo se almacena en la raíz del árbol. Pero la raíz del árbol no se puede quitar directamente. Primero, se reemplaza con cualquiera de las hojas y luego se retira. Por ejemplo: para eliminar el Node 45 , primero se reemplaza con el Node 7 . Pero esto viola la propiedad del montón, así que mueva el Node reemplazado hacia abajo. Para eso, use la operación de cambio hacia abajo.
- Operación ShiftDown: Intercambie el Node colocado incorrectamente con un hijo más grande hasta que se cumpla la propiedad del montón. Por ejemplo , el Node 7 se intercambia con el Node 32 y luego, por último, se intercambia con el Node 31 .
- ChangePriority: Deje que el elemento cambiado se desplace hacia arriba o hacia abajo dependiendo de si su prioridad disminuyó o aumentó. Por ejemplo: Cambie la prioridad de los Nodes 11 a 35 , debido a este cambio, el Node tiene que subir el Node para mantener la propiedad del montón.
- Eliminar: para eliminar un elemento, cambie su prioridad a un valor mayor que el máximo actual, luego muévalo hacia arriba y luego extráigalo usando extract max. Encuentre el máximo actual usando getMax.
- GetMax: el valor máximo se almacena en la raíz del árbol. Para obtener el máximo, simplemente devuelva el valor en la raíz del árbol.
Representación de array de almacenamiento dinámico binario
Dado que el montón se mantiene en forma de un árbol binario completo , debido a este hecho, el montón se puede representar en forma de array. Para mantener el árbol completo y poco profundo, al insertar un nuevo elemento, insértelo en la posición vacante más a la izquierda en el último nivel, es decir, al final de nuestra array. De manera similar, mientras extrae el máximo, reemplace la raíz con la última hoja en el último nivel, es decir, el último elemento de la array. A continuación se muestra la ilustración del mismo:
A continuación se muestra el programa para implementar Priority Queue usando Binary Heap:
C++
// C++ code to implement priority-queue
// using array implementation of
// binary heap
#include <bits/stdc++.h>
using namespace std;
int H[50];
int size = -1;
// Function to return the index of the
// parent node of a given node
int parent(int i)
{
return (i - 1) / 2;
}
// Function to return the index of the
// left child of the given node
int leftChild(int i)
{
return ((2 * i) + 1);
}
// Function to return the index of the
// right child of the given node
int rightChild(int i)
{
return ((2 * i) + 2);
}
// Function to shift up the node in order
// to maintain the heap property
void shiftUp(int i)
{
while (i > 0 && H[parent(i)] < H[i]) {
// Swap parent and current node
swap(H[parent(i)], H[i]);
// Update i to parent of i
i = parent(i);
}
}
// Function to shift down the node in
// order to maintain the heap property
void shiftDown(int i)
{
int maxIndex = i;
// Left Child
int l = leftChild(i);
if (l <= size && H[l] > H[maxIndex]) {
maxIndex = l;
}
// Right Child
int r = rightChild(i);
if (r <= size && H[r] > H[maxIndex]) {
maxIndex = r;
}
// If i not same as maxIndex
if (i != maxIndex) {
swap(H[i], H[maxIndex]);
shiftDown(maxIndex);
}
}
// Function to insert a new element
// in the Binary Heap
void insert(int p)
{
size = size + 1;
H[size] = p;
// Shift Up to maintain heap property
shiftUp(size);
}
// Function to extract the element with
// maximum priority
int extractMax()
{
int result = H[0];
// Replace the value at the root
// with the last leaf
H[0] = H[size];
size = size - 1;
// Shift down the replaced element
// to maintain the heap property
shiftDown(0);
return result;
}
// Function to change the priority
// of an element
void changePriority(int i, int p)
{
int oldp = H[i];
H[i] = p;
if (p > oldp) {
shiftUp(i);
}
else {
shiftDown(i);
}
}
// Function to get value of the current
// maximum element
int getMax()
{
return H[0];
}
// Function to remove the element
// located at given index
void remove(int i)
{
H[i] = getMax() + 1;
// Shift the node to the root
// of the heap
shiftUp(i);
// Extract the node
extractMax();
}
// Driver Code
int main()
{
/* 45
/ \
31 14
/ \ / \
13 20 7 11
/ \
12 7
Create a priority queue shown in
example in a binary max heap form.
Queue will be represented in the
form of array as:
45 31 14 13 20 7 11 12 7 */
// Insert the element to the
// priority queue
insert(45);
insert(20);
insert(14);
insert(12);
insert(31);
insert(7);
insert(11);
insert(13);
insert(7);
int i = 0;
// Priority queue before extracting max
cout << "Priority Queue : ";
while (i <= size) {
cout << H[i] << " ";
i++;
}
cout << "\n";
// Node with maximum priority
cout << "Node with maximum priority : "
<< extractMax() << "\n";
// Priority queue after extracting max
cout << "Priority queue after "
<< "extracting maximum : ";
int j = 0;
while (j <= size) {
cout << H[j] << " ";
j++;
}
cout << "\n";
// Change the priority of element
// present at index 2 to 49
changePriority(2, 49);
cout << "Priority queue after "
<< "priority change : ";
int k = 0;
while (k <= size) {
cout << H[k] << " ";
k++;
}
cout << "\n";
// Remove element at index 3
remove(3);
cout << "Priority queue after "
<< "removing the element : ";
int l = 0;
while (l <= size) {
cout << H[l] << " ";
l++;
}
return 0;
}
Java
// Java code to implement
// priority-queue using
// array implementation of
// binary heap
import java.util.*;
class GFG{
static int []H = new int[50];
static int size = -1;
// Function to return the index of the
// parent node of a given node
static int parent(int i)
{
return (i - 1) / 2;
}
// Function to return the index of the
// left child of the given node
static int leftChild(int i)
{
return ((2 * i) + 1);
}
// Function to return the index of the
// right child of the given node
static int rightChild(int i)
{
return ((2 * i) + 2);
}
// Function to shift up the
// node in order to maintain
// the heap property
static void shiftUp(int i)
{
while (i > 0 &&
H[parent(i)] < H[i])
{
// Swap parent and current node
swap(parent(i), i);
// Update i to parent of i
i = parent(i);
}
}
// Function to shift down the node in
// order to maintain the heap property
static void shiftDown(int i)
{
int maxIndex = i;
// Left Child
int l = leftChild(i);
if (l <= size &&
H[l] > H[maxIndex])
{
maxIndex = l;
}
// Right Child
int r = rightChild(i);
if (r <= size &&
H[r] > H[maxIndex])
{
maxIndex = r;
}
// If i not same as maxIndex
if (i != maxIndex)
{
swap(i, maxIndex);
shiftDown(maxIndex);
}
}
// Function to insert a
// new element in
// the Binary Heap
static void insert(int p)
{
size = size + 1;
H[size] = p;
// Shift Up to maintain
// heap property
shiftUp(size);
}
// Function to extract
// the element with
// maximum priority
static int extractMax()
{
int result = H[0];
// Replace the value
// at the root with
// the last leaf
H[0] = H[size];
size = size - 1;
// Shift down the replaced
// element to maintain the
// heap property
shiftDown(0);
return result;
}
// Function to change the priority
// of an element
static void changePriority(int i,
int p)
{
int oldp = H[i];
H[i] = p;
if (p > oldp)
{
shiftUp(i);
}
else
{
shiftDown(i);
}
}
// Function to get value of
// the current maximum element
static int getMax()
{
return H[0];
}
// Function to remove the element
// located at given index
static void remove(int i)
{
H[i] = getMax() + 1;
// Shift the node to the root
// of the heap
shiftUp(i);
// Extract the node
extractMax();
}
static void swap(int i, int j)
{
int temp= H[i];
H[i] = H[j];
H[j] = temp;
}
// Driver Code
public static void main(String[] args)
{
/* 45
/ \
31 14
/ \ / \
13 20 7 11
/ \
12 7
Create a priority queue shown in
example in a binary max heap form.
Queue will be represented in the
form of array as:
45 31 14 13 20 7 11 12 7 */
// Insert the element to the
// priority queue
insert(45);
insert(20);
insert(14);
insert(12);
insert(31);
insert(7);
insert(11);
insert(13);
insert(7);
int i = 0;
// Priority queue before extracting max
System.out.print("Priority Queue : ");
while (i <= size)
{
System.out.print(H[i] + " ");
i++;
}
System.out.print("\n");
// Node with maximum priority
System.out.print("Node with maximum priority : " +
extractMax() + "\n");
// Priority queue after extracting max
System.out.print("Priority queue after " +
"extracting maximum : ");
int j = 0;
while (j <= size)
{
System.out.print(H[j] + " ");
j++;
}
System.out.print("\n");
// Change the priority of element
// present at index 2 to 49
changePriority(2, 49);
System.out.print("Priority queue after " +
"priority change : ");
int k = 0;
while (k <= size)
{
System.out.print(H[k] + " ");
k++;
}
System.out.print("\n");
// Remove element at index 3
remove(3);
System.out.print("Priority queue after " +
"removing the element : ");
int l = 0;
while (l <= size)
{
System.out.print(H[l] + " ");
l++;
}
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 code to implement priority-queue
# using array implementation of
# binary heap
H = [0]*50
size = -1
# Function to return the index of the
# parent node of a given node
def parent(i) :
return (i - 1) // 2
# Function to return the index of the
# left child of the given node
def leftChild(i) :
return ((2 * i) + 1)
# Function to return the index of the
# right child of the given node
def rightChild(i) :
return ((2 * i) + 2)
# Function to shift up the
# node in order to maintain
# the heap property
def shiftUp(i) :
while (i > 0 and H[parent(i)] < H[i]) :
# Swap parent and current node
swap(parent(i), i)
# Update i to parent of i
i = parent(i)
# Function to shift down the node in
# order to maintain the heap property
def shiftDown(i) :
maxIndex = i
# Left Child
l = leftChild(i)
if (l <= size and H[l] > H[maxIndex]) :
maxIndex = l
# Right Child
r = rightChild(i)
if (r <= size and H[r] > H[maxIndex]) :
maxIndex = r
# If i not same as maxIndex
if (i != maxIndex) :
swap(i, maxIndex)
shiftDown(maxIndex)
# Function to insert a
# new element in
# the Binary Heap
def insert(p) :
global size
size = size + 1
H[size] = p
# Shift Up to maintain
# heap property
shiftUp(size)
# Function to extract
# the element with
# maximum priority
def extractMax() :
global size
result = H[0]
# Replace the value
# at the root with
# the last leaf
H[0] = H[size]
size = size - 1
# Shift down the replaced
# element to maintain the
# heap property
shiftDown(0)
return result
# Function to change the priority
# of an element
def changePriority(i,p) :
oldp = H[i]
H[i] = p
if (p > oldp) :
shiftUp(i)
else :
shiftDown(i)
# Function to get value of
# the current maximum element
def getMax() :
return H[0]
# Function to remove the element
# located at given index
def Remove(i) :
H[i] = getMax() + 1
# Shift the node to the root
# of the heap
shiftUp(i)
# Extract the node
extractMax()
def swap(i, j) :
temp = H[i]
H[i] = H[j]
H[j] = temp
# Insert the element to the
# priority queue
insert(45)
insert(20)
insert(14)
insert(12)
insert(31)
insert(7)
insert(11)
insert(13)
insert(7)
i = 0
# Priority queue before extracting max
print("Priority Queue : ", end = "")
while (i <= size) :
print(H[i], end = " ")
i += 1
print()
# Node with maximum priority
print("Node with maximum priority :" , extractMax())
# Priority queue after extracting max
print("Priority queue after extracting maximum : ", end = "")
j = 0
while (j <= size) :
print(H[j], end = " ")
j += 1
print()
# Change the priority of element
# present at index 2 to 49
changePriority(2, 49)
print("Priority queue after priority change : ", end = "")
k = 0
while (k <= size) :
print(H[k], end = " ")
k += 1
print()
# Remove element at index 3
Remove(3)
print("Priority queue after removing the element : ", end = "")
l = 0
while (l <= size) :
print(H[l], end = " ")
l += 1
# This code is contributed by divyeshrabadiya07.
C#
// C# code to implement priority-queue
// using array implementation of
// binary heap
using System;
class GFG{
static int []H = new int[50];
static int size = -1;
// Function to return the index of the
// parent node of a given node
static int parent(int i)
{
return (i - 1) / 2;
}
// Function to return the index of the
// left child of the given node
static int leftChild(int i)
{
return ((2 * i) + 1);
}
// Function to return the index of the
// right child of the given node
static int rightChild(int i)
{
return ((2 * i) + 2);
}
// Function to shift up the
// node in order to maintain
// the heap property
static void shiftUp(int i)
{
while (i > 0 &&
H[parent(i)] < H[i])
{
// Swap parent and current node
swap(parent(i), i);
// Update i to parent of i
i = parent(i);
}
}
// Function to shift down the node in
// order to maintain the heap property
static void shiftDown(int i)
{
int maxIndex = i;
// Left Child
int l = leftChild(i);
if (l <= size &&
H[l] > H[maxIndex])
{
maxIndex = l;
}
// Right Child
int r = rightChild(i);
if (r <= size &&
H[r] > H[maxIndex])
{
maxIndex = r;
}
// If i not same as maxIndex
if (i != maxIndex)
{
swap(i, maxIndex);
shiftDown(maxIndex);
}
}
// Function to insert a
// new element in
// the Binary Heap
static void insert(int p)
{
size = size + 1;
H[size] = p;
// Shift Up to maintain
// heap property
shiftUp(size);
}
// Function to extract
// the element with
// maximum priority
static int extractMax()
{
int result = H[0];
// Replace the value
// at the root with
// the last leaf
H[0] = H[size];
size = size - 1;
// Shift down the replaced
// element to maintain the
// heap property
shiftDown(0);
return result;
}
// Function to change the priority
// of an element
static void changePriority(int i,
int p)
{
int oldp = H[i];
H[i] = p;
if (p > oldp)
{
shiftUp(i);
}
else
{
shiftDown(i);
}
}
// Function to get value of
// the current maximum element
static int getMax()
{
return H[0];
}
// Function to remove the element
// located at given index
static void Remove(int i)
{
H[i] = getMax() + 1;
// Shift the node to the root
// of the heap
shiftUp(i);
// Extract the node
extractMax();
}
static void swap(int i, int j)
{
int temp = H[i];
H[i] = H[j];
H[j] = temp;
}
// Driver Code
public static void Main(String[] args)
{
/* 45
/ \
31 14
/ \ / \
13 20 7 11
/ \
12 7
Create a priority queue shown in
example in a binary max heap form.
Queue will be represented in the
form of array as:
45 31 14 13 20 7 11 12 7 */
// Insert the element to the
// priority queue
insert(45);
insert(20);
insert(14);
insert(12);
insert(31);
insert(7);
insert(11);
insert(13);
insert(7);
int i = 0;
// Priority queue before extracting max
Console.Write("Priority Queue : ");
while (i <= size)
{
Console.Write(H[i] + " ");
i++;
}
Console.Write("\n");
// Node with maximum priority
Console.Write("Node with maximum priority : " +
extractMax() + "\n");
// Priority queue after extracting max
Console.Write("Priority queue after " +
"extracting maximum : ");
int j = 0;
while (j <= size)
{
Console.Write(H[j] + " ");
j++;
}
Console.Write("\n");
// Change the priority of element
// present at index 2 to 49
changePriority(2, 49);
Console.Write("Priority queue after " +
"priority change : ");
int k = 0;
while (k <= size)
{
Console.Write(H[k] + " ");
k++;
}
Console.Write("\n");
// Remove element at index 3
Remove(3);
Console.Write("Priority queue after " +
"removing the element : ");
int l = 0;
while (l <= size)
{
Console.Write(H[l] + " ");
l++;
}
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript code to implement priority-queue
// using array implementation of
// binary heap
var H = Array(50).fill(0);
var size = -1;
// Function to return the index of the
// parent node of a given node
function parent(i)
{
return parseInt((i - 1) / 2);
}
// Function to return the index of the
// left child of the given node
function leftChild(i)
{
return parseInt((2 * i) + 1);
}
// Function to return the index of the
// right child of the given node
function rightChild(i)
{
return parseInt((2 * i) + 2);
}
// Function to shift up the node in order
// to maintain the heap property
function shiftUp( i)
{
while (i > 0 && H[parent(i)] < H[i]) {
// Swap parent and current node
swap(parent(i), i);
// Update i to parent of i
i = parent(i);
}
}
function swap(i, j)
{
var temp = H[i];
H[i] = H[j];
H[j] = temp;
}
// Function to shift down the node in
// order to maintain the heap property
function shiftDown( i)
{
var maxIndex = i;
// Left Child
var l = leftChild(i);
if (l <= size && H[l] > H[maxIndex]) {
maxIndex = l;
}
// Right Child
var r = rightChild(i);
if (r <= size && H[r] > H[maxIndex]) {
maxIndex = r;
}
// If i not same as maxIndex
if (i != maxIndex) {
swap(i, maxIndex);
shiftDown(maxIndex);
}
}
// Function to insert a new element
// in the Binary Heap
function insert( p)
{
size = size + 1;
H[size] = p;
// Shift Up to maintain heap property
shiftUp(size);
}
// Function to extract the element with
// maximum priority
function extractMax()
{
var result = H[0];
// Replace the value at the root
// with the last leaf
H[0] = H[size];
size = size - 1;
// Shift down the replaced element
// to maintain the heap property
shiftDown(0);
return result;
}
// Function to change the priority
// of an element
function changePriority(i, p)
{
var oldp = H[i];
H[i] = p;
if (p > oldp) {
shiftUp(i);
}
else {
shiftDown(i);
}
}
// Function to get value of the current
// maximum element
function getMax()
{
return H[0];
}
// Function to remove the element
// located at given index
function remove(i)
{
H[i] = getMax() + 1;
// Shift the node to the root
// of the heap
shiftUp(i);
// Extract the node
extractMax();
}
// Driver Code
/* 45
/ \
31 14
/ \ / \
13 20 7 11
/ \
12 7
Create a priority queue shown in
example in a binary max heap form.
Queue will be represented in the
form of array as:
45 31 14 13 20 7 11 12 7 */
// Insert the element to the
// priority queue
insert(45);
insert(20);
insert(14);
insert(12);
insert(31);
insert(7);
insert(11);
insert(13);
insert(7);
var i = 0;
// Priority queue before extracting max
document.write( "Priority Queue : ");
while (i <= size) {
document.write( H[i] + " ");
i++;
}
document.write( "<br>");
// Node with maximum priority
document.write( "Node with maximum priority : "
+ extractMax() + "<br>");
// Priority queue after extracting max
document.write( "Priority queue after "
+ "extracting maximum : ");
var j = 0;
while (j <= size) {
document.write( H[j] + " ");
j++;
}
document.write( "<br>");
// Change the priority of element
// present at index 2 to 49
changePriority(2, 49);
document.write( "Priority queue after "
+ "priority change : ");
var k = 0;
while (k <= size) {
document.write( H[k] + " ");
k++;
}
document.write( "<br>");
// Remove element at index 3
remove(3);
document.write( "Priority queue after "
+ "removing the element : ");
var l = 0;
while (l <= size) {
document.write( H[l] + " ");
l++;
}
// This code is contributed by noob2000.
</script>
Producción
Priority Queue : 45 31 14 13 20 7 11 12 7 Node with maximum priority : 45 Priority queue after extracting maximum : 31 20 14 13 7 7 11 12 Priority queue after priority change : 49 20 31 13 7 7 11 12 Priority queue after removing the element : 49 20 31 12 7 7 11
Complejidad de tiempo: La complejidad de tiempo de toda la operación es O(log N) excepto GetMax() que tiene una complejidad de tiempo de O(1).
Espacio Auxiliar: O(N)