이진 힙
이진 힙은 다음 특징(Properties)을 가진 이진 트리입니다.
1. 완전 트리(Complete Tree)이며 배열(Array)안에 저장되기 적합(Suitable)합니다.
2. 이진 힙은 최소(Min) 힙 또는 최대(Max) 힙 중 하나입니다. 최소 힙에서 루트 노드의 값은 모든 노드의 값중 가장 작은 값이며, 최대 힙에서 루트 노드의 값은 모든 노드의 값중 가장 큰 값입니다.
이진 힙의 표현
이진 힙은 완전 이진 트리(Complete Binary Tree)입니다. 이진 힙은 일반적으로(typically) 배열로 표현 됩니다.
루드 노드는 Arr[0] - 배열의 첫번째 요소가 됩니다.
부모 노드의 표현 - Arr[(i-1)/2]
좌측 자식 노드의 표현 - Arr[(2*i)+1]
우측 자식 노드의 표현 - Arr[(2*i)+2]
이진 힙 배열의 순회 순서는 너비(Level) 순서입니다.
힙의 활용
1. 힙 정렬(Heap Sort) : 힙 정렬은 O(nLog n) 시간 복잡도를 가지는 배열의 정렬 방법입니다.
2. 우선순위 큐(Priority Queue) : 우선순위 큐는 O(log n)의 시간 복잡도를 가지는(삽입, 삭제 등) 이진 힙을 효율적으로 사용할 수 있습니다.
3. 그래프 알고리즘(Graph Algorithm) : 그래프 알고리즘에 우선순위 큐를 효과적으로 사용 할 수 있습니다.
최소 힙의 구현 - 소스코드(C++)
class MinHeap
{
int *harr; // 힙 요소 포인터
int capacity; // 최소 힙의 최대 크기
int heap_size; // 최소 힙의 현재 크기
public:
MinHeap(int capacity); // 생성자
void MinHeapify(int);
int extractMin();
int parent(int i) { return (i-1)/2; } // 부모 노드 반환
int left(int i) { return (2*i + 1); } // 좌측 자식 노드 반환
int right(int i) { return (2*i + 2); } // 우측 자식 노드 반환
void decreaseKey(int i, int new_val);
int getMin() { return harr[0]; } // 가장 작은 값(루트 노드) 반환
void deleteKey(int i);
void insertKey(int k);
};
MinHeap::MinHeap(int cap) // 생성자
{
heap_size = 0;
capacity = cap;
harr = new int[cap];
}
void MinHeap::insertKey(int k) // 노드 추가
{
if (heap_size == capacity)
{
cout << "\nOverflow: Could not insertKey\n";
return;
}
heap_size++; // 사이즈 증가
int i = heap_size - 1;
harr[i] = k;
while (i != 0 && harr[parent(i)] > harr[i]) // 자신의 위치를 검색
{
swap(&harr[i], &harr[parent(i)]);
i = parent(i);
}
}
void MinHeap::decreaseKey(int i, int new_val)
{
harr[i] = new_val;
while (i != 0 && harr[parent(i)] > harr[i])
{
swap(&harr[i], &harr[parent(i)]);
i = parent(i);
}
}
int MinHeap::extractMin()
{
if (heap_size <= 0)
return INT_MAX;
if (heap_size == 1)
{
heap_size--;
return harr[0];
}
int root = harr[0];
harr[0] = harr[heap_size-1];
heap_size--;
MinHeapify(0);
return root;
}
void MinHeap::deleteKey(int i)
{
decreaseKey(i, INT_MIN);
extractMin();
}
void MinHeap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
}
정보가 유익하셨다면 아래 공감버튼 눌러주시면 감사하겠습니다.
질문사항은 댓글로 달아주시면 성의껏 답변해드리겠습니다.
