힙(Heap)

힙

힙은 다음 조건들을 만족해야 한다.

• O(1): 최대 원소에 즉각적으로 접근할 수 있어야 함.
• O(log N): 원소 삽힙 동작의 시간 복잡도
• O(log N): 최대 원소 삭제 동작의 시간 복잡도

이 조건들의 만족을 시키기 위해 완전 이진 트리(complete binary tree)가 사용된다. 완전 이진 트리는 마지막 레벨의 노드를 제외하고 모두 두개의 자식을 가지며 마지막 노드는 왼쪽부터 노드가 있는 트리이다.

완전 이진 트리는 다른 노드를 가리키는 포인터 없이, 배열 또는 벡터에 저장하고 배열의 인덱스 계산으로 노드의 이동 구현이 가능하기 때문에 메모리 사용에서 효율적이다. 만약 부모 노드가 i 번째 배열 원소로 저장되어 있다면 2*i + 1 또는 2*i +2 번째 인덱스의 배열이 자식 노드가 된다.

힙의 불변성

1. 최대 원소에 즉각적으로 접근 가능해야 함
2. 1의 조건 때문에 부모 노드가 항상 자식 노드보다 커야 함

이러한 조건을 가진 힙을 최대 힙(max heap)이라고 함

1. 최소 원소에 즉각적으로 접근 가능해야 함
2. 1의 조건 때문에 부모 노드가 항상 자식 노드보다 작아야 함

이러한 조건을 가진 힙을 최소 힙(min heap)이라고 함

힙의 연산

힙에 원소 삽입

1. 새로운 원소를 배열의 가장 마지막에 삽입(마지막 노드의 오른쪽에 삽입하는 것과 같음)
2. 부모 노드가 자식 노드보다 큰지 검증하기 위해, 새로운 원소를 부모 노드의 값과 비교, 부모 노드가 더 작다면 서로 교환
3. 조건을 만족할 때까지 2번 동작을 반복
   

힙에서 원소 삭제

힙에서는 루트 노드에만 직접 접근할 수 있으므로 루트 노드만 삭제 가능

1. 루트 노드와 가장 마지막 노드를 교환한 후 가장 마지막 노드를 삭제
   
2. 루트 노드를 자식 노드와 비교하여 부모 노드가 더 작다면 교환
3. 조건을 만족할 때까지 2번 동작을 반복

힙 초기화

다른 자료구조와는 다르게 힙은 불변성을 유지해야 하기 때문에 초기화 하기가 간단하지 않음. 비어 있는 힙에 원소를 하나씩 삽입하는 작업은 O(N log N)의 시간 복잡도를 가져 효율적이지 않음.

힙 생성 알고리즘을 사용하면 O(N) 시간에 힙을 초기화 가능.

전체 트리의 아래쪽부터 힙 불변성을 만족하도록 힙을 업데이트하는 방식. C++ 표준에는 배열 또는 벡터의 반복자를 인자로 받아 힙을 구성하는 std::make_heap() 함수를 제공