[자료구조] 최소힙, 최대힙

최소힙을 이해하기 위해서는 완전이진트리 개념을 먼저 알아야합니다.

완전이진트리(Complete Binary Tree)

완전이진트리는 각 노드가 최대 2개의 자식 노드를 갖는 트리 구조로써 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 합니다. 또한, 마지막 레벨 노드는 왼쪽 자식 노드만 가지고 있거나, 왼쪽,오른쪽 자식 노드를 모두 가지고 있어야 하며, 노드를 삽입할 때, 최하단의 왼쪽 자식 노드로 삽입해야 합니다.

왼쪽에 보이는 이진 트리는 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있고, 마지막 레벨 노드는 왼쪽 자식 노드만 가지고 있거나, 왼쪽, 오른쪽 자식 노드를 모두 가지고 있기 때문에 완전이진트리가 맞습니다.

반면에, 오른쪽 이진 트리는 3의 자식 노드가 오른쪽 자식 노드밖에 없기 때문에 완전이진트리가 아닙니다.

최소힙?

완전이진트리로 구현된 자료구조이며, 모든 노드의 부모 노드가 자식 노드보다 작은 값을 가지는 트리입니다. 결과적으로 최소힙의 Root 노드에는 전체 트리의 최솟값이 저장되어 있습니다.

예를들어 4,3,2,1,5,6,7 순으로 입력되어 최소힙에 삽입된다면 아래와 같이 구성 됩니다.

모든 노드에 대하여 부모 노드는 자식 노드보다 작은 값을 가진다는 조건을 만족하죠?
그리고, 루트 노드에는 모든 값들 중 최솟값이 저장되어 있습니다.

그렇다면, 최소힙에서 어떤 방식으로 노드가 삽입 되고, 삭제되길래 이런 결과가 나오는지 자세하게 알아보겠습니다.

처음에 5를 최소힙에 삽입하게 되면, 루트 노드에 삽입되게 됩니다.

루트 노드 단 하나만 존재하기 때문에 자식 노드는 없겠죠.
이 상태에서 3이 왼쪽 자식 노드로 삽입되면,

이렇게 간선(Edge)를 통해 왼쪽 자식 노드와 부모 노드를 연결합니다.
그런데, 이 형태가 최소힙의 형태인가요?
최소힙은 부모 노드가 자식 노드보다 값이 작아야한다고 했었죠?? 이렇게 부모 노드보다 자식 노드가 작은 경우에 두 노드를 Swap 합니다.

이렇게 최소힙에 값을 삽입할 때마다 부모 노드와 자식 노드의 값을 비교해서 자식 노드의 값이 더 작으면, swap하는 것을 업힙(up heap)이라고 합니다.

마찬가지로 2가 삽입되었을 때에도 부모 노드인 3이 오른쪽 자식 노드인 2보다 크기 때문에 swap합니다.

4가 삽입 되었을 때에도 마찬가지 입니다. 5가 4보다 크죠? swap 합니다.

swap을 하고 봤을 때, 3은 4보다 작기 때문에 swap을 더 하지 않아도 최소힙의 형태를 갖습니다.
최소힙은 이와 같은 방식으로 값을 추가하고, 4->3->2->1->5->6->7 순서로 값을 삽입했을 때, 결론적으로 아래와 같은 결과가 나오게 됩니다.

그럼 이제 노드를 삭제하는 과정도 알아보겠습니다.
최소힙에서 노드 삭제는 Root노드를 삭제할 수 있습니다.

루트 노드를 삭제하면, 누군가는 그 자리를 채워야겠죠??
이 때, 그 자리를 채우는 녀석은 마지막 레벨의 가장 오른쪽 노드가 채우게 됩니다.

근데 이게 최소힙의 형태인가요???? 아니죠~
그럼 자식 노드와 값을 비교해서 swap을 해줘야겠죠?
자식 노드는 2와 3이 있습니다. 둘 다 7보다 작은데 어떤 녀석과 바꿔줘야할까요?

바로 둘 중에 더 작은 녀석인 2와 swap 해줘야합니다. 이것을 다운힙(down heap)이라고 합니다.

• 노드를 삽입할 때는 부모 노드와 비교해서 삽입한 노드의 값이 더 작으면 부모 노드와 swap해서 상위 노드로 이동했으니까 업 힙(up heap)
• 노드를 삭제할 때는 자식 노드와 비교해서 노드의 값이 더 크면, 자식 노드와 swap해서 하위 노드로 이동했으니까 다운 힙(down heap)

이제 최소힙의 형태가 됐나요??! 아니죠~
그럼 또 다시 자식 노드와 비교해서 자식 노드 중 더 작은 녀석과 swap을 해줘야합니다.

이제 최소힙의 형태인가요???! 네~~
이런식으로 최소힙의 값을 삭제할 수 있습니다.

최대힙

최소힙은 부모 노드가 자식 노드보다 값이 작았다면, 최대힙은 그 반대입니다.
즉, 최대힙은 부모 노드가 자식 노드보다 값이 커야합니다.

따라서 최대힙에 4->3->2->1->5->6->7 순서로 값을 삽입하면,

위와 같은 결과가 나옵니다.
최소힙과는 반대로 루트 노드에 최댓값이 저장되어있습니다.
노드를 삽입, 삭제하는 과정은 최소힙을 이해했다면, 충분히 할 수 있을 것이라고 생각해 생략합니다.

정리

• 완전이진트리 : 마지막 레벨 노드를 제외한 모든 노드는 왼쪽, 오른쪽 자식 노드를 모두 갖는 완전한 형태이면서 마지막 레벨 노드는 왼쪽 자식 노드만 갖거나 왼쪽, 오른쪽 자식 노드를 모두 가져야한다. 그리고, 노드를 삽입할 때 최하단 왼쪽 자식 노드에 삽입한다.

• 최소힙 : 부모 노드가 자식 노드보다 값이 작은 완전이진트리 형태의 자료구조. 루트 노드에 최솟값이 저장되어 있는 것이 특징

• 최대힙 : 부모 노드가 자식 노드보다 값이 큰 완전이진트리 형태의 자료구조. 루트 노드에 최댓값이 저장되어 있는 것이 특징