#include <iostream>
#include <queue> //This contains the STL's efficient implementation of a priority queue using a heap
using namespace std;


/*
In this lab you will implement a data structure that supports
2 primary operations:
	- insert a new item
	- remove and return the smallest item
A data structure that supports these two operations is
called a "priority queue".  There are many ways to
implement a priority queue, with differernt efficiencies
for the two primary operations.  For this lab,
please do not attempt (at least at first) to implement
something fancy (like a heap).  Just use your mind to
do something simple.  Analyze the efficiency of both
insertion and removal for your implementation.
Afterwards, feel free to investigagte "min heaps"
to see a very clever and fast priority queue
implementation.  Feel free to try to implement it.

After implementuing your priority queue, use it to
implement a sorting algorithm (priorityQueueSort).
Analyze the run time of your sorting algorithm.

Next, plug-in the stand template libraries priority queue
(which is implemented with a heap) and compare the speed.

(don't forget to run in release mode)

To get lab credit, finish all of the coding below,
as well as be able to state the run times of
your priority queue operations and sorting algorithm
to the lab TAs.
*/


//What is the big-oh run time of this sorting routine with respect
//to the number of items n?
//How does this compare to bubble sort or selection sort?
void priorityQueueSort(int * numbers, int size)
{
	priorityQueue PQ;

	//Step 1:  insert each item from 'numbers' into PQ.

	//Step 2:  Extract from PQ until PQ is empty, each time placing the extracted item into the numbers array, one after another.

}

//For this part you will need to use the built in priority queue in the STL libary.
//The STL priority_queue is implemented using a "heap".  Feel free to read about this on your own
//to understand why it is so fast.
//The STL priority_queue has the following methods:
// push(x), which adds x to the priority queue (this is like your "insert" method)
// pop(), which removes the highest value item from the priority queue
// top(), which returns the highest value item in the priority queue (but does not remove it).
// Run time:  Inserting 1 item into a min heap takes O(log n) time.  Extracting the biggest takes O(log n).
// Therefore, the run time of this sorting algorithm is O(n log n), and that is why it sorts a billion items so fast.
// Which "fast" sort is better?  Blaze sort (aka quick sort), or heap sort?
void heapSort(int * numbers, int size)
{
	priority_queue<int> PQ;

	//Step 1:  insert each item from 'numbers' into PQ.

	//Step 2:  Extract from PQ until PQ is empty, each time placing the extracted item into the numbers array, one after another.

}


int main()
{
	//Part 1:  Implement a priority queue data structure
	priorityQueue pq;

	pq.insert(59);
	pq.insert(12);
	pq.insert(548);
	pq.insert(45);
	pq.insert(18);
	pq.insert(345);

	cout << "Extracting min: " << pq.extractMin() << endl; //12
	cout << "Extracting min: " << pq.extractMin() << endl; //18
	cout << "Extracting min: " << pq.extractMin() << endl; //45
	cout << "Extracting min: " << pq.extractMin() << endl; //59

	pq.insert(2);
	pq.insert(400);
	pq.insert(600);
	pq.insert(20);


	//2 20 345 400 548 600
	while (!pq.empty())
	{
		cout << "Extracting min: " << pq.extractMin() << endl;
	}


	//Part 2:  create a sorting function that uses your priority queue data structure to sort
	int numbers[] = { 53, 359, 31, 95, 345, 52, 13, 58, 2, 78 };

	priorityQueueSort(numbers, 10);

	for (int i = 0; i < 10; i++)	//should be in sorted order now
		cout << numbers[i] << endl;


	//Part 3:  Implement the "heap sort" algorithm using the STL built in priority queue.
	int size = 10; //replace with 10000000 to stress test and time
	int * bignums = new int[size];
	for (int i = 0; i < size; i++)
		bignums[i] = rand();

	clock_t start, end;

	start = clock();
	heapSort(bignums, size);
	end = clock();

	cout << "Heap sort took: " << end - start << " milleseconds." << endl;

	//comment out display for stress test
	for (int i = 0; i < size; i++)
		cout << bignums[i] << endl;

	return 0;
}