[자료구조] 힙(Heap)

1. 힙(Heap)

완전이진트리를 기본으로 한 자료구조이다.

A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다는 속성을 가지고 있으며 중복값이 허용된다. 힙은 아래의 두 종류로 분류된다.

• 최대 힙(Max heap)
부모노드의 키값이 자식노드의 키값보다 항상 큰 힙
• 최소 힙(Min heap)
부모노드의 키값이 자식노드의 키값보다 항상 작은 힙

키 값의 대소 관계는 부모 노드와 자식 노드 사이에만 성립하며 형제 사이의 대소 관계는 고려하지 않는다. 자식 노드의 최대 개수는 힙의 종류마다 다르나, 최대 자식 노드가 2개인 힙을 이진 힙(binary heap)이라 하며 가장 대중적으로 사용된다.

이러한 힙의 특성을 이용해 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아낼 수 있다.

2. 힙의 구현

힙은 보통 배열로 구현하며 최상위 루트 노드에는 데이터의 최댓값, 혹은 최솟값이 저장된다. 완전이진트리 힙의 부모 노드의 인덱스를 i라고 했을 때, 부모 노드를 기점으로 왼쪽 자식 노드는 2i, 오른쪽 자식 노드는 2(i+1)의 인덱스를 가진다.

삽입

데이터를 삽입할 때, 힙은 다음과 같은 과정을 거친다.

1. 새로 삽입되는 노드를 기존 마지막 노드에 이어서 삽입한다.
2. 새로운 노드를 부모 노드의 값과 비교하여 힙의 성질을 만족할 때까지 교환한다.

최대 힙의 경우, 새로운 노드의 값이 부모 노드의 값보다 크다면 새로운 노드의 값과 부모 노드의 값을 교환하고, 그렇지 않다면 상태를 유지한다. 마찬가지로 최소 힙의 경우는 새로운 노드의 값이 부모 노드보다 작을 때 교환하게 될 것이다.

삭제

데이터를 삭제할 때, 힙은 다음과 같은 과정을 거친다.

1. 루트 노드를 삭제한다.
2. 가장 말단 노드를 루트 노드의 자리로 옮긴다.
3. 루트 노드와 자식 노드의 값을 비교하여 힙의 성질을 만족할 때까지 교환한다.

최대 힙의 경우, 루트 노드를 삭제하고 말단 노드를 루트 노드의 자리로 옮긴 후, 그것의 값이 자식 노드들 중 큰 값보다 작다면 큰 자식 노드와 자리를 교환하는 방식이다. 최소 힙의 경우도 더 작은 값을 따질 뿐 같은 방식을 반복한다.

출처
https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)
https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%9E%99Heap