Heap과 Priority Queue의 차이, 그리고 Abstract Data Type이란 무엇인가

 얼마 전까지만 해도 나도 헷갈렸던 부분이다.

 일단 배경지식이 어느 정도 필요하다. C++에서 스택(std::stack)은 어떻게 구현되어 있을까? std::vector 구현체처럼 그냥 공간을 뭉탱이로 할당해 놓고 공간 부족해지면 늘려서 할당하고 그런 식으로 구현되어 있지 않을까? 대부분의 자료 구조 강의에서도 stack을 그런 식으로 구현하니 말이다. 하지만 실제로는 이렇게 생겼다.

 

이게 뭐람

 왜 이렇게 끔찍하게 생긴 방식으로 구현되었을까? 사실 이 구현은 양쪽에서 모두 원소를 뽑아 쓸 수 있는 큐인 deque(double-ended queue)에서 한쪽을 막아놓는다는 이상한(?) 방식이다. std::queue 구현도 마찬가지다. 대체 왜 그냥 자료 구조 교과서에 있는 스택을 안 만들고 굳이 deque를 만든 다음 한쪽을 막는 오버테크놀로지로 구현되어 있는지는 나도 감이 잘 안 잡힌다. 그냥 나 같은 빡대가리보다 STL 헤더 짜는 사람이 훨씬 더 똑똑하겠지 하는 생각뿐이다.

 다만 여기서 주목해야 할 부분은, 이런 것도 스택이라고 부를 수 있고 큐라고 부를 수 있다는 것이다. 큐 구현 하면 보통 메모리 뭉탱이로 할당해 놓고 포인터를 움직이거나, 아니면 rotating queue 방식으로 구현하거나 이런 것들을 자료 구조 시간에 배운다. 하지만 C++의 std::queue도 엄연한 큐다. 이런 식으로 생각해 보면, first-in first-out을 지키는 모든 자료구조는 내부가 연결 리스트 모양으로 되어 있든 동적 할당으로 되어 있든 우주전함 모양으로 되어 있든 first-in first-out이 O(1)이기만 하면 다 큐라고 생각할 수가 있다. 

 문제는 여기서 터진다. C++의 queue는 큐긴 하지만 rotating queue는 아니다. rotating queue는 rotating queue의 구현 방식을 따라야만 그렇게 부를 수가 있다. 여기서 용어의 중복된 뜻이 생긴다. queue는 구현과 상관없이 push 연산, pop 연산, 그리고 그 시간복잡도로만 정의되는데, 비슷한 이름을 쓰는 rotating queue는 정해진 방식을 따르는 어떤 구현체를 의미한다. 그래서 사람들이 abstract data structure와 data structure 구현체의 차이를 잘 인지하지 못하는 것이다.

 

 Heap과 Priority Queue의 차이도 사실 그 차이다. PQ는 abstract data structure고 Heap은 PQ의 구현체이다. 물론 PQ를 다른 방식으로 구현할 수도 있다. 예컨대 레드-블랙 트리는 힙이 할 수 있는 push 연산과 pop 연산을 다 할 수 있다. 시간이 상수 배만큼 느려질 뿐이다.

 

 C++의 policy 디자인 패턴은 템플릿을 이용해서 자료형의 생긴 모습은 그대로 두되 내부 구현체만 바꿔 끼우는 재미난 일을 할 수 있다. 예컨대 std::priority_queue<int>의 진짜 이름은 std::priority_queue<int, std::vector<int>, std::less<>>인데, 여기서 std::vector<int>는 std::priority_queue의 내부 저장소로 std::vector를 써 달라는 의미다. 내부 저장소로 다른 저장소를 쓰면 PQ의 구현도 달라진다! 이렇게 policy 디자인 패턴을 잘 사용하면 서로 다른 클래스를 조립하듯이 프로그래밍하면서 코드 재사용성을 눈에 띄게 높일 수 있다. 위의 STL 사례에서도 보았듯이, 이런 패턴의 장점은 자신이 작성한 코드를 사용자가 어떻게 활용할지 알기 어려운 라이브러리를 제작할 때 특히 돋보이는 것 같다.

 

 하지만 내가 갖고 있는 PQ가 std::priority_queue<int>든 std::priority_queue<int, naega_mandun::vector<int>, neorul_wihe_guwotji>든 이것들은 동일한 인터페이스를 제공할 것이다. 잘 알려졌다시피 동일한 인터페이스는 코드 재사용성과 통일성을 증가시키는 데 긍정적인 영향을 준다. abstract data structure라는 개념이 존재하는 이유이다.