STL Priority Queue es la implementación de Heap Data Structure . De forma predeterminada, es un montón máximo y puede ser fácilmente para tipos de datos primitivos . Hay algunas aplicaciones importantes que se pueden encontrar en este artículo .
La cola de prioridad se puede inicializar de dos maneras, ya sea empujando todos los elementos uno por uno o inicializándolos usando su constructor . En este artículo, discutiremos ambos métodos y examinaremos sus complejidades temporales .
Método 1: el enfoque más simple es atravesar la array dada y empujar cada elemento uno por uno en la cola de prioridad. En este método, el método de inserción en la cola de prioridad toma el tiempo O (log N) . Donde N es el número de elementos de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to initialize the
// priority queue
#include <bits/stdc++.h>
using namespace std;
// Driver Code
int main()
{
int arr[] = { 15, 25, 6, 54, 45, 26, 12 };
int N = sizeof(arr) / sizeof(arr[0]);
// Initialize priority_queue
priority_queue<int> pq;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Push the element arr[i]
pq.push(arr[i]);
}
cout << "The elements in priority"
<< " Queue are: ";
// Traverse until pq is non-empty
while (!pq.empty()) {
// Print the element in pq
cout << pq.top() << " ";
// Pop the top element
pq.pop();
}
return 0;
}
Java
// Java program to initialize the
// priority queue
import java.util.*;
public class GFG
{
public static void main(String[] args)
{
int[] arr = { 15, 25, 6, 54, 45, 26, 12 };
int N = arr.length;
// Initialize priority_queue
Vector<Integer> pq = new Vector<Integer>();
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
// Push the element arr[i]
pq.add(arr[i]);
}
Collections.sort(pq);
Collections.reverse(pq);
System.out.print("The elements in priority" + " Queue are: ");
// Traverse until pq is non-empty
while (pq.size() > 0)
{
// Print the element in pq
System.out.print(pq.get(0) + " ");
// Pop the top element
pq.remove(0);
}
}
}
// This code is contributed by divyesh072019.
Python3
# Python3 program to initialize the
# priority queue
# Driver Code
if __name__ == '__main__':
arr = [15, 25, 6, 54, 45, 26, 12]
N = len(arr)
# Initialize priority_queue
pq = []
# Traverse the array arr[]
for i in range(N):
# Push the element arr[i]
pq.append(arr[i])
print("The elements in priority Queue are: ", end = "")
pq = sorted(pq)
# Traverse until pq is non-empty
while (len(pq) > 0):
# Print the element in pq
print(pq[-1], end = " ")
# Pop the top element
del pq[-1]
# This code is contributed by mohit kumar 29.
C#
// C# program to initialize the
// priority queue
using System;
using System.Collections.Generic;
class GfG
{
public static void Main()
{
int[] arr = { 15, 25, 6, 54, 45, 26, 12 };
int N = arr.Length;
// Initialize priority_queue
List<int> pq = new List<int>();
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Push the element arr[i]
pq.Add(arr[i]);
}
pq.Sort();
pq.Reverse();
Console.Write("The elements in priority" + " Queue are: ");
// Traverse until pq is non-empty
while (pq.Count > 0) {
// Print the element in pq
Console.Write(pq[0] + " ");
// Pop the top element
pq.RemoveAt(0);
}
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program to initialize the priority queue
let arr = [ 15, 25, 6, 54, 45, 26, 12 ];
let N = arr.length;
// Initialize priority_queue
let pq = [];
// Traverse the array arr[]
for (let i = 0; i < N; i++) {
// Push the element arr[i]
pq.push(arr[i]);
}
pq.sort(function(a, b){return a - b});
pq.reverse();
document.write("The elements in priority" + " Queue are: ");
// Traverse until pq is non-empty
while (pq.length > 0) {
// Print the element in pq
document.write(pq[0] + " ");
// Pop the top element
pq.shift();
}
// This code is contributed by suresh07.
</script>
The elements in priority Queue are: 54 45 26 25 15 12 6
Complejidad de tiempo: O(N*log N), donde N es el número total de elementos en la array.
Espacio Auxiliar: O(N)
Método 2: en este método, copie todos los elementos de la array en la cola de prioridad mientras la inicializa (esta copia se realizará utilizando el constructor de copia de la cola de prioridad). En este método, la cola de prioridad utilizará el método de montón de compilación internamente. Por lo tanto, el método del montón de compilación está tomando tiempo O (N) .
Sintaxis:
Priority_queue<int> pq(dirección del primer elemento, dirección del siguiente del último elemento);
Sintaxis para la array :
Priority_queue<int> pq (arr, arr + N)
donde arr es la array y N es el tamaño de la array.
Sintaxis para el vector :
cola_prioridad<int> pq(v.begin(), v.end());
donde v es el vector.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to initialize the
// priority queue
#include <iostream>
#include <queue>
using namespace std;
// Driver Code
int main()
{
int arr[] = { 15, 25, 6, 54, 45, 26, 12 };
int N = sizeof(arr) / sizeof(arr[0]);
// By this type of initialization
// the priority_queue is using
// build heap to make the max heap
cout << "The elements in priority"
<< " Queue are: ";
// Initialize priority_queue
priority_queue<int> pq(arr, arr + N);
// Iterate until pq is non empty
while (!pq.empty()) {
// Print the element
cout << pq.top() << " ";
pq.pop();
}
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
public static void main(String[] args)
{
Integer[] arr = { 15, 25, 6, 54, 45, 26, 12 };
int N = arr.length;
// By this type of initialization
// the priority_queue is using
// build heap to make the max heap
System.out.println("The elements in priority"
+ " Queue are: ");
// Initialize priority_queue
ArrayList<Integer> l = new ArrayList<Integer>();
Collections.addAll(l, arr);
Collections.sort(l);
// Iterate until pq is non empty
while (l.size() != 0) {
// Print the element
System.out.print(l.get(l.size() - 1) + " ");
l.remove(l.size() - 1);
}
}
}
// This code is contributed by phasing17
Python3
# Python3 program to initialize the
# priority queue
# Driver Code
if __name__=='__main__':
arr = [ 15, 25, 6, 54, 45, 26, 12 ]
N = len(arr)
# By this type of initialization
# the priority_queue is using
# build heap to make the max heap
print("The elements in priority Queue are: ", end = '')
# Initialize priority_queue
pq = arr
pq.sort()
# Iterate until pq is non empty
while (len(pq) != 0):
# Print the element
print(pq[-1], end = ' ')
pq.pop()
# This code is contributed by rutvik_56.
C#
// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Driver Code
public static void Main(string[] args)
{
int []arr= { 15, 25, 6, 54, 45, 26, 12 };
int N = arr.Length;
// By this type of initialization
// the priority_queue is using
// build heap to make the max heap
Console.Write("The elements in priority"
+ " Queue are: ");
// Initialize priority_queue
List<int> l = new List<int>(arr);
l.Sort();
// Iterate until pq is non empty
while (l.Count!=0) {
// Print the element
Console.Write(l[l.Count-1]+ " ");
l.RemoveAt(l.Count-1);
}
}
}
// This code is contributed by noob2000.
Javascript
<script>
// JAvaScript program to initialize the
// priority queue
let arr = [ 15, 25, 6, 54, 45, 26, 12 ];
let N = arr.length;
// By this type of initialization
// the priority_queue is using
// build heap to make the max heap
document.write("The elements in priority Queue are: ")
// Initialize priority_queue
let pq = arr;
pq.sort(function(a, b){return a - b;});
// Iterate until pq is non empty
while(pq.length != 0)
// Print the element
document.write(pq.pop()+" ");
// This code is contributed by unknown2108
</script>
The elements in priority Queue are: 54 45 26 25 15 12 6
Complejidad temporal: O(N), donde N es el número total de elementos de la array.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ratulmaity2504 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA