힙(heap) 트리
최종 수정 : 25.1.2
힙(heap) 트리
1. 정의와 종류
힙(heap)는 여러 개의 값 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있도록 구성된 자료구조이다.
최대 힙(max heap)
☞ 키값이 가장 큰 노드를 찾기 위한 완전 이진 트리이며, 부노드의 키값은 자노드의 키값보다 항상 이상( ≥ )이다. 따라서 루트는 키값 중 가장 큰 노드가 된다.
최소 힙(min heap)
☞ 키값이 가장 작은 노드를 찾기 위한 완전 이진 트리로 부노드의 키값이 자노드의 킷값보다 항상 이하( ≤ )이다. 즉, 루트는 키값 중 가장 작은 값을 가진다.
이러한 힙은 최댓값이나 최솟값을 루트로 올려 빠르게 검색할 수 있는 트리로, 이는 정렬에서 사용된다. 이를 힙 정렬이라 한다.
2. 우선순위 큐
일반적인 큐는 선입 선출(FIFO)의 원칙에 의해 먼저 들어온 데이터가 먼저 나가게 된다. 반면에 우선순위 큐는 원소 간의 우선순위를 미리 정하여 우선순위가 높은 데이터가 먼저 나가게 된다. 우선순위 큐는 운영체제의 작업 스케줄링이나 수치 해석적인 계산들에 사용된다.
최소 우선순위 큐
☞ 가장 우선순위가 낮은 요소를 먼저 삭제한다.
최대 우선순위 큐
☞ 가장 우선순위가 높은 요소를 먼저 삭제하는 큐이다.
우선순위 큐를 구현하는 방법에는 배열이나 연결 리스트를 이용하는 방법과 힙을 이용하여 구현하는 방법이 있다.
1) 배열을 이용하여 구현
각 배열읭 원소들을 우선순위에 따라 오름차순으로 정렬하여 가장 우선순위가 큰 레코드는 항상 배열의 마지막에 위치하는 방법이다. 삭제하는 연산은 항상 마지막 레코드에 대하여 반환함으로 시간 복잡도는 O(1)이다.
2) 연결 리스트로 표현
정렬이 안 된 배열에 대해서는 새로운 레코드를 무조건 배열 끝에 삽입하므로 삽입에 대한 효율은 O(1)이다. 배열과 달리 우선순위를 기준으로 내림차순 정렬한다. 우선순위가 가장 높은 레코드를 헤드 포인터가 직접 가리키도록 하고, 삭제 연산이 요구되면 헤드 포인터가 가리키는 첫 원소를 삭제 반환한다. 배열로 표현된 우선순위 큐와 다르게 삭제 연산을 위해서 이동하는 시간이 없다.
3) 힙을 이용하는 방법
우선순위 큐를 구현하기 위해 우선순위가 부여된 레코드들을 최대 힙으로 구성하여 삭제 연산을 진행할 경우는 루트를 삭제하여 반환하는 과정을 반복한다.
3. 최대 힙의 삽입
최대 힙에서의 원소의 삽입은 이미 구성된 완전 이진 트리를 유지하면서 새로 삽입되는 노드를 임시로 저장한 후, 삽입된 원소와 이미 구성된 완전 이진 트리와의 크기 관계를 비교하여 원소 이동을 통해 다시 최대 힙으로 된 완전 이진 트리를 생성한다. 이동은 현재 부노드의 키값과 삽입하는 원소의 크기를 비교하여 부노드가 이상( ≥ )이라는 조건을 만족하지 않으면 서로 값을 교환하고, 교환된 자노드는 다시 상위 부노드와 크기 관계를 비교 반복 수행한다.
4. 최대 힙의 삭제
최대 힙에서의 원소 삭제 연산은 루트를 삭제 반환한 후에도 최대 힙으로 구성된 완전 이진 트리로 재구성하는 부가적인 작업이 필요하다.
참고
독학사 교재