#include <iostream>
#include <vector>
#include <algorithm>
// A class to represent a priority queue
class PriorityQueue {
private:
std::vector<int> data;
// Helper function to heapify the tree
void heapify_up(int index) {
if (index == 0) return; // Base case: root node
int parent = (index - 1) / 2;
if (data[index] > data[parent]) {
std::swap(data[index], data[parent]);
heapify_up(parent);
}
}
void heapify_down(int index) {
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
int largest = index;
if (leftChild < data.size() && data[leftChild] > data[largest]) {
largest = leftChild;
}
if (rightChild < data.size() && data[rightChild] > data[largest]) {
largest = rightChild;
}
if (largest != index) {
std::swap(data[index], data[largest]);
heapify_down(largest);
}
}
public:
// Insert a new element into the priority queue
void push(int value) {
data.push_back(value);
heapify_up(data.size() - 1);
}
// Remove and return the highest priority element
int pop() {
if (data.empty()) {
throw std::out_of_range("Priority Queue is empty");
}
int root = data.front();
data[0] = data.back();
data.pop_back();
heapify_down(0);
return root;
}
// Return the highest priority element without removing it
int top() const {
if (data.empty()) {
throw std::out_of_range("Priority Queue is empty");
}
return data.front();
}
// Check if the priority queue is empty
bool empty() const {
return data.empty();
}
};
int main() {
PriorityQueue pq;
// Inserting elements into the priority queue
pq.push(5);
pq.push(15);
pq.push(10);
pq.push(30);
pq.push(20);
std::cout << "Top element: " << pq.top() << std::endl;
// Removing elements from the priority queue
std::cout << "Popped element: " << pq.pop() << std::endl;
std::cout << "Popped element: " << pq.pop() << std::endl;
std::cout << "Top element after popping: " << pq.top() << std::endl;
return 0;
}
