#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

class minHeap
{
private:
	//The actual heap
	vector<double> items;

	//Fast lookup data structure (map)
	//to find items in the heap
	unordered_map<double, int> I;

	int parent(int i)
	{
		return (i - 1) / 2;
	}

	//bubble item at location index
	//up the heap
	void bubbleUp(int index)
	{
		int i = index;
		while (items[i] < items[parent(i)])
		{
			swap(items[i], items[parent(i)]);
			swap(I[items[i]], I[items[parent(i)]]);

			i = parent(i);
		}

	}

public:

	void insert(double x)
	{
		//add item as bottom-left leaf
		items.push_back(x);
		I[x] = items.size() - 1;

		//bubble item up heap
		bubbleUp(items.size()-1);
	}

	void testDisplay()
	{
		for (int i = 0; i < items.size(); i++)
		{
			cout << i << ": " << items[i] << endl;
		}

		cout << "Where is item 16?" << endl;
		cout << "It's at " << I[16] << endl;
		cout << endl;

		for (auto x : I)
		{
			cout << x.first << ":: " << x.second << endl;
		}
	}
};