MaxHeap(최대 힙) 구현
1) Root를 항상 최댓값으로 가진다
2) 최대 힙의 구조에서 형제 노드(Sibling Node)끼리는 대소관계가 필요하지 않다.
* 삽입 연산 시에는 최대 힙의 '구조'만 가지면 되기 때문에 자식, 즉 깊이(Depth)에서의 대소관계만 필요
* 삭제 연산 시에는 최대 힙의 구조에서 루트에 항상 최댓값이 오기 때문에 형제 노드끼리의 대소관계도 필요
→ 삽입 시 부모노드와 자식노드만 비교, 삭제 시 부모노드와 자식노드의 형제노드까지 비교
3) 완전 이진 트리의 형태를 가진다.
→ 깊이의 차이가 1이 넘게 날 수 없다.
어떠한 부모노드가 왼쪽 자식은 없는데 오른쪽 자식은 있는 경우는 없다. 단, 잎(Leaf) 노드는 상관 없다.
* 부모 / 자식간의 인덱스의 참조를 편하게 하기 위해 Root = heap[0]이 아닌 heap[1]로 정의
1) Heap_push (힙의 삽입) - vector 자료구조 이용
void heap_push(int key)
{
heap.push_back(key);
if (heap.size() == 2) return;
int child = heap.size() - 1;
int parent = child / 2;
while (child > 1 && heap[parent] < heap[child])
{
int temp = heap[parent];
heap[parent] = heap[child];
heap[child] = temp;
child = parent;
parent = child / 2;
}
}- key값을 우선 삽입합니다.
- key값을 삽입했는데 힙의 사이즈가 2라면 현재 힙에 들어와있는 데이터가 1개밖에 없다는 의미입니다. 그대로 종료.
* heap[0]은 사용하지 않으나, 공간은 차지하고 있는 상태입니다.
* 그렇다면 heap[1]이 사실상 첫 번째 공간이 되나, size는 1개가 들어왔을때 [0]의 공간까지 포함 2의 크기를 가집니다.
- child와 parent 정의
* child는 현재 맨 마지막에 삽입되있으므로 child의 index는 맨 마지막
* parent는 child / 2
- child가 parent보다 크다면 최대힙의 정의에 위배. 그러므로, parent가 child보다 더 클 수 있도록 계속해서 반복해줍니다.
※ 삽입의 연산 횟수는 최대 트리의 높이만큼 이루어집니다. 그러므로, 시간복잡도 = O(logN)
2) Heap_pop(힙의 삭제)
void heap_pop()
{
if (heap.size() == 1)return;
int temp = heap[1];
heap[1] = heap[heap.size() - 1];
heap[heap.size() - 1] = heap[1];
heap.pop_back();
int parent = 1;
int child = 2;
if (child + 1 < heap.size())
{
if (heap[child + 1] > heap[child])
child = child + 1;
}
while (child <= heap.size() && heap[child] > heap[parent])
{
int temp = heap[parent];
heap[parent] = heap[child];
heap[child] = temp;
parent = child;
child = parent * 2;
if (child + 1 < heap.size())
{
if (heap[child + 1] > heap[child])
child = child + 1;
}
}
}- 힙에 원소가 아무것도 들어있지 않다면 삭제연산을 하지 않습니다.
- 최대 힙에서의 삭제
* Root노드와 마지막 노드를 SWAP → 마지막 노드 삭제 → 힙의 재구성
- Root를 마지막 노드르 옮겨주고 마지막 노드를 Root로 가져온 후, 마지막 노드를 삭제해줍니다.
- Root 노드를 자식과 비교해가며 연산을 수행합니다 → Root노드는 항상 최댓값이 와야 하기 때문에 자식 2명 다 비교
* heap[parent] < heap[child]라면 parent가 더 클 수 있도록 연산해줍니다.
* child와 child의 형제 노드 (child + 1)의 대소관계까지 확인해야합니다.
- 이 작업을 하지 않으면 같은 깊이에 있는 형제 노드 간에 무엇이 더 큰 값인지를 확인하지 않기 때문에
루트에 항상 최댓값을 넣을 수 있다는 정의에 위배가 됩니다.
※ 삭제 연산은 최대 트리의 높이만큼 연산, 시간복잡도 = O(logN)
=============================================================================
즉, 삭제와 삽입에 모두 O(logN)의 시간복잡도를 가지는 자료구조입니다.
=============================================================================
힙 정렬은 어떻게 할까요?
Heap_pop 연산을 한 값을 나열하면 됩니다. 즉, Heap_pop 연산을 계속 하면 됩니다.
Heap은 Root에 최댓값을 기록해두는 자료구조입니다.
Heap_pop을 계속해서 한다는 것은, 매 연산이 실행될 때마다 최댓값을 pop한다는 소리이기 때문에
현재 Heap구조에서 최댓값이 내림차순으로 정렬이 됩니다.
하여 Heap정렬이 O(NlogN)의 시간을 가지는 것입니다. N개의 데이터에 대하여 POP을 N번 한 것과 동일!
최소힙은 대소관계만 바뀌고, 작은 값이 Root로 오도록 설계해주면 됩니다.