Untitled

#include<bits/stdc++.h>
#include "heap.h"
using namespace std;
int main()
{
	long long x=31441;
	
	vector<long long> A;
	for(int i=0;i<10;i++)
	{
		x=x*48271%2147483647;
		A.push_back(x);      // make a vector A
	}
	cout<<"Before sort : ";
	for(auto i:A)
		cout<<i<<' ';
	cout<<"\nAfter sort : ";
	Heap pr(A);
	pr.heapsort();   //sort vector A
} 


#ifndef heap_H
#define heap_H

#include<bits/stdc++.h>
using namespace std;
class Heap
{
	public:
		Heap( vector<long long> );  //construct a heap its elements are in input
		void insert(long long );
		void siftUp(int );
		void siftDown(int);
		long long max();
		long long pop();
		void heapsort();  // sort elements in heap with decreasing order and output it
	private:
		vector<long long> heap;
};
#endif



#include<bits/stdc++.h>
#include"heap.h"
using namespace std;
Heap::Heap(vector<long long> input)
{
	heap=input;
	for(int i=heap.size()-1;i>=0;i--)
		siftDown(i);
}
void Heap::insert(long long key)
{
	heap.push_back(key);
	siftUp(heap.size()-1);
}
void Heap::siftUp(int index)  
{
	while(index>0&&heap[index]>heap[(index-1)/2])
	{
		swap(heap[index],heap[(index-1)/2]);
		index=(index-1)/2;
	}
}
void Heap::siftDown(int index)
{
	while(2*index+1<heap.size())
	{
		int child=2*index+1;
		if(child+1<heap.size()&&heap[child]<heap[child+1])
			child+=1;
		if(heap[index]<heap[child])
		{
			swap(heap[index],heap[child]);
			index=child;
		}
		else
			break;
	}
}
long long Heap::max()
{
	return heap[0];
}
long long Heap::pop()
{
	long long res=heap[0];
	swap(heap[0],heap.back());
	heap.pop_back(); 
	siftDown(0);
	return res;
}
void Heap::heapsort()
{
	Heap *output= new Heap(heap);
	while(output->heap.size())
		cout<<(*output).pop()<<' ';
	cout<<'\n';
	delete output;
}