Last Updated on March 22, 2022 by Ria Pathak
Concepts Used
Heap
Difficulty Level
Easy
Problem Statement :
Given an array arr[ ] and a number
KwhereKis smaller than the size of the array, the task is to find theKthsmallest element in the given array. It is given that all array elements are distinct.
See original problem statement here
Solution Approach :
Introduction :
Idea is to create a min-heap then extract the first (k-1) elements.
Now print the first element of the heap.
Method 1 :
Sort the array in increasing order using any sorting algorithm. Now print the kth value in the array which is our
kthsmallest value.
Method 2 :
We will create a min-heap of size
n. 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 it’s parent is always smaller than the item itself. If the parent is greater, then we need to swap the current item with its parent.In order to print the kth smallest element we need to extract() the first
k-1elements and now print the first element of our heap.
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);
}
while(--k)
{
extract(heap,&size);
}
printf("%d\n",extract(heap,&size));
}
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);
}
while(--k)
{
extract(heap,&size);
}
cout<<heap[0]<<endl;
}
return 0;
}
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int t=sc.nextInt();
while(t-->0) {
int n = sc.nextInt();
int k = sc.nextInt();
MinHeap minHeap = new MinHeap(n);
for (int i = 0; i < n; i++) {
minHeap.insert(sc.nextInt());
}
for(int i=0;i<k-1;i++)
minHeap.remove();
System.out.println(minHeap.remove());
}
}
}
class MinHeap
{
private int[]Heap;
private int size;
private int maxSize;
private static final int FRONT = 1;
MinHeap(int maxSize)
{
this.maxSize = maxSize;
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;
}
private boolean isLeaf(int pos)
{
if(pos>=(size/2) && pos<=size)
return true;
return false;
}
private void swap(int fpos, int spos)
{
int temp;
temp = Heap[fpos];
Heap[fpos]=Heap[spos];
Heap[spos]=temp;
}
private void minHeapify(int pos)
{
int left = leftChild(pos);
int right = rightChild(pos);
int largest = pos;
if(left<=size && Heap[left]<Heap[largest])
largest=left;
if(right<=size && Heap[right]<Heap[largest])
largest = right;
if(largest!=pos)
{
swap(pos, largest);
minHeapify(largest);
}
}
void insert(int element)
{
if(size>=maxSize)
return;
Heap[++size]=element;
int i=size;
while(Heap[i]<Heap[parent(i)])
{
swap(i,parent(i));
i=parent(i);
}
}
private void build_heap()
{
int j=(int)Math.floor(size/2.0);
for(int i=j;i>=1;i--){
minHeapify(i);
}
}
public void heapSort(Writer wr) throws IOException {
build_heap();
int length=size;
for(int i=size;i>=2;i--)
{
swap(1,i);
size--;
minHeapify(1);
}
size=length;
// printHeap(wr);
}
public int remove()
{
int popped = Heap[FRONT];
Heap[FRONT] = Heap[size];
size=size-1;
minHeapify(FRONT);
return popped;
}
public void deleteKey(int i)
{
decreaseKey(i, Integer.MIN_VALUE);
remove();
}
private void decreaseKey(int i, int new_val) {
Heap[i]=new_val;
while(i !=0 && Heap[parent(i)]>Heap[i])
{
swap(i,parent(i));
i=parent(i);
}
}
}
[forminator_quiz id="1632"]
So, in this blog, we have tried to explain the concept of Heap. If you want to solve more questions on Heap, which are curated by our expert mentors at PrepBytes, you can follow this link Heap.