힙 트리

힙 트리

• 최대 2개의 자식을 갖는 이진트리중 하나이다.

• 부모노드가 가진 값은 항상 자식노드가 가진 값보다 크다. ( 최대 힙, 최소 힙은 반대로 부모노드가 자식 노드보다 작다.)

• 노드 개수를 알면, 트리 구조는 무조건 확정할 수 있다.

• 배열을 이용해서 힙 구조를 바로 표현할 수 있다.

  • i번 노드의 왼쪽 자식은 [(2 * i) + 1] 번 노드이다.
  • i번 노드의 오른쪽 자식은 [(2 * i) + 2] 번 노드이다.
  • i번 노드의 부모는 [(i - 1) / 2] 번 노드이다.

• 힙 트리의 특성상 루트 노드의 값은 트리의 최댓값이다.

template<typename T,typename Container=vector<T>,typename Predicate =less<T>>
class Priority_queue
{
public:
	void push(const T& data)
	{
		// 우선 힙 구조부터 맞춰준다.
		_heap.push_back(data);

		// 도장깨기 시작
		int now = static_cast<int>(_heap.size()) - 1;
		// 루트노드 까지
		while (now > 0)
		{

			int parent = (now - 1) / 2;

			// 부모 노드와 비교해서  greater 크면 /less 작으면 true
			if (_predicate( _heap[now], _heap[parent]))
				break;

			// 데이터 교체
			::swap(_heap[now], _heap[parent]);
			now = parent;

		}
	}

	void pop()
	{
		_heap[0] = _heap.back();
		_heap.pop_back();

		// 도장깨기 시작
		int now = 0;

		while (true)
		{
			int left = now * 2 + 1;
			int right = now * 2 + 2;
			
			// 리프에 도달한 경우
			if (left >= _heap.size())
				break;


			int next = now;

			// 왼쪽과 비교
			if (_predicate(_heap[next], _heap[left]))
				next = left;
			// 둘 중 승자를 오른쪽과 비교
			if (right < _heap.size() && _predicate(_heap[next], _heap[right]))
				next = right;

			// now가 변화가 없다면 적절한 위치에 도달한 것임으로 break
			if (now == next)
				break;

			::swap(_heap[now], _heap[next]);
			now = next;
		}
	}

	T& top()
	{
		return _heap[0];
	}

	bool empty() 
	{
		return _heap.empty();
	}
private:
	Container _heap = {};
	Predicate _predicate = {};
};

• 데이터 추가

  • 이진 트리이므로 우선 정해진 위치(마지막 위치)에 들어가게 된다.

  • 추가된 데이터는 자신의 부모와 비교하여 부모보다 클 경우(최대 힙 기준) 부모와 자리를 바꾸게 된다.

  • 위 연산을 추가된 데이터가 적절한 위치 (부모가 자신보다 큰 위치)로 갈 때 까지 반복한다.

• 데이터 pop()

  • 데이터의 최댓값인 루트 노드가 삭제되고 가장 마지막에 위치한 노드가 루트자리로 옮겨지게 된다.

  • 옮겨진 노드를 적절한 위치로 옮기기 위해서 자신(부모)과 왼쪽 자식노드, 오른쪽 자식노드와 비교하여 셋중 가장 큰 노드(최대 힙 기준)가 부모자리에 위치하게 된다.