힙은 힙 속성을 만족하는 특수한 트리 기반 데이터 구조입니다. 힙은 종종 이진 트리로 구현됩니다. 여기서 각 노드의 값은 최대 힙인지 최소 힙인지에 따라 해당 하위 항목의 값보다 크거나 같습니다(또는 작거나 같습니다). 힙 속성은 트리의 루트가 데이터 구조의 최대 또는 최소 요소를 나타내도록 보장합니다.
[힙의 주요 특성]
- 힙 속성:
최대 힙: 각 노드의 값은 해당 하위 노드의 값보다 크거나 같습니다.
최소 힙: 각 노드의 값은 해당 하위 노드의 값보다 작거나 같습니다.
- 바이너리 힙:
일반적으로 각 노드에 최대 2개의 자식이 있는 이진 트리로 구현됩니다.
- 어레이 표현:
힙은 종종 배열로 표현됩니다. 여기서 루트는 인덱스 0에 있고 인덱스 'i'에 있는 모든 노드의 경우 왼쪽 하위 항목은 '2i + 1'에 있고 오른쪽 하위 항목은 '2i + 2'에 있습니다.
- 완전한 이진 트리:
이진 힙은 완전한 이진 트리입니다. 즉, 왼쪽에서 오른쪽으로 채워지는 마지막 수준을 제외하고 모든 수준이 완전히 채워집니다.
- 힙 작업:
삽입:
힙 속성을 유지하면서 힙에 새 요소를 추가합니다.
최대 힙에서는 새 요소가 상위 요소와 비교되어 더 큰 경우 교체됩니다. 이 프로세스는 힙 속성이 복원될 때까지 반복됩니다.
추출(제거):
힙에서 루트 요소(최대 또는 최소)를 제거합니다.
제거 후에는 힙의 마지막 요소가 루트로 이동되고, 힙 속성을 복원하기 위해 "heapify"라는 프로세스가 수행됩니다.
힙파이:
힙 속성을 유지하기 위해 힙의 요소를 재배열합니다.
Heapify는 삽입 또는 추출 후에 힙이 유효한지 확인하는 데 중요합니다.
힙의 응용:
우선순위 대기열:
힙은 일반적으로 우선순위 큐를 구현하는 데 사용됩니다. 여기서 요소는 연관된 우선순위와 함께 삽입되고 가장 높은(또는 가장 낮은) 우선순위를 가진 요소가 효율적으로 추출될 수 있습니다.
힙 정렬:
힙 정렬은 바이너리 힙을 사용하여 정렬된 배열을 만드는 비교 기반 정렬 알고리즘입니다.
그래프 알고리즘:
힙은 그래프에서 최단 경로를 찾는 Dijkstra 알고리즘과 같은 다양한 그래프 알고리즘에 사용됩니다.
작업 예약:
힙은 우선 순위가 높거나 낮은 작업을 먼저 예약해야 하는 작업 예약 알고리즘에 사용됩니다.
힙 유형:
바이너리 최대 힙:
각 노드의 값은 그 자식 노드의 값보다 크거나 같습니다.
이진 최소 힙:
각 노드의 값은 그 자식 노드의 값보다 작거나 같습니다.
D-ary 힙:
각 노드에 최대 d개의 자식이 있는 바이너리 힙의 일반화.
피보나치 힙:
특정 작업에 대해 더 나은 상각 시간 복잡성을 갖춘 고급 힙 구조입니다.
복잡성 분석:
시간 복잡성:
삽입: O(log n)
삭제 : O(log n)
공간 복잡성:
O(n), 여기서 n은 힙의 요소 수입니다.
힙은 우선순위 기반 정렬과 관련된 작업에 효율적인 솔루션을 제공하며 다양한 알고리즘 및 애플리케이션에서 널리 사용됩니다. 특히 바이너리 힙은 기본적이고 다양한 기능을 갖춘 데이터 구조입니다.
