What i learned from interviews
Priority queue is a very important data structure which needs to be understood very clearly.
To be clear in it i would always suggest to implement it(as a array).Try and implement a heap and test it. If you cant you can see soultion down but i strongly suggest you try it yourself.
Short explanation on priority queue then implementation:
Priority queues are a type of container adapters, specifically designed such that the first element of the queue is the greatest of all elements in the queue and elements are in non increasing order (hence we can see that each element of the queue has a priority {fixed order}). you search more about priority queue if you dont understand.
Code with heap sort too(edge cases such as if user types string instead of integer it will crash but heap is implemented proplerly....can use getch() to solve that but i thought not to make code complex )
Please upvote if it helped...it gives me lot of motivation
#include<iostream>
#include<vector>
using namespace std;
class heap {
private:
vector<int>v;
int size = 0;
public:
void push(int num) {
v.push_back(num);
int i = v.size() - 1;
int parent = (i - 1) / 2;
if(v[i]>v[parent]) {
while (v[i] > v[parent]) {
int x = v[parent];
v[parent]=v[i];
v[i] = x;
i = parent;
parent = (i - 1) / 2;
}
}
}
void pop() {
if (v.size() == 0)
return;
int x = v[v.size() - 1];
v.pop_back();
if (!v.size())
return;
v[0] = x;
int i = 0;
while (i < v.size()) {
if ((i * 2 + 1 >= v.size() || v[i * 2 + 1] <= v[i]) && (i * 2 + 2 >= v.size() || v[i * 2 + 2] <= v[i])) {
break;
}
int child;
if (i * 2 + 2 >= v.size()) {
child = i * 2 + 1;
}
else
child = v[i * 2 + 1] >= v[i * 2 + 2] ? i * 2 + 1 : i * 2 + 2;
int y = v[i];
v[i] = v[child];
v[child] = y;
}
}
void show() {
for (int i : v)
cout << i << " ";
cout << endl;
}
int top() {
if(v.size())
return v[0];
}
void heap_sort() {
vector<int>x(v.size());
heap h2;
for (int i = 0; i < v.size(); i++)
h2.push(v[i]);
int i = x.size()-1;
while (i >= 0) {
// cout << h2.top()<<" ";
x[i] = h2.top();
h2.pop();
i--;
}
for (int z : x)//can print vector or return it.
cout << z<<" ";
cout << endl;
}
};
int main() {
heap h;
while (1) {
int i;
cout << "1-> pop" << endl << "2-> push" << endl << "3-> show" << endl << "4-> heap sort show" << endl;
cin >> i;
switch(i) {
case 1:
h.pop();
break;
case 2:
cout << "Enter a number ";
int num;
cin >> num;
h.push(num);
break;
case 3:
h.show();
break;
case 4:
h.heap_sort();
break;
default:
cout << "CANT TYPE PROPERLY????????\n";
break;
}
}
}