Heaps and Priority Queue

Contents:

1. Heaps and Priority Queue
2. Types of Heap
1. Min-heap
2. Max-heap
3.  Some uses of heap with their complexities.
4.  Problem from Hackerearth:
1. Brute Force solution
2. Solution using priority_queue

Heaps and Priority Queue:

Heap is a tree-based data structure , in which all the nodes are in specific order whith respect to
their children.Most commonly used heap is binary heap in which each node has atmost 2 children.
In a complete binary tree with n nodes, height will be log2(n).

Types of Heap:

Max_heap: In this the nodes are arranges in such a way that parent node is greater than all its child nodes.

Have a close look at the above picture. Node 6 is greater than its child nodes-4 & 5 , and similarly for other nodes.

Min_heap: Based on the same concept we have min heap in which parent node is less than its child nodes.

Closely observe the above picture, each parent node is less than its child nodes.

NOTE:-Root node of min heap gives us the smallest element and Root of max heap gives us the largest element.

Benifits of using heap:

1. Extract min/max - O(log n)
2. Get min/max - O(1)
3. BuildHeap - O(n)
4. Heapify - O(logn)

Solution of a Hackerearth Problem:

Lets discuss the implementation with the help of question given HERE

Brute-force:
Use sorting and find the element at the kth position.
But sorting takes O(nlogn).
indexing kth element O(1) but removing it takes O(n).

Optimal approach using heap:
Note: here we use priority queue which is an implementation of heap data structure.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

#include<bits/stdc++.h> using namespace std; main() { long long int n,i; scanf("%lld",&n); long long int sum[n]; for(i=0;i<n;i++) { long long int a; scanf("%lld",&a); sum[i]=a; } for(i=0;i<n;i++) { long long int a; scanf("%lld",&a); sum[i]+=a; } for(i=0;i<n;i++) { long long int a; scanf("%lld",&a); sum[i]+=a; //sum of three categories } /*priority queue in ascending order helps to extract the minimum element similar to min heap*/ priority_queue<long long int,vector<long long int>,greater<long long int> >min_heap; for(i=0;i<n;i++) { min_heap.push(sum[i]); } long long int q; scanf("%lld",&q); while(q--) { long long int k,t; scanf("%lld",&k); vector<long long int>v; if(k>min_heap.size()) { printf("-1\n"); continue; } for(i=0;i<k;i++) { t= min_heap.top();/*extract the first k minimum elements*/ v.push_back(t); /*and get the kth minimum*/ min_heap.pop(); /*and insert back in heap the rest*/ } printf("%lld\n",v[k-1]); v.pop_back(); for(i=k-2;i>=0;i--) { t=v[i]; min_heap.push(t); v.pop_back(); } } }

The Time complexity of above implementation is O(q*klog(n)).

There is another method of finding kth smallest/largest element using order statistics which can be done in O(n). This will be discussed in next post.
Till then
HAPPY CODING! :)


Contributed by Sunpriya Kaur Bhatia