[자료구조]Heap 공부: 최대 히입, 최소 히입

1. 힙 Heap이란?

 

 힙(heap)은 우선순위 큐(priority queue)라고도 부르며, 컨테이너에서 가장 작은 또는 가장 큰 원소에 빠르게 접근할 수 있는 자료구조 입니다. 

 

연산	시간 복잡도
원소 접근	O(1)
원소 삽입	O(log N)
원소 삭제	O(log N)

 

 원소 삽입/삭제 연산에 대해 O(log N)의 시간 복잡도를 만족하기 위해선 완전 이진 트리 구조를 사용해야 합니다. 

 

 완전 이진 트리는 마지막 레벨의 노드를 제외하고는 모두 두 개의 자식 노드가 있고, 마지막 레벨에서는 왼쪽부터 차례대로 노드가 있는 트리입니다. 

 

완전 이진 트리

 완전 이진 트리는 트리의 데이터를 배열을 이용하여 저장할 수 있습니다.

 

 배열을 이용한 완전 이진 트리 표현은 다른 노드를 가리키는 포인터를 저장할 필요가 없기 때문에 메모리 사용 측면에서 효율적입니다. 

 

 부모 노드의 index가 i 라면, 자식 노드는 i*2+1, i*2+2 이고,

 자식 노드의 index가 i 라면, 부모 노드는 (i-1) / 2 입니다. 

 

 

 

2. 힙의 불변성(invariants)

 

 힙에서 원소를 삽입하거나 삭제할 때 유지해야 할 조건이 있는데, 이를 힙의 불변성이라고 합니다. 

 

 그 종류에는 최대 힙(max heap)과 최소 힙(min heap)이 있습니다. 

 

 (1) 최대 힙 max heap

 

 최대 힙은 최대 원소가 항상 트리의 루트에 위치합니다. 때문에 최대 원소에 빠르게 접근해야 할 때 최대 힙을 사용합니다. 

 

 최대 힙의 불변성은 부모 노드가 자식 노드보다 항상 크게 유지하도록 설정합니다. 

 

 

 (2) 최소 힙 min heap

 

 최소 힙은 최소 원소가 항상 트리의 루트에 위치합니다. 때문에 최소 원소에 빠르게 접근해야 할 때 최소 힙을 사용합니다. 

 

 최소 힙의 불변성은 부모 노드가 자식 노드보다 항상 작게 유지하도록 설정합니다. 

 

출처: https://t1.daumcdn.net/cfile/tistory/17084F504DA9895214

 

 

 

3. 힙 연산

 

 (1) 원소 삽입

 

 힙에 새로운 원소를 삽입하는 연산입니다. 

 

 우선 새로운 원소를 완전 이진 트리의 맨 마지막에 삽입합니다. 

 

 그 후에 힙의 불변성에 맞게, 삽입된 원소와 부모 노드를 재귀적으로 비교하며 알맞은 위치에 배치될 때까지 swap 합니다. 

 

 

 (2) 원소 삭제 

 

 힙에서는 다른 원소에 직접 접근할 수 없기 때문에 루트 노드만 삭제할 수 있습니다. 

 

 우선 루트 노드와 트리의 맨 마지막 노드를 swap 합니다. 

 

 그 후 맨 마지막 노드(기존의 루트 노드)를 삭제합니다. 

 

 이제 루트 노드에 알맞은 노드가 배치될 때까지 재귀적으로 자식 노드와 비교하며 swap 합니다. 

 

 

 (3) 힙 초기화

 

 힙 초기화는 힙에서 중요한 연산 중 하나입니다. 가장 간단한 알고리즘은 비어 있는 힙에 하나씩 원소를 삽입하는 방법이나, 이 작업은 O(N log N)의 시간 복잡도를 가지므로 비효율적입니다. 

 

 그러나 힙 생성 알고리즘(heapifycation algorithm)을 사용하면 O(N) 시간에 힙을 초기화 할 수 있습니다. 

 

 이 알고리즘은 전체 트리의 아래 서브 트리부터 힙 불변성을 만족하도록 힙을 업데이트하는 방식입니다. 한 레벨씩 트리 위로 올라가면서 힙 속성을 만족하도록 트리를 업데이트합니다. 

 

 c++ 에서는 std::make_heap() 함수를 제공합니다.