[자료구조] Priority Queue를 통한 Heap의 구현

0. 자료구조와 알고리즘을 공부하다 보면,

자주 등장하는 개념인 Priority Queue와 Heap.

이번 글에서는 이 두 개념이 각각 무엇인지, 그리고 서로 어떤 관계인지 정리해보려 한다.

 

1. Priority Queue (우선순위 큐)

Priority Queue는 "들어간 순서에 관계없이 우선순위가 가장 높은 데이터를 가장 먼저 꺼낸다"라는

동작 규칙을 정의한 개념이다.

비슷한 개념으로는 리스트, 스택, 큐가 있다.

 

2. Heap (힙)

Heap은 Priority Queue를 실제로 컴퓨터 상에서 구현하기 위해 정의된, 완전 이진트리 기반 자료구조이다.

부모 노드의 값이 항상 자식 노드의 값보다 작거나 같은 Heap을 Min Heap,

부모 노드의 값이 항상 자식 노드의 값보다 크거나 같은 Heap을 Max Heap이라고 한다.

예를 들어, 값이 클수록 우선순위가 높은 Priority Queue는 Max Heap으로 구현할 수 있다.

 

3. 따라서 Heap 외에 배열, Linked List 같은 다른 자료구조로도 Priority Queue를 구현할 수 있다.

하지만 Heap으로 구현했을 때 가장 효율적이다. (삽입과 삭제가 모두 O(logN)))

 

4. 따라서 가장 작은 값이나 큰 값을 빠르게 꺼내야 하는 상황이 나오면,

개념적으로는 Priority Queue,

구현하기 위해서는 C++의 priority_queue나 make_heap 기능을 활용하면 된다.