Maximice la cantidad de juguetes que se pueden comprar con la cantidad K usando min Heap

Dada una array arr[] que consiste en el costo de los juguetes y un número entero K que representa la cantidad de dinero disponible para comprar juguetes. La tarea es encontrar el número máximo de juguetes que uno puede comprar con la cantidad K.
Nota: Uno puede comprar solo 1 cantidad de un juguete en particular.

Ejemplos: 
 

Entrada: arr[] = {1, 12, 5, 111, 200, 1000, 10, 9, 12, 15}, K = 50 
Salida: 6 
juguetes con cantidad 1, 5, 9, 10, 12 y 12 
latas ser comprado resultando en una cantidad total de 49. 
Por lo tanto, el número máximo de juguetes es 6.

Entrada: arr[] = {1, 12, 5, 111, 200, 1000, 10}, K = 50 
Salida: 4

Enfoque: inserte todos los elementos de la array dada en una cola de prioridad ahora, uno por uno, elimine los elementos de esta cola de prioridad y agregue estos costos en una suma variable inicializada en 0 . Siga eliminando los elementos mientras que la nueva adición mantiene la suma más pequeña que K . Al final, el conteo de elementos eliminados será la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// maximum toys that can be bought
int maxToys(int arr[], int n, int k)
{
 
    // Create a priority_queue and push
    // all the array elements in it
    priority_queue<int, vector<int>, greater<int> > pq;
    for (int i = 0; i < n; i++) {
        pq.push(arr[i]);
    }
 
    // To store the count of maximum
    // toys that can be bought
    int count = 0;
    while (pq.top() <= k) {
        count++;
        k = k - pq.top();
        pq.pop();
    }
    return count;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 12, 5, 111, 200, 1000, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 50;
 
    cout << maxToys(arr, n, k);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
import java.util.*;
 
class GFG{
     
// Function to return the count of
// maximum toys that can be bought    
public static int maxToys(int[] arr, int k)
{
    int n = arr.length;
     
    // Create a priority_queue and push
    // all the array elements in it
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    for(int i = 0; i < n; i++)
    {
        pq.offer(arr[i]);
    }
     
    // To store the count of maximum
    // toys that can be bought
    int count = 0;
    while (!pq.isEmpty() && pq.peek() <= k)
    {
        k = k - pq.poll();
        count++;
    }
    return count;
}
 
// Driver code
public static void main (String[] args)
{
    int[] arr = new int[]{ 1, 12, 5, 111,
                           200, 1000, 10 };
    int k = 50;                      
     
      System.out.println(maxToys(arr, k));     
}
}
 
// This code is contributed by ankit bajpai

# Python3 implementation of the approach
 
# Function to return the count of
# maximum toys that can be bought
 
# importing heapq module
import heapq
 
 
def maxToys(arr, n, k):
    # Create a priority_queue and push
    # all the array elements in it
    pq = arr
    heapq.heapify(pq)
    # To store the count of maximum
    # toys that can be bought
    count = 0
 
    while (pq[0] <= k):
        count += 1
        k -= pq[0]
        # assigning last element of the min heap
        # to top of the heap
        pq[0] = pq[-1]
        # deleting the last element.
        pq.pop()
        # pq.pop() is an O(1) operation
        # maintaining the heap property again
 
        heapq.heapify(pq)
    return count
 
 
# Driver code
arr = [1, 12, 5, 111, 200, 1000, 10]
n = len(arr)
k = 50
print(maxToys(arr, n, k))

// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
     
    // Function to return the count of
    // maximum toys that can be bought
    static int maxToys(int[] arr, int n, int k)
    {
      
        // Create a priority_queue and push
        // all the array elements in it
        List<int> pq = new List<int>();
        for (int i = 0; i < n; i++)
        {
            pq.Add(arr[i]);
        }
         
        pq.Sort();
      
        // To store the count of maximum
        // toys that can be bought
        int count = 0;
        while (pq[0] <= k)
        {
            count++;
            k = k - pq[0];
            pq.RemoveAt(0);
        }
        return count;
    }
 
  // Driver code
  static void Main()
  {
    int[] arr = { 1, 12, 5, 111, 200, 1000, 10 };
    int n = arr.Length;
    int k = 50;
    Console.WriteLine(maxToys(arr, n, k));
  }
}
 
// This code is contributed by divyeshrabadiya07.

<script>
 
    // Javascript implementation of the approach
     
    // Function to return the count of
    // maximum toys that can be bought
    function maxToys(arr, n, k)
    {
       
        // Create a priority_queue and push
        // all the array elements in it
        let pq = [];
        for (let i = 0; i < n; i++)
        {
            pq.push(arr[i]);
        }
          
        pq.sort(function(a, b){return a - b});
       
        // To store the count of maximum
        // toys that can be bought
        let count = 0;
        while (pq[0] <= k)
        {
            count++;
            k = k - pq[0];
            pq.shift();
        }
        return count;
    }
       
    let arr = [ 1, 12, 5, 111, 200, 1000, 10 ];
    let n = arr.length;
    let k = 50;
    document.write(maxToys(arr, n, k));
     
</script>

4

Complejidad de tiempo: O(N*logN)
Espacio auxiliar: O(N)