"Math.max && Math.min"
힙(Heap)
힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)
위키백과에 서술된 힙에 대한 설명 입니다. 힙의 특징 2 가지를 굵게 처리해보았는데요. 바로 최대값 또는 최소값을 찾기 위한 것이라는 것, 그리고 완전이진트리를 기본으로 한다는 것입니다.
완전이진트리
완전이진트리에 대해 먼저 간략하게 짚어보겠습니다. 이진트리는 모든 노드가 최대 2개의 자식 노드를 갖게 되는 트리입니다. 여기에 완전이라는 표현이 붙게 되면, 마지막 레벨을 제외한 모든 레벨의 노드가 2개의 자식 노드를 다 가지고 있고, 마지막 레벨의 노드는 가장 왼쪽부터 채워진다는 의미입니다.
출처 https://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html
힙의 특징
힙의 특징 중 하나가 완전이진트리라면 또 다른 특징은 최대값 또는 최소값을 빠르게 찾기 위해 고안된 자료구조라는 점입니다.
"A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다."
위키백과는 힙이 가지는 속성을 위와 같이 정리해두었는데요. 이러한 속성에 따라 부모 노드가 자식 노드보다 큰 경우를 '최대 힙', 부모 노드가 자식 노드보다 작은 경우를 '최소 힙' 이라고 합니다.
그러다보니 자식 노드 간에는 정렬이 되지 않는다 하더라도 최소한 root 노드는 언제나 가장 높은 값이거나 가장 낮은 값이 된다는 특징을 가지게 됩니다.
힙에서의 데이터 삽입 및 삭제
데이터 삽입
힙에서 데이터를 삽입할 때는 1. 가장 끝의 노드에 데이터를 삽입한 후, 2. 부모 노드와 삽입한 노드를 서로 비교합니다. 최대 힙인 경우 부모 노드가 더 큰 값이어야 하고, 최소 힙인 경우 부모 노드가 더 작은 값이어야 하죠. 만약 그렇지 않다면 3. 부모 노드와 삽입한 노드의 위치를 바꾸어줍니다. 4. 조건이 맞아 떨어질 때까지 이 작업을 반복합니다.
데이터 삭제
데이터를 삭제할 때는 1. root 노드를 제거하고 가장 마지막 노드를 root 노드의 자리로 올립니다. 2. 새로운 root 노드와 자식 노드를 비교합니다. 3. 최대 힙 또는 최소 힙의 조건에 맞지 않을 경우 자식 노드와 교환합니다. 4. 조건이 맞아 떨어질 때까지 이 작업을 반복합니다.
단 삭제할 때에는 추가적인 조건이 필요합니다. 가장 아래의 레벨에서부터 시작해서 올라가는 경우에는 부모 노드 하나와 비교하면 끝이 나지만, 삭제시에는 root 에서부터 아래로 내려가게 되어 비교 대상이 2개가 되기 때문이죠. 만약 둘 다 부모 노드보다 크거나, 둘 다 작다면 서로를 비교해서 조건에 더 잘 부합하는 것과 자리를 교환해야 합니다.
보다 더 잘 정리된 자료를 나무위키에서 확인하실 수 있습니다. 이 글과 나무위키를 함께 읽어보시면 충분히 이해가 될 거라고 생각합니다. (사실 그냥 나무위키를 보시는 편이..)
