Эффективный способ инициализации очереди приоритетов
Опубликовано: 21 Января, 2022
STL Priority Queue - это реализация структуры данных кучи. По умолчанию это максимальная куча, и ее можно легко использовать для примитивных типов данных. В этой статье можно найти несколько важных применений.
Очередь с приоритетом может быть инициализирована двумя способами: путем последовательного нажатия всех элементов или инициализации с помощью их конструктора. В этой статье мы обсудим оба метода и рассмотрим их временную сложность.
Метод 1. Самый простой подход - пройти по заданному массиву и поместить каждый элемент один за другим в очередь с приоритетом. В этом методе метод push в очереди с приоритетом занимает время O (log N) . Где N - количество элементов в массиве.
Below is the implementation of the above approach:
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> |
Output:
The elements in priority Queue are: 54 45 26 25 15 12 6