[힙(Heap)] 힙 기반 우선순위큐 구현 (with Heap Sort)

#include <iostream>
#include <vector>
using namespace std;

template<typename T>
class myPriorityQueue {
private:
	// 내부 컨테이너는 vector
	// 힙은 완전이진트리 기반이며,
	// 완전 이진트리는 배열로 표현 가능!
	vector<T> container;

public:
	// push
	void push(const T& data) {
		// (1) 맨 마지막 요소로 추가한다.
		container.push_back(data);
		// (2) 부모와 비교해가며 swap 한다. 
			// => "힙 정렬(Heap Sort)"
		int childIdx = static_cast<int>(container.size()) - 1;
		while (childIdx > 0) {
			int parentIdx = (childIdx - 1) / 2;

			if (container[parentIdx] < container[childIdx]) {
				// 부모보다 크다면 -> swap (최대 힙)
				T temp = container[parentIdx];
				container[parentIdx] = container[childIdx];
				container[childIdx] = temp;

				childIdx = parentIdx;
			}
			else {
				// 부모보다 크지 않다면 -> 정렬 중지
				break;
			}
		}
	}

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

	// pop
	void pop() {
		// (1) 힙의 루트를 제거하고, 맨 끝의 요소로 대체
		container[0] = container[container.size() - 1];
		container.pop_back();

		// (2) 맨 끝 요소로 대체된 루트를 다시 아래 방향으로 향하며
		// 자식 노드와 비교해가며 위치를 찾는다.
		int parentIdx = 0;
		while (parentIdx < container.size()) {
			int left = parentIdx * 2 + 1;
			int right = parentIdx * 2 + 2;

			// 2-1) 자식 노드가 존재하지 않는다면,
			if (left >= container.size()) {
				break;
			}
			// 2-2) 하나의 자식 노드(left)만 존재한다면,
			else if (right >= container.size()) {
				if (container[left] > container[parentIdx]) {
					// swap
					T temp = container[left];
					container[left] = container[parentIdx];
					container[parentIdx] = temp;
				}
				break;
			}
			// 2-3) 두 자식 노드 모두 존재한다면,
			else {
				// 더 큰 자식과 swap 한다
				if (container[left] > container[right]) {
                	if(container[left] > container[parentIdx]) {
						::swap(container[left], container[parentIdx]);
						parentIdx = left;
                    }
                    else
                    	break;
				}
				else {
                	if(container[right] > container[parentIdx]) {
						::swap(container[right], container[parentIdx]);
						parentIdx = right;
                    }
                    else
                    	break;
				}
			}
		}
	}

	// empty
	bool empty() {
		return container.empty();
	}
};

int main() {
	myPriorityQueue<int> pq;

	pq.push(5);
	pq.push(4);
	pq.push(1);
	pq.push(2);
	pq.push(3);
	while (!pq.empty()) {
		cout << pq.top() << endl;
		pq.pop();
	}

	pq.push(100);
	pq.push(300);
	pq.push(400);
	pq.push(200);
	pq.push(500);
	while (!pq.empty()) {
		cout << pq.top() << endl;
		pq.pop();
	}

}