ㅏ 더미 특별하다 완전 이진 트리 . 힙은 완전한 이진 트리이므로 N 노드에는 로그N 키. 가장 높거나 가장 낮은 우선순위 요소를 제거하는 것이 유용합니다. 일반적으로 다음과 같이 표현됩니다. 정렬 . 힙에는 두 가지 유형이 있습니다.최소 힙
안에 최소 힙 루트 노드에 있는 키는 모든 하위 노드에 있는 키보다 작거나 같아야 합니다. 해당 이진 트리의 모든 하위 트리에 대해 동일한 속성이 반복적으로 true여야 합니다. 최소 힙에서는 루트에 존재하는 최소 키 요소입니다. 아래는 Min Heap의 모든 속성을 만족하는 Binary Tree이다.
최대 힙
안에 최대 힙 루트 노드에 있는 키는 모든 하위 노드에 있는 키보다 크거나 같아야 합니다. 동일한 속성이 있어야 합니다. 재귀적으로 진실 해당 이진 트리의 모든 하위 트리에 대해. Max-Heap에서는 루트에 존재하는 최대 키 요소입니다. 아래는 Max Heap의 속성을 모두 만족하는 Binary Tree이다.
타이프스크립트 화살표 기능
최소 힙과 최대 힙의 차이점
| 최소 힙 | 최대 힙 | |
|---|---|---|
| 1. | 최소 힙에서 루트 노드에 있는 키는 모든 하위 노드에 있는 키보다 작거나 같아야 합니다. | Max-Heap에서 루트 노드에 있는 키는 모든 하위 노드에 있는 키보다 크거나 같아야 합니다. |
| 2. | 최소 힙에서는 루트에 존재하는 최소 키 요소입니다. | Max-Heap에서는 루트에 존재하는 최대 키 요소입니다. |
| 삼. | 최소 힙은 오름차순 우선순위를 사용합니다. | Max-Heap은 내림차순 우선순위를 사용합니다. |
| 4. | Min-Heap을 구성할 때 가장 작은 요소가 우선순위를 갖습니다. | Max-Heap 구성에서는 가장 큰 요소가 우선순위를 갖습니다. |
| 5. | 최소 힙에서는 가장 작은 요소가 힙에서 가장 먼저 팝됩니다. | Max-Heap에서는 가장 큰 요소가 힙에서 가장 먼저 팝됩니다. |
힙의 응용 :
- 힙 정렬 : Heap Sort는 Heap Sort를 사용하는 최고의 정렬 알고리즘 중 하나입니다. 바이너리 힙 에게 배열을 정렬하다 ~에 O(N*로그 N) 시간.
- 우선순위 대기열 : 우선순위 큐는 힙을 사용하여 구현할 수 있습니다. 끼워 넣다() , 삭제() , 추출최대() , 감소키() 의 운영 오(로그 N) 시간.
- Dijkstra의 최단 경로 그리고 Prim의 최소 스패닝 트리 .
최소 힙과 최대 힙의 성능 분석 :
- 최대 또는 최소 요소 가져오기: O(1)
- 최대 힙 또는 최소 힙에 요소 삽입: O(log N)
- 최대 또는 최소 요소 제거: O(log N)