**Priority Queue : **
Priority queue is an abstract data type similar to a regular queue or stack data structure in which each element additionally has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.
Main Concepts/Problems To learn in priority queue :
- Implementation of Heap(Min Heap & Max Heap) .
- Inplace Heap Sort .
- Kth Smallest Element / Kth Largest Element .
- K largest & Smallest Elements in array .
- K sorted array .
- Top K frequent Numbers .
- Frequency sort .
- K Closest points to origin .
- K Closest Numbers .
- Connect ropes to minimize the cost ( GFG ) .
- Merge K sorted Arrays (Important) .
- Merge K sorted Linked Lists (Important) .
- Running Median (Important) .
- Check if Binary Tree is a Heap .
- Kth largest Sum Contiguous sub array .
Below i am attaching some code snippets of the above problems.
1 . Min heap Implementation
class PriorityQueue {
private:
vector<int> pq;
public:
PriorityQueue() {
}
bool isEmpty() {
return pq.size() == 0;
}
int getSize() {
return pq.size();
}
void insert(int elem) {
pq.push_back(elem);
int childIndex = pq.size() - 1;
while(childIndex > 0) {
int parentIndex = (childIndex - 1)/2;
if(pq[parentIndex] > pq[childIndex]) {
swap(pq[parentIndex],pq[childIndex]);
}
else {
break;
}
childIndex = parentIndex;
}
}
int removeMin() {
if(pq.size() == 0) {
return -1;
}
int minVal = pq[0];
int size = pq.size();
swap(pq[0],pq[size - 1]);
pq.pop_back();
int parentIndex = 0;
int leftChildIndex = 2 * parentIndex + 1;
int rightChildIndex = 2 * parentIndex + 2;
int minIndex = 0;
while(leftChildIndex < pq.size()) {
if(pq[leftChildIndex] < pq[parentIndex]) {
minIndex = leftChildIndex;
}
if(rightChildIndex < pq.size() && pq[rightChildIndex] < pq[minIndex]) {
minIndex = rightChildIndex;
}
if(minIndex == parentIndex) {
break;
}
swap(pq[minIndex], pq[parentIndex]);
parentIndex = minIndex;
leftChildIndex = 2 * parentIndex + 1;
rightChildIndex = 2 * parentIndex + 2;
}
return minVal;
}
};Max heap Implementation will also be similar to this.
2 . Inplace Heap Sort
#include<bits/stdc++.h>
using namespace std;
int32_t main() {
int n;
cin >> n;
int *pq = new int[n];
for(int i = 0; i < n; i++) {
cin >> pq[i];
}
// HEAP SORT
// If we use MIN HEAP then the array will be sorted in descending order and viceversa
// There are 2 steps in Heap sort
// 1. Heapify the given array
// 2. Use remove min function to sort the elements
// Step1
for(int i = 1; i < n; i++) {
int childIndex = i;
while(childIndex > 0) {
int parentIndex = (childIndex - 1)/2;
if(pq[parentIndex] > pq[childIndex]) {
swap(pq[parentIndex], pq[childIndex]);
}
else {
break;
}
childIndex = parentIndex;
}
}
// Step2
int size = n;
while(size > 1) {
swap(pq[0], pq[size - 1]);
size--;
int parentIndex = 0;
int leftChildIndex = 2 * parentIndex + 1;
int rightChildIndex = 2 * parentIndex + 2;
int minIndex = 0;
while(leftChildIndex < size) {
if(pq[minIndex] > pq[leftChildIndex]) {
minIndex = leftChildIndex;
}
if(rightChildIndex < size && pq[minIndex] > pq[rightChildIndex]) {
minIndex = rightChildIndex;
}
if(parentIndex == minIndex) {
break;
}
swap(pq[parentIndex], pq[minIndex]);
parentIndex = minIndex;
leftChildIndex = 2 * parentIndex + 1;
rightChildIndex = 2 * parentIndex + 2;
}
}
// Sorted array
for(int i = 0; i < n;i++) {
cout << pq[i] << " ";
}
}Tip : In question if they ask to find kth smallest element we have to use MAX HEAP and if they ask to find kth largest element we have to use MIN HEAP
3 . Kth smallest element
int kthSmallestElement(int *arr,int n,int k) {
// Here we want smallest so we have to use MAX HEAP, default priority queue is max heap
priority_queue<int> pq;
for(int i = 0; i < n; i++) {
pq.push(arr[i]);
if(i >= k) {
pq.pop(); // we only want k elements in the priority queue at any time
}
}
return pq.top();
}Kth largest element
int kthLargestElement(int *arr,int n,int k) {
// Here we want largest so we have to use MIN HEAP.
priority_queue<int, vector<int>, greater<int>> pq;
for(int i = 0; i < n; i++) {
pq.push(arr[i]);
if(i >= k) {
pq.pop(); // we only want k elements in the priority queue at any time
}
}
return pq.top();
}4 . K Smallest Elements
vector<int> ksmallestElements(int *arr,int n,int k) {
priority_queue<int> pq;
for(int i = 0; i < n; i++) {
pq.push(arr[i]);
if(i >= k) {
pq.pop();
}
}
vector<int> ans;
while(!pq.empty()) {
ans.push_back(pq.top());
pq.pop();
}
return ans;
}5 . K sorted array
vector<int> sortTheKSortedArray(int *arr,int n,int k) {
vector<int> ans;
priority_queue<int, vector<int>, greater<int>> pq;
for(int i = 0; i < n; i++) {
pq.push(arr[i]);
if(i >= k) {
ans.push_back(pq.top());
pq.pop();
}
}
while(!pq.empty()) {
ans.push_back(pq.top());
pq.pop();
}
return ans;
}6 . Top K Frequent Elements
typedef pair<int,int> pii;
class Solution {
public:
struct compare {
bool operator()(pair<int,int> p1, pair<int,int> p2) {
return p1.second > p2.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
map<int,int> m;
vector<pair<int,int>> v;
for(int i=0;i<nums.size();i++) {
m[nums[i]]++;
}
priority_queue<pii, vector<pii>, compare> pq;
int cnt = 0;
for(auto it : m) {
pq.push({it.first,it.second});
cnt++;
if(cnt > k) {
pq.pop();
}
}
vector<int> ans;
while(!pq.empty()) {
ans.push_back(pq.top().first);
pq.pop();
}
return ans;
}
};7 . Frequency sort can also be solved using the same logic used for "Top k frequent Elements"
8 . K closest points to origin
typedef pair<vector<int>, double> pvi;
class Solution {
public:
struct compare {
bool operator()(pvi p1,pvi p2) {
return p1.second < p2.second;
}
};
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
priority_queue<pvi, vector<pvi>, compare> pq;
for(int i = 0; i < k; i++) {
double dist=sqrt( points[i][0]*points[i][0] + points[i][1]*points[i][1] );
pq.push({points[i],dist});
}
for(int i = k; i < points.size(); i++) {
double dist=sqrt( points[i][0]*points[i][0] + points[i][1]*points[i][1] );
if(dist < pq.top().second) {
pq.pop();
pq.push({points[i],dist});
}
}
vector<vector<int>> ans;
while(!pq.empty()) {
ans.push_back(pq.top().first);
pq.pop();
}
return ans;
}
};9 . K closest Elements
class Solution {
public:
struct compare {
bool operator()(pair<int,int> p1, pair<int,int> p2) {
if(p1.second == p2.second) {
return p1.first < p2.first;
}
return p1.second < p2.second;
}
};
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
priority_queue<pair<int,int> , vector<pair<int,int>> , compare> pq;
for(int i = 0; i < arr.size(); i++) {
pq.push({arr[i], abs(arr[i] - x)});
if(i >= k) {
pq.pop();
}
}
vector<int> ans ;
while(!pq.empty()) {
ans.push_back(pq.top().first);
pq.pop();
}
sort(ans.begin(), ans.end());
return ans;
}
};11 . Merge K sorted Arrays
#include<bits/stdc++.h>
using namespace std;
typedef pair<pair<int,int>, int> ppi;
struct compare {
bool operator()(ppi p1, ppi p2) {
return p1.second > p2.second;
}
};
vector<int> mergeKSortedArrays(vector<vector<int>*> input) {
int n = input.size();
priority_queue<ppi, vector<ppi>, compare> pq;
for(int i = 0; i < n; i++) {
pq.push({ {i,0}, input[i]->at(0) });
}
vector<int> ans;
while(!pq.empty()) {
pair<pair<int,int>,int> curr = pq.top();
ans.push_back(curr.second);
pq.pop();
if(curr.first.second != input[curr.first.first]->size() - 1) {
int nextRow = curr.first.first;
int nextCol = curr.first.second + 1;
pq.push( { {nextRow,nextCol}, input[nextRow]->at(nextCol) } );
}
}
return ans;
}12 . Merge K sorted Linked Lists
class Solution {
public:
struct compare {
bool operator()(ppi p1, ppi p2) {
return p1.second > p2.second ;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ppi, vector<ppi>, compare> pq;
for(int i = 0; i < lists.size(); i++) {
if(lists[i] != NULL) {
pq.push( {lists[i] ,lists[i] -> val});
}
}
ListNode* finalHead = NULL;
ListNode* finalTail = NULL;
while(!pq.empty()) {
ppi curr = pq.top();
ListNode* newNode = new ListNode(curr.second);
if(finalHead == NULL) {
finalHead = newNode;
finalTail = newNode;
}
else {
finalTail -> next = newNode;
}
finalTail = newNode;
pq.pop();
if(curr.first -> next != NULL) {
pq.push({curr.first -> next , curr.first -> next ->val });
}
}
return finalHead;
}
};13 . Running Median in a Stream
#include<bits/stdc++.h>
void printRunningMedian(int arr[], int n){
if(n == 0) {
return;
}
priority_queue<int> maxH;
priority_queue<int, vector<int>, greater<int>> minH;
maxH.push(arr[0]);
cout << arr[0] << " ";
for(int i = 1; i < n; i++) {
if(arr[i] < maxH.top()) {
maxH.push(arr[i]);
}
else {
minH.push(arr[i]);
}
if(maxH.size() > minH.size() && abs(maxH.size() - minH.size()) > 1) {
int elem = maxH.top();
maxH.pop();
minH.push(elem);
}
else if(maxH.size() < minH.size() && abs(maxH.size() - minH.size()) > 1) {
int elem = minH.top();
minH.pop();
maxH.push(elem);
}
if( (maxH.size() + minH.size()) % 2 == 0) {
//cout << maxH.top() << " " << minH.top() << endl;
cout << (maxH.top() + minH.top())/2 << " ";
}
else if(maxH.size() > minH.size()) {
cout << maxH.top() << " ";
}
else {
cout << minH.top() << " ";
}
}
}14 . Check Binary Tree is a Heap
/* For doing this question we have to check two properties
1. Completeness of a Binary Tree .
2. Heap order property (
Root value should be less than left child value and right child value - For Min Heap,
Root value should be greater than left child value and right child value - For Max Heap )
*/ Please suggest me some more problems to practice in Heaps.
Comments (6)