heap

힙은 트리의 일종이지만 조금 특이하다. 최대힙과 최소 힙이 있다.

최대힙은 완전 트리면서 Root가 모든 경우에 자식들보다 커야한다

최대, 최소값을 찾아내는 연산을 빠르게 하기 위해 완전이진트리를 기본으로 한 자료구조다. 즉, 마지막 레벨을 제외하고 모든 노드가 채워진 이진트리이다.

최대, 최소값을 빠르게 찾기 위해 부모 노드가 다음 특징을 가진다.

1. A가 B의 부모노드면 A,B 의 값들이 대소관계가 성립된다.

   예를 들어, 최대힙이면 부모 > 자식, 최소힙이면 부모 < 자식 이다. (형제간의 대소관계는 정해지지 않는다.)

   • 힙에서는 가장 높은 혹은 가장 낮은 우선 순위를 가진 노드가 항상 root에 온다.

2. 마지막 레벨을 제외한 다른 모든 레벨은 완전 이진트리를 형성한다.

위 두 가지 특징을 항상 유지 해야한다

이를 응용하여 Priority Queue를 구현할 수 있다.

Priority Queue

먼저, 우선순위 큐는 힙이 아니다. 우선순위 큐는 리스트나 맵 처럼 추상적인 개념이다. 마치 리스트는 연결리스트나 배열로 구현될 수 있는 것처럼 우선순위 큐는 힙, 배열, 연결리스트와 같은 다양한 방법으로 구현 가능하다.

힙으로 구현해보자.