힙이란
이진 검색 트리와 비슷한 형태의 구조를 가지고 있지만 트리보다 더 느슨한 대소 관계 조건을 가지고 있고 더 엄격한 모양 조건을 가지고 있는 구조를 말한다. 이진 검색 트리는 루트보다 작은 노드는 왼쪽 자식, 큰 노드는 오른쪽 자식의 규칙을 가지고 있는데, 힙은 부모 노드보다 자식 노드가 작기만 하면 된다. 이렇게 느슨한 대소 관계 규칙을 가지고 있기 때문에 모양 규칙은 더 엄격하다. 마지막 레벨을 제외한 레벨의 노드는 모두 꽉 차 있어야 하고 마지막 레벨에 노드가 있을 때는 왼쪽부터 채워져야 한다.
힙의 구현
이렇게 항상 일정한 모양을 갖게끔 강제 되기 때문에 힙은 트리 처럼 구조체 등을 이용해 복잡하게 구현할 필요 없이 벡터와 같은 컨테이너 하나로 구현할 수 있다. 보통 컨테의너의 첫 원소를 힙의 루트 노드로 본다.
- A[i]에 대응되는 노드의 왼쪽 자손은 A[2*i+1]에 대응된다
- A[i]에 대응되는 노드의 오른쪽 자손은 A[2*i+2]에 대응된다
- A[i]에 대응되는 노드의 부모는 A[(i-1)/2]에 대응되는데, 이 때 나눗겜의 결과는 내림한다.
이러한 규칙에 따라 배열에 모든 노드를 저장하면 연결 관계를 명시하지 않고서도 힙의 구조대로 노드들을 배치할 수 있다.
원소 삽입
원소를 삽입하는 경우 새로운 원소의 값에 따라 힙의 대소 관계 규칙, 모양 규칙을 만족시키면서 적절한 곳에 삽입해주어야 한다. 이를 동시에 만족시키고자 하면 과정이 복잡해 질 수 있기 때문에, 먼저 모양 규칙부터 적용시킨 뒤 수정해 나간다. 모양 규칙에 따르면 새로운 원소는 힙의 마지막 왼쪽 리프에 들어가는데, 이는 컨테이너에서 마지막 원소에 해당된다. 일단 그 위치에 새로운 원소를 삽입한 뒤 대소 관계 규칙을 확인해 주기 위해 부모 노드와 값을 비교한다. 부모 노드와 값을 비교해 만약 새로운 값이 더 큰 경우에는 부모와 자리를 바꿔 주고 같은 과정을 반복한다.
이렇게 하면 결국 새로운 원소는 대소 관계 규칙과 모양 규칙을 모두 만족시키는 적절한 곳에 위치하게 된다. 시간 복잡도는 힙의 높이에 비례하므로 logN이다.
최대 원소 꺼내기
힙의 가장 큰 장점 중 하나는 컨테이너에서 최대 원소를 효율적으로 꺼낼 수 있다는 것이다. 힙의 최대 원소는 항상 루트 노드, 즉 컨테이너의 첫 번째 원소이기 때문에 간단히 꺼낼 수 있다. 그러나 꺼낸 뒤 힙의 구조를 그대로 유지시켜줘야 한다는 문제가 있다. 이를 위해서 원소를 삽입한 경우와 유사한 과정으로 구조를 유지시킨다. 먼저 힙의 최소 원소, 즉 마지막 원소를 빼낸 루트 노드 자리에 넣고 자식 노드들과 값을 비교해 더 큰 값과 자리를 바꾼다. 이 작업을 트리에 리프에 도달하거나 두 자식이 모두 자기 자신 이하의 원소를 갖고 있을 때 까지 반복하면 힙의 구조가 완성된다. 시간 복잡도는 힙의 높이에 비례하므로 logN이다.
힙의 다른 연산
힙은 최대 원소를 가장 빠르게 꺼낼 수 있다는 특징을 이용해 정렬에도 활용되는데 이를 힙 정렬이라고 부른다. 힙 정렬은 매 원소마다 최대 원소를 꺼내고 힙의 구조를 다시 만들어 주는 과정을 거치면 되므로 NlogN의 시간 복잡도를 갖는 효율적인 정렬이다.
