힙은 우선순위 큐를 위해 만들어진 자료구조이다.

먼저 우선순위 큐에 대해서 간략히 알아보자.

우선 순위 큐(Priority Queue)

우선 순위의 개념을 큐에 도입한 자료구조

데이터들이 우선순위를 가지고 있음. 우선 순위가 높은 데이터가 먼저 나감

힙

완전 이진 트리의 일종

여러 값 중 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조

반정렬 상태

• 힙 트리는 중복된 값을 허용한다.
• 이진 탐색 트리는 중복된 값을 허용하지 않는다

힙 종류

1. 최대 힙(max heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
2. 최소 힙(min heap) : 부모 노드의 키 값이 자식 노드의 키 값도가 작거나 같은 완전 이진 트리