Heap

Heap
힙
힙은 트리의 일종인 '완전 이진 트리'에 두 가지 엄격한 규칙을 추가한 자료구조이다.
- 모양 규칙 (완전 이진 트리): 위에서 아래로, 왼쪽에서 오른쪽으로 빈틈없이 차곡차곡 채워져야 한다.
- 값 규칙 (Heap Property)
  - 최대 힙: 부모의 값은 항상 자식보다 크거나 같아야 함.
  - 최소 힙: 부모의 값은 항상 자식보다 작거나 같아야 함.
최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조로, 각 노드의 키 값이 자식의 키 값보다 작지 않거나(최대 힙) 그 자식의 키 값보다 크지 않은(최소힙) 완전 이진 트리이다.
우선순위가 가장 높은 값을 Root 노드로 만든다.
마지막에 값을 붙이면서 가장 우선순위가 높은 최대 값을 맨 꼭대기로 올린다.
우선순위 큐(Priority Queue) 이다.
활용: 정렬(Heap sort)
stable
힙(Heap)은 완전 이진 트리(Complete Binary Tree)를 기반으로 하며, 보통 이진 힙(Binary Heap) 구조를 사용한다.
힙은 우선순위 큐(Priority Queue) 등의 데이터 구조를 구현하는 데 많이 활용된다.
Heap(힙)은 완전 이진 트리 기반의 우선순위 큐 자료구조로, Min Heap과 Max Heap이 있다.
- Min Heap: 부모 노드가 자식보다 작음 (최소값이 루트)
- Max Heap: 부모 노드가 자식보다 큼 (최대값이 루트)