#pragma once
#include <iostream>
#include <vector>
using namespace std;
class Heap
{
private:
	vector<int> arr;
public:
	void createHeap(vector<int> heap)//노드생성
	{
		arr.push_back(0);
		for (int i = 0; i < heap.size(); i++)
			insert(heap[i]);
	}
	void display()
	{
		if (isEmpty()) cout << "empty";
		for (int i = 1; i < arr.size(); i++) cout << arr[i] << " ";
		cout << endl;
	}
	void insert(int data){
		arr.push_back(data);
		bubbleUp(arr.size()-1);
	}
	void bubbleUp(int pos)
	{
		//왼쪽자식 인덱스 : [부모인덱스*2]
		//오른쪽자식 인덱스 : [(부모인덱스*2)+1]
		//부모 인덱스 : (자식인덱스/2)
		int parent = pos / 2;
		int child = pos;
		while (child > 0 && arr[child] < arr[parent])
		{
			swap(arr[child],arr[parent]);
			child = parent;
			parent /= 2;
		}
	}
	int extractMin()
	{
		int min = arr[1], max = arr.back();
		arr.pop_back();
		if (min == max) return min;
		arr[1] = max;
		sinkDown(1);
		return min;
	}
	void sinkDown(int pos)
	{
		//왼쪽자식 인덱스 : [부모인덱스*2]
		//오른쪽자식 인덱스 : [(부모인덱스*2)+1]
		//부모 인덱스 : (자식인덱스/2)
		int current = pos;
		int leftIdx = pos * 2, rightIdx = (pos * 2) + 1;
		if (leftIdx < arr.size() && rightIdx < arr.size())
		{
			if (arr[leftIdx] < arr[rightIdx]) current = leftIdx;
			else current = rightIdx;
		}
		//자식이 하나만 있을때
		if (leftIdx < arr.size())
			if (arr[leftIdx] < arr[current]) swap(arr[leftIdx], arr[current]);
		if (rightIdx < arr.size())
			if (arr[rightIdx] < arr[current]) swap(arr[rightIdx], arr[current]);

		if (current != pos){
			swap(arr[current], arr[pos]);
			pos = current;
			sinkDown(pos);
		}
	}
	void swap(int& a, int& b){ int t = a; a = b; b = t; }
	bool isEmpty(){ return (arr.size()-1 == 0) ? true : false; }
	int heapSize(){ return arr.size() - 1; }
};