이진 힙

이진 힙(binary heap)이란 이진 트리 형태를 취하는 힙 (자료 구조) 자료 구조이다. 이진 힙은 우선순위 큐를 구현하는 일반적인 방법이다. 이진 힙은 1964년 J. W. J. 윌리엄스에 의해 힙 정렬을 위한 자료 구조로 도입되었다.

이진 힙은 두 가지 추가 제약 조건이 있는 이진 트리로 정의된다.

• 모양 속성(shape property): 이진 힙은 완전 이진 트리이다. 즉, 마지막 수준(가장 깊은 수준)을 제외하고 트리의 모든 수준이 완전히 채워지며, 트리의 마지막 수준이 완전하지 않은 경우 해당 수준의 노드는 왼쪽에서 오른쪽으로 채워진다.
• 힙 속성(heap property): 각 노드에 저장된 키는 전체 순서에 따라 해당 노드의 하위 항목에 있는 키보다 크거나 같거나(≥) 작거나 같다(≤).

상위 키가 하위 키보다 크거나 같은(≥) 힙을 최대 힙이라고 한다. (≤)보다 작거나 같은 것을 최소 힙이라고 한다. 효율적인(로그 시간) 알고리즘은 이진 힙에 우선순위 큐를 구현하는 데 필요한 두 가지 작업, 즉 요소를 삽입하고 최소 힙 또는 최대 힙에서 가장 작은 요소 또는 가장 큰 요소를 제거하는 작업으로 알려져 있다. 이진 힙은 암시적 자료 구조로 구현되어 배열에 키를 저장하고 해당 배열 내의 상대 위치를 사용하여 자식-부모 관계를 나타낼 수 있기 때문에 내부 알고리즘인 힙 정렬 정렬 알고리즘에도 일반적으로 사용된다.

같이 보기

• 힙 (자료 구조)
• 힙 정렬