#include<bits/stdc++.h>
using namespace std;
// define maximum capacity of heap
#define N 100
// Data structure for Max Heap
struct PriorityQueue
{
private:
// array of size N to store heap elements
int A[N];
// stores current size of heap data
unsigned size = 0;
// return parent of A[i]
// don't call this function if it is already a root node
int PARENT(int i)
{
return (i - 1) / 2;
}
// return left child of A[i]
int LEFT(int i)
{
return (2 * i + 1);
}
// return right child of A[i]
int RIGHT(int i)
{
return (2 * i + 2);
}
// Recursive Heapify-down algorithm
// the node at index i and its two direct children
// violates the heap property
void heapify_down(int i)
{
// get left and right child of node at index i
unsigned left = LEFT(i);
unsigned right = RIGHT(i);
int largest = i;
// compare A[i] with its left and right child
// and find largest value
if (left < size && A[left] > A[i])
largest = left;
if (right < size && A[right] > A[largest])
largest = right;
// swap with child having greater value and
// call heapify-down on the child
if (largest != i) {
swap(A[i], A[largest]);
heapify_down(largest);
}
}
// Recursive Heapify-up algorithm
void heapify_up(int i)
{
// check if node at index i and its parent violates
// the heap property
if (i && A[PARENT(i)] < A[i])
{
// swap the two if heap property is violated
swap(A[i], A[PARENT(i)]);
// call Heapify-up on the parent
heapify_up(PARENT(i));
}
}
public:
// return size of the heap
unsigned heapSize()
{
return size;
}
// function to check if heap is empty or not
int empty()
{
return size == 0;
}
// insert key into the heap
void push(int key)
{
// if heap is full, return
if (size == N) {
printf("Heap overflow\n");
return;
}
// insert the new element to the end of the array
int i = size;
A[i] = key;
// call heapify-up procedure
heapify_up(i);
// increment size of heap by 1
size++;
}
// function to remove element with highest priority (present at root)
void pop()
{
// if heap has no elements
if (size <= 0) {
printf("Heap underflow\n");
return;
}
// replace the root of the heap with the last element
// of the array
A[0] = A[size-1];
// decrease heap size by 1
size--;
// call heapify-down on root node
heapify_down(0);
}
// function to return element with highest priority (present at root)
int top()
{
// if heap has no elements
if (size <= 0)
{
printf("Heap underflow\n");
return -1;
}
// else return the root (first) element
return A[0];
}
};
int main(void)
{
PriorityQueue pq;
// Note - Priority is decided by element's value
pq.push(3);
pq.push(2);
pq.push(15);
printf("Size is %d\n", pq.heapSize());
printf("%d ", pq.top());
pq.pop();
printf("%d ", pq.top());
pq.pop();
pq.push(5);
pq.push(4);
pq.push(45);
printf("Size is %d\n", pq.heapSize());
printf("%d ", pq.top());
pq.pop();
printf("%d ", pq.top());
pq.pop();
printf("%d ", pq.top());
pq.pop();
printf("%d ", pq.top());
pq.pop();
if (pq.empty())
printf("\nHeap is empty\n");
pq.top(); // top operation on an empty heap
pq.pop(); // pop operation on an empty heap
return 0;
}