heap

[CS][Data Structure] 힙 (Heap)

Heap이란? Heap은 이진 트리를 기반으로한 자료구조로 부모 노드와 자식 노드 간의 순서 관계를 유지합니다. Heap은 순서 관계에 따라 최대 힙(Max Heap), 최소 힙(Min Heap) 두 가지로 나눠집니다. 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리입니다. 루트는 항상 최대값이 있습니다. 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리입니다. 루트는 항상 최솟값이 있습니다. Heap의 기본 연산 삽입 : 새로운 원소를 삽입하는 경우 힙의 속성을 유지하기 위해 트리를 재구성하는 과정이 포함되기 때문에 O(logN)의 시간 복잡도를 가집니다. 삭제 : 노드의 값을 삭제하는 경우 힙의 속성을 유지하기 위해 트리를 재구..