[c++] 힙(Heap)
힙은 우선순위 큐나 힙 정렬과 같이 자료의 우선 순위를 관리하는 데 주로 사용됩니다.
힙의 구조
힙은 일반적으로 배열로 구현되며, 부모 노드와 자식 노드 간에 특정한 순서를 유지하면서 데이터를 저장합니다. 우선 순위 큐의 경우, 루트 노드가 우선순위가 가장 높은 값을 갖습니다.
힙의 주요 연산
힙은 주로 다음과 같은 연산을 지원합니다.
- 삽입(Insertion): 새로운 요소를 힙에 추가하고, 특정한 순서로 재정렬하여 힙 속성을 유지합니다.
- 삭제(Deletion): 우선 순위가 가장 높은 요소를 제거하고, 힙을 다시 재정렬하여 힙 속성을 유지합니다.
힙의 종류
힙은 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나뉩니다.
- 최대 힙: 각 노드의 값이 해당 자식 노드의 값보다 크거나 같은 힙 구조
- 최소 힙: 각 노드의 값이 해당 자식 노드의 값보다 작거나 같은 힙 구조
힙은 효율적인 우선 순위 큐를 구현하는 데 사용되며, 다양한 응용 프로그램에서 유용하게 활용됩니다.