[알고리즘] 힙, 우선순위 큐

Heap

이진트리 자료 구조로서 min-heap, max-heap이 있다.

1. push

트리의 맨 끝에 원소가 추가된다. 해당 힙은 min-heap이므로 추가된 원소를 부모노드와 비교하여 올바른 위치로 보내야한다.

4는 부모노드인 6보다 작으므로 6과 자리를 바꿔준다.

2. pop

힙에서 pop을 하면 힙의 최상위 노드가 pop된다.

빠진 최상위노드 자리에 맨 마지막 노드가 들어가게 된다.

이후 최상위노드부터 자식노드와 값을 비교해가며 점점 아래로 내려간다. 최상위노드 6은 자식노드 3,4 보다 값이 크므로 자리를 바꿔야한다. 이 때 자식노드 둘 중 더 작은 값인 3과 6을 자리를 바꾼다.

6이 1번 자리로 내려왔으면 다시 또 자식노드와 비교를 한다. 자식노드 5보다 6이 더 크므로 5와 6의 자리를 바꾼다.

이렇게 min-heap 형태까지 다 만들었으면 pop과정이 끝난다.

우선순위 큐

힙을 이용한 대표적인 자료구조가 우선순위 큐이다. 우선순위큐는 우선순위에 맞춰 값이 저장되는 큐로서 꼭 힙으로 구현할 필요는 없지만 힙으로 구현하는 것이 시간복잡도면에서 효율적이다.

우선순위 큐는 일반 큐와는 달리 front 대신 top을 사용한다.

우선순위 큐는 기본적으로 내림차순으로 정렬된다. 즉 max-heap이 기본이므로 pop을 하면 큰 수부터 출력되게 된다.

pair와 함께 우선순위 큐 사용하기

우선순위 큐를 사용할 때 pair의 첫 요소로 우선적으로 정렬하고 첫 요소가 같은 경우 두번째 요소로 정렬하는 방식이다.

#include <queue>

int main(){
	priority_queue<pair<int,int>> temp;
    temp.push(make_pair(3,100));
}