Dada una array arr[] que consiste en N enteros y un entero K , la tarea es encontrar el K -ésimo elemento más pequeño en la array usando Priority Queue .
Ejemplos:
Entrada: arr[]= {5, 20, 10, 7, 1}, N = 5, K = 2
Salida: 5
Explicación: En la array dada, el segundo elemento más pequeño es 5. Por lo tanto, la salida requerida es 5 .Entrada: arr[] = {5, 20, 10, 7, 1}, N = 5, K = 5
Salida: 20
Explicación: En la array dada, el quinto elemento más pequeño es 20. Por lo tanto, la salida requerida es 20 .
Enfoque: la idea es usar PriorityQueue Collection en Java o la biblioteca STL de prioridad_cola para implementar Max_Heap para encontrar el K -ésimo elemento de array más pequeño. Siga los pasos a continuación para resolver el problema:
- Implemente Max Heap utilizando una cola de prioridad .
- Empuje los primeros elementos de la array K en la cola_prioridad .
- A partir de ahí, después de cada inserción de un elemento de array, extraiga el elemento en la parte superior de la cola de prioridad .
- Después de completar el recorrido de la array , imprima el elemento en la parte superior de la cola de prioridad como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find kth smallest array element void kthSmallest(vector<int>& v, int N, int K) { // Implement Max Heap using // a Priority Queue priority_queue<int> heap1; for (int i = 0; i < N; ++i) { // Insert elements into // the priority queue heap1.push(v[i]); // If size of the priority // queue exceeds k if (heap1.size() > K) { heap1.pop(); } } // Print the k-th smallest element cout << heap1.top() << endl; } // Driver code int main() { // Given array vector<int> vec = { 5, 20, 10, 7, 1 }; // Size of array int N = vec.size(); // Given K int K = 2; // Function Call kthSmallest(vec, N, K % N); return 0; }
Java
// Java program for the above approach import java.util.*; class CustomComparator implements Comparator<Integer> { @Override public int compare(Integer number1, Integer number2) { int value = number1.compareTo(number2); // elements are sorted in reverse order if (value > 0) { return -1; } else if (value < 0) { return 1; } else { return 0; } } } class GFG{ // Function to find kth smallest array element static void kthSmallest(int []v, int N, int K) { // Implement Max Heap using // a Priority Queue PriorityQueue<Integer> heap1 = new PriorityQueue<Integer>(new CustomComparator()); for (int i = 0; i < N; ++i) { // Insert elements into // the priority queue heap1.add(v[i]); // If size of the priority // queue exceeds k if (heap1.size() > K) { heap1.remove(); } } // Print the k-th smallest element System.out.print(heap1.peek() +"\n"); } // Driver code public static void main(String[] args) { // Given array int []vec = { 5, 20, 10, 7, 1 }; // Size of array int N = vec.length; // Given K int K = 2; // Function Call kthSmallest(vec, N, K % N); } } // This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach # Function to find kth smallest array element def kthSmallest(v, N, K): # Implement Max Heap using # a Priority Queue heap1 = [] for i in range(N): # Insert elements into # the priority queue heap1.append(v[i]) # If size of the priority # queue exceeds k if (len(heap1) > K): heap1.sort() heap1.reverse() del heap1[0] # Print the k-th smallest element heap1.sort() heap1.reverse() print(heap1[0]) # Driver code # Given array vec = [ 5, 20, 10, 7, 1 ] # Size of array N = len(vec) # Given K K = 2 # Function Call kthSmallest(vec, N, K % N) # This code is contributed by divyeshrabadiya07
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find kth smallest array element static void kthSmallest(int []v, int N, int K) { // Implement Max Heap using // a Priority Queue List<int> heap1 = new List<int>(); for (int i = 0; i < N; ++i) { // Insert elements into // the priority queue heap1.Add(v[i]); // If size of the priority // queue exceeds k if (heap1.Count > K) { heap1.Sort(); heap1.Reverse(); heap1.RemoveAt(0); } } heap1.Sort(); heap1.Reverse(); // Print the k-th smallest element Console.WriteLine(heap1[0]); } // Driver code public static void Main(String[] args) { // Given array int []vec = { 5, 20, 10, 7, 1 }; // Size of array int N = vec.Length; // Given K int K = 2; // Function Call kthSmallest(vec, N, K % N); } } // This code is contributed by gauravrajput1
Javascript
<script> // Javascript program for the above approach // Function to find kth smallest array element function kthSmallest(v,N,K) { let heap1 = []; for (let i = 0; i < N; ++i) { // Insert elements into // the priority queue heap1.push(v[i]); // If size of the priority // queue exceeds k if (heap1.length > K) { heap1.sort(function(a,b){ return a-b; }); heap1.reverse(); heap1.shift(); } } heap1.sort(function(a,b){ return a-b; }); heap1.reverse(); // Print the k-th smallest element document.write(heap1[0] +"<br>"); } // Driver code // Given array let vec=[5, 20, 10, 7, 1 ]; // Size of array let N = vec.length; // Given K let K = 2; // Function Call kthSmallest(vec, N, K % N); // This code is contributed by patel2127 </script>
5
Complejidad de tiempo: O(N LogK)
Espacio auxiliar: O(K), ya que la cola de prioridad en cualquier momento se mantiene en un máximo de k elementos.