Heap 자료구조를 설명해보세요
Keyword
완전이진트리,최소힙,최대힙,최소값,최댓값
Script
Heap은 Tree의 구조로 이루어진 자료구조로, 완전이진트리 자료구조입니다. 대표적으로 최소힙과 최대힙이 존재하며, 최소힙은 각 Node에 해당하는 값이 자식 Node의 값보다 작거나 같은 Binary Tree입니다.
이때, root Node는 최소값을 가지기 때문에, 최소값을 찾는데는 항상 O(1) 시간복잡도를 보장합니다. 반면, 추가나 삭제에서는 O(log n)의 시간복잡도를 가집니다.
Additional
Heap을 배열로 구현하기
Heap 자료구조는 완전이진트리로, 배열로 구현하기에 적합하다. 배열의 0-index는 사용하지 않고, 1-index 부터 사용하여, binary tree의 계층구조를 간단한 수식으로 쉽게 탐색할 수 있다.
항상 아직 채워지지 않은 마지막 index를 변수로 가지고 있으면, 새로운 값의 추가와 삭제에 사용할 수 있다.
추가의 경우, 아직 채워지지 않은 마지막 index에 값을 넣고, 부모 노드와 비교한다. 최소힙으로 예시를 들면, 부모 노드보다 작은 값을 가지고 있다면 부모 노드와 자리를 바꾸고 이를 재귀적으로 수행한다.
루트 노드의 삭제의 경우, 먼저 마지막으로 채워진 index에 존재하는 값을 루트 노드로 이동하고, 재귀적으로 다시 자식 노드와 값을 비교하며 위치를 수정한다.
우선순위 큐
우선순위 큐는 먼저 들어온 데이터가 아닌, 높은 우선순위를 가지는 데이터가 먼저 나가는 구조이다. 이는 Heap 자료구조를 사용하면 쉽게 구현할 수 있다.
예를 들어, 최소힙의 경우, 작은 값을 가지는 노드에 높은 우선순위를 부여하는 우선순위 큐에서 사용할 수 있다.
