/**
	Тестов minHeap за Дийкстра и Прим
	Поддържа extract_min(), decrease_key() и empty().
*/

typedef std::pair<int, int> pr;

class minHeap // minHeap от int с ключове int
{
	int size;

	pr* heap; // node-овете на heap-а са наредени двойки от стойност и индекс 
	int* pos; // къде в heap-а се намира търсеният индекс

	void swap(int i, int j)
	{
		pos[heap[i].second] = j; pos[heap[j].second] = i;
		pr temp = heap[i]; heap[i] = heap[j]; heap[j] = temp;
	}

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

	void heapify(int i)
	{
		int left = 2 * i + 1, right = 2 * i + 2;

		int s = i;
		if (left < size && heap[left].first < heap[s].first) s = left;
		if (right < size && heap[right].first < heap[s].first) s = right;
		if (s != i)
		{
			swap(i, s);
			heapify(s);
		}
	}

public:
	minHeap(int s, int* a) // декларация с масив - използва build_heap
	{
		size = s;
		heap = new pr[s];
		pos = new int[s];

		for (int i = 0; i < s; i++)
		{
			heap[i]=(pr(a[i], i));
			pos[i] = i;
		}

		for (int i = size / 2 - 1; i >= 0; i--) heapify(i); // build_heap
	}
	
	~minHeap()
	{
		delete[] heap;
		delete[] pos;
	}
	
	pr extract_min()
	{
		pr temp = heap[0];
		swap(0, --size);
		heapify(0);
		return temp;
	}

	void decrease_key(int i, int key)
	{
		i = pos[i];
		if (heap[i].first < key) return;
		
		heap[i].first = key;

		while (i>0 && heap[parent(i)] > heap[i])
		{
			swap(parent(i), i);
			i = parent(i);
		}
	}

	bool empty()
	{
		return size == 0;
	}
};