Last Updated on March 29, 2022 by Ria Pathak
Concepts Used
Heap
Difficulty Level
Medium
Problem Statement :
We are given
Nbook costs, andkamount of money. We need to find the maximum number of books we can buy with the amountk.
See original problem statement here
Solution Approach :
Introduction :
In order to buy maximum number of books we have to buy the books with lesser price first. We will sum up the costs of the books we have bought.
If the sum is greater thank, print the number of books we have bought.
Method 1:
-
We need to buy maximum number of books which is only possible if we buy books with least prices. If we have
kamount of money we can sort the prices in increasing order, now we starting buying books and subtracting the prices of the books we bought fromkand also keep a counter variable to store the number of books we have bought. -
Now when
price-k<=0, we stop and print the books count. -
We need to geneate a min heap of size
Nto get the least price every time we buy a book. -
In a min-heap, the root always stores the smaller value as compared to its left & right subtree, this condition needs to be true for every node. We need to insert each item one by one such that parent is always smaller than the item itself. If parent is greater, then swap the current item with its parent.
-
Insert the cost of the books in the heap. Now extract the costs, add them to
S& also keep track of the number of books we are buying. -
Once
Sis greater thankprint the number of books.
extract(): Removes the minimum element from Min-Heap. Time Complexity of this Operation is O(Logn) as this operation needs to maintain the heap property (by calling heapify()) after removing root.
heapify(): Maintains the heap property for each node. If any node does not follow heap property it swaps the node with the node which is smaller ,or greater (in case of max-heap), than the node.
Below is the algorithm of above approach.
Algorithms :
Insert() :
- Insert the item at the last index, and increment the size by 1.
- Then, check if the inserted item is smaller than its parent,
- If yes, then swap the inserted item with its parent.
- If no, then do nothing.
- Now, go to step
2and repeat untill we reach root (first element).
Extract() :
- Store the value of the first node of our heap (
temp = heap[0]).- Replace the root node with the farthest right node (last element).
- Decrease the size by
1.(heap[0] = heap[size-1])- Perform heapify starting from the new root.
- Return the stored value.(temp)
Heapify () :
- if the heap property holds true then you are done.
- else if
- the replacement node value <= its parent nodes value
then swap them, and repeat step 3.- else
- swap the replacement node with the smallest child node, and
repeat step 3.
Example:
Solutions:
#include <stdio.h>
int parent(int i)
{
return (i-1)/2;
}
int left(int i)
{
return (i*2)+1;
}
int right(int i)
{
return (i*2)+2;
}
void swap(int *a,int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void insert(int heap[],int *size, int val)
{
heap[*size] = val;
int i = *size;
(*size)++;
while(i!=0 && heap[parent(i)]>heap[i])
{
swap(&heap[parent(i)],&heap[i]);
i = parent(i);
}
}
void heapify(int heap[],int i,int size)
{
int l = left(i);
int r = right(i);
int s = i;
if(l<size && heap[l]<heap[i])
s = l;
if(r<size && heap[r]<heap[s])
s = r;
if(s!=i)
{
swap(&heap[i],&heap[s]);
heapify(heap,s,size);
}
}
int extract(int heap[],int *size)
{
int root = heap[0];
heap[0] = heap[(*size)-1];
(*size)--;
heapify(heap,0,*size);
return root;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,k;
scanf("%d %d", &n,&k);
int *heap = (int *)malloc(sizeof(int)*n);
int size = 0;
for(int i=0;i<n;i++)
{
int t;
scanf("%d",&t);
insert(heap,&size,t);
}
int count=0,sum=0;
while(k>=0 && size)
{
k -= extract(heap,&size);
count++;
}
printf("%d\n",count-1);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int parent(int i)
{
return (i-1)/2;
}
int left(int i)
{
return (i*2)+1;
}
int right(int i)
{
return (i*2)+2;
}
void swap(int *a,int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void insert(int heap[],int *size, int val)
{
heap[*size]= val;
int i = *size;
(*size)++;
while(i!=0 && heap[parent(i)]>heap[i])
{
swap(&heap[parent(i)],&heap[i]);
i = parent(i);
}
}
void heapify(int heap[],int i,int size)
{
int l = left(i);
int r = right(i);
int s = i;
if(l<size && heap[l]<heap[i])
s = l;
if(r<size && heap[r]<heap[s])
s = r;
if(s!=i)
{
swap(&heap[i],&heap[s]);
heapify(heap,s,size);
}
}
int extract(int heap[],int *size)
{
int root = heap[0];
heap[0] = heap[*size-1];
(*size)--;
heapify(heap,0,*size);
return root;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
int *heap = (int *)malloc(sizeof(int)*n);
int size = 0;
for(int i=0;i<n;i++)
{
int t;
cin>>t;
insert(heap,&size,t);
}
int count=0,sum=0;
while(k>=0 && size)
{
k -= extract(heap,&size);
count++;
}
cout<<count-1<<endl;
}
return 0;
}
import java.util.*;
import java.io.*;
public class Main {
private int[] Heap;
private int size;
private int maxsize;
private static final int FRONT = 1;
public Main(int maxsize)
{
this.maxsize = maxsize;
this.size = 0;
Heap = new int[this.maxsize + 1];
Heap[0] = Integer.MIN_VALUE;
}
private int parent(int pos)
{
return pos / 2;
}
private int leftChild(int pos)
{
return (2 * pos);
}
private int rightChild(int pos)
{
return (2 * pos) + 1;
}
// Function that returns true if the passed
// node is a leaf node
private boolean isLeaf(int pos)
{
if (pos >= (size / 2) && pos <= size) {
return true;
}
return false;
}
// Function to swap two nodes of the heap
private void swap(int fpos, int spos)
{
int tmp;
tmp = Heap[fpos];
Heap[fpos] = Heap[spos];
Heap[spos] = tmp;
}
// Function to heapify the node at pos
private void minHeapify(int pos)
{
// If the node is a non-leaf node and greater
// than any of its child
if (!isLeaf(pos)) {
if (Heap[pos] > Heap[leftChild(pos)]
|| Heap[pos] > Heap[rightChild(pos)]) {
// Swap with the left child and heapify
// the left child
if (Heap[leftChild(pos)] < Heap[rightChild(pos)]) {
swap(pos, leftChild(pos));
minHeapify(leftChild(pos));
}
// Swap with the right child and heapify
// the right child
else {
swap(pos, rightChild(pos));
minHeapify(rightChild(pos));
}
}
}
}
// Function to insert a node into the heap
public void insert(int element)
{
if (size >= maxsize) {
return;
}
Heap[++size] = element;
int current = size;
while (current != 1 && Heap[current] < Heap[parent(current)]) {
swap(current, parent(current));
current = parent(current);
}
}
public int remove()
{
int popped = Heap[FRONT];
Heap[FRONT] = Heap[size--];
minHeapify(FRONT);
return popped;
}
// Driver code
public static void main(String[] arg)
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0)
{
int n = sc.nextInt();
int k = sc.nextInt();
int []a = new int[n];
Main minHeap = new Main(n);
for(int i=0;i<n;i++)
{
a[i] = sc.nextInt();
minHeap.insert(a[i]);
}
int count=0,sum=0;
while(k>=0)
{
k -= minHeap.remove();
count++;
}
System.out.println(count-1);
}
}
}
[forminator_quiz id="1685"]
This article tried to discuss the concept of heap. Hope this blog helps you understand and solve the problem. To practice more problems on heap you can check out MYCODE | Competitive Programming