[자료구조] 힙(Heap)

개념

데이터에서 최대값(or 최소값)을 빠르게 찾을 수 있는 완전 이진 트리

• 우선순위가 가장 높은 데이터가 제일 앞(루트)에 위치한다.
• 모든 부모 노드는 자식노드보다 우선순위가 크다.
• 시간복잡도는 O(logN)이므로 삽입/삭제가 매우 빠르다.
• 대표적으로 최소힙(Min Heap), 최대힙(Max Heal)이 있다.
• 최소값이나 최대값을 빨리 찾을 때 유용하다.
• 힙 트리에서는 중복된 값을 허용한다(완전 이진 트리에서는 중복된 값을 허용하지 않는다.)

• 일반적으로 배열로 구현한다.

• 예시) 운영체제에서의 작업스케쥴링

최소 힙(min heap)

• 데이터 중 가장 작은 값이 루트에 위치한다.
• 모든 부모 노드는 자식보다 작거나 같다.
• key(부모 노드) ≤ key(자식 노드)

최대 힙(max heap)

• 데이터 중 가장 큰 값이 루트에 위치한다.
• 모든 부모 노드는 자식보다 크거나 같다.
• key(부모 노드) ≥ key(자식 노드)