[C++] stl priority_queue와 heap

heap이란

heap은 최대값과 최소값을 빠르게 찾기 위해 만들어진 완전이진트리로 구성된 자료구조이다.

 

- maxheap 최대힙

maxheap에서는 임의의 한 트리가 있을 때에 root 노드는 항상 최대값을 갖는다.

 

- minheap 최소힙

minheap에서는 임의의 한 트리가 있을 때에 root 노드는 항상 최소값을 갖는다.

 

둘의 공통점

- 이진 탐색 트리와 같이 작은 값이 왼쪽 큰 값이 오른쪽으로 가지않고 자식이 부모보다 max,min인지의 조건에 따라 크거나 작은지를 확인한다.

 

힙을 이용한다면 최댓값 혹은 최솟값을 O(logN)에 찾을 수 있다. 

 

heap의 삽입 과정

maxheap기준

1. 삽입 값을 힙의 마지막 위치에 넣는다.

2. 부모와의 크기를 비교하여 부모가 더 작다면 자식의 값과 부모의 값을 바꾼다. 

3. 2가 해당되지 않을 때까지 반복한다.

 

heap의 삭제 과정

maxheap기준

1. root의 값을 삭제한다.

2. root의 자리에 힙의 마지막 값을 넣는다.

3. root의 자식들과 비교를 하고 크다면 자식값을 부모값과 바꾼다.

4. 부모값보다 자식값크다면 계속 바꿔준다. (큰 순으로 정렬한다.)

 

priority_queue

- priority_queue는 heap으로 구성되어 있다.

- push시에 기본적으로 내림차순으로 정렬되며 값을 삽입한다.

- pop시에 가장 큰 값이 먼저 나오게 된다.

 

 

 

 

 

참고사이트 : https://hochoon-dev.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-%EC%A0%95%EB%A6%AC-Heap-Priority-Queue-%EA%B0%9C%EB%85%90-c-%EA%B5%AC%ED%98%84

[알고리즘 개념 정리] Heap, Priority Queue 개념 c++ 구현