*완전 이진 트리(Complete Binary Tree): 트리의 위부터 아래, 왼쪽부터 오른쪽의 순서로 빠짐없이 가득 차있는 이진 트리
ㅁ힙(heap): 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 완전 이진 트리의 일종
+ 영단어 heap: 무엇인가를 차곡차곡 쌓아 올린 더미
+ 자료구조의 힙(Heap)과 컴퓨터 메모리의 힙 영역(Heap Area)은 완전히 다른 개념이다
[힙의 활용]
- 우선순위 큐(Priority Queue): 힙을 사용하여 구현할 수 있으며, 각 요소가 우선순위를 가지는 큐
- 힙 정렬(Heap Sort): 힙을 이용한 정렬 알고리즘으로, O(nlog(n))의 시간 복잡도를 가진다
- 그래프 알고리즘: 크루스칼 알고리즘, 다익스트라 알고리즘 등에서 우선순위 큐를 활용해 최소 신장 트리, 최단 경로를 찾는 데 사용된다
[힙의 종류]
ㅇ최대 힙(Max Heap): 루트 노드에 최대 값이 위치하며, 각 부모 노드의 값이 자식 노드의 값보다 크다
- 최대 값을 빠르게 찾을 수가 있다
- 값이 작은 데이터가 우선적으로 제거
ㅇ최소 힙(Min Heap): 루트 노드에 최소 값이 위치하며, 각 부모 노드의 값이 자식 노드의 값보다 작다
- 최소 값을 빠르게 찾을 수가 있다
- 값이 큰 데이터가 우선적으로 제거
upHeap: 삽입 노드로부터 상향 경로를 따라가며 키 k를 교환함으로써 힙순서 속성을 복구
downHeap: 루트로부터 하향 경로를 따라가며 키 k를 교환함으로써 힙순서 속성을 복구
힙의 데이터 삽입: upHeap
힙의 데이터 삭제: downHeap
[이진트리 생성 방식 2가지]
- 순차힙: 배열을 이용한 순차트리 형태
- 연결힙: 연결리스트를 이용한 연결트리 형태
[힙 생성 방식 2가지]
- 삽입식: 모든 키들이 미리 주어진 경우 or 키들이 차례로 주어지는 경우에 가능
- 상향식: 모든 키들이 미리 주어진 경우에만 가능
(동일 키들의 동일 순서로 구성된 초기 리스트라도 삽입식, 상향식 중 어느 방식을 적용하느냐에 따라 상이한 힙이 생성될 수 있다)
[배열에 기초한 힙의 성질]
왼쪽 자식: 2i
오른쪽 자식: 2i + 1
부모: ⌊i / 2⌋
ㅇheapify(힙화): 입력 배열을 최대 힙 또는 최소 힙 구조로 변환
(힙은 완전 이진 트리의 형태를 가지며, 최대 힙(Max Heap) 또는 최소 힙(Min Heap)으로 정렬된 상태를 유지한다)
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
(문제 1, 2 공통 요구 사항)
1) 순차힙으로 구현한다. 즉, 배열을 이용한 순차트리 형식으로 힙을 저장
2) 최대힙으로 구현한다. 따라서 힙으로부터 삭제 작업은 우선순위 큐에서 일반적으로 이루어지는 최솟값 삭제가 아닌 최대값 삭제가 된다 (참고로 최소힙에서는 최소값 삭제를 수행)
3) 연산 효율을 위해 배열 인덱스 0 위치는 사용하지 않고 비워둔다
4) 데이터구조를 단순화하기 위해 힙의 항목으로써 (키, 원소) 쌍에서 원소를 생략하고 키만 저장하는 것으로 한다
5) 키들은 중복이 없는 1 이상의 정수로 전제 – 즉, 중복 키 검사는 불필요
6) O(1) 공간으로 수행할 것 – 즉, 주어진 키들을 저장한 초기 배열 외 추가 메모리 사용은 O(1)을 초과할 수 없다
7) 힙은 어느 시점에서라도 최대 항목 수 < 100 으로 전제
문제1) 삽입식 힙 생성
대화식 프로그램에 주어지는 명령은 i, d, p, q 네 가지며 각 명령에 대해 다음과 같이 수행해야 한다.
i : <키> : <키>를 힙에 삽입하고 0을 인쇄.
d : 힙에서 삭제(이때 루트에 저장된 키가 삭제되어야 한다)하여 반환된 키를 인쇄.
p : 힙의 내용을 인쇄(이때 이진트리의 레벨순서로 항목들을 인쇄해야 한다).
* 레벨순서란 이진트리의 레벨 0의 노드부터 다음 레벨 1, 2, 33,... 의 노드들을 차례로 방문한다. 같은 레벨의 노드들은 왼쪽에서 오른쪽으로 방문한다.
q : 프로그램 종료
(전체코드)
// 삽입식 힙 생성
#include <stdio.h>
#define MAX_HEAP_SIZE 99
int g_heap[MAX_HEAP_SIZE]; // 배열구조의 힙
int g_n = 0; // 힙의 크기(현재 총 키의 개수)
void insertItem(int key);
int removeMax();
void upHeap(int idx);
void downHeap(int idx);
void printHeap();
int main() {
char cmd;
int key;
while (1) {
scanf("%c", &cmd);
if (cmd == 'i') {
scanf(" %d", &key);
insertItem(key);
printf("0\n");
}
else if (cmd == 'd') {
printf("%d\n", removeMax());
}
else if (cmd == 'p') {
printHeap();
}
else if (cmd == 'q') {
break;
}
}
return 0;
}
void insertItem(int key) {
g_n++;
g_heap[g_n] = key;
upHeap(g_n);
}
int removeMax() {
int key = g_heap[1];
g_heap[1] = g_heap[g_n];
g_n--;
downHeap(1);
return key;
}
void upHeap(int idx) { // 재귀적으로도 구현 가능
int parent;
int temp;
while (idx > 1 && g_heap[idx] > g_heap[idx / 2]) { // g_heap[idx] > g_heap[parent]
parent = idx / 2;
temp = g_heap[idx];
g_heap[idx] = g_heap[parent];
g_heap[parent] = temp;
idx = parent;
}
}
void downHeap(int idx) { // 재귀적으로도 구현 가능
int temp;
int largerChildIdx; // lChildIdx or rChildIdx
int lChildIdx, rChildIdx;
while (2 * idx <= g_n) { // lChildIdx <= g_n
lChildIdx = 2 * idx;
rChildIdx = 2 * idx + 1;
if (rChildIdx <= g_n && g_heap[rChildIdx] > g_heap[lChildIdx])
largerChildIdx = rChildIdx;
else
largerChildIdx = lChildIdx;
if (g_heap[idx] >= g_heap[largerChildIdx])
break;
temp = g_heap[idx];
g_heap[idx] = g_heap[largerChildIdx];
g_heap[largerChildIdx] = temp;
idx = largerChildIdx;
}
}
void printHeap() {
for (int i = 1; i <= g_n; i++) {
printf(" %d", g_heap[i]);
}
printf("\n");
}
문제2) 상향식 힙 생성
1) 이번엔 키들이 미리 한꺼번에 주어진다. 이들을 주어진 순서대로 초기 배열에 저장한다.
2) 초기 배열에 저장된 키들을 상향식으로 재배치하여 힙을 생성한다. 상향식 힙 생성을 위한 재귀 또는 비재귀 방식의 알고리즘 가운데 어느 전략을 사용해도 좋다(사용하지 않은 나머지 전략도 나중에 작성해 보자).
3) 참고로 재귀, 비재귀 두 가지 방식 모두 O(n) 시간에 수행 가능하므로(왜 그런지 복습하자) 그렇게 되도록 작성해야 한다.
(힌트: 문제 1 삽입식 힙 생성에서 이미 작성한 downHeap과 printHeap 함수를 그대로 사용하면 된다)
(전체코드)
// 상향식 힙 생성: 재귀버전/비재귀버전
#include <stdio.h>
#define MAX_HEAP_SIZE 99
int g_heap[MAX_HEAP_SIZE]; // 배열구조의 힙
int g_n = 0; // 힙의 크기(현재 총 키의 개수)
void rBuildHeap(int i); // 재귀버전
void buildHeap(); // 비재귀버전
void downHeap(int idx);
void printHeap();
int main() {
scanf("%d", &g_n);
for (int idx = 1; idx <= g_n; idx++) {
scanf("%d", &g_heap[idx]);
}
rBuildHeap(1);
// buildHeap();
printHeap();
return 0;
}
void rBuildHeap(int idx) { // 재귀버전의 상향식 힙 생성
if (idx > g_n) {
return;
}
int lChildIdx = 2 * idx;
int rChildIdx = 2 * idx + 1;
rBuildHeap(lChildIdx); // 현재 부트리의 좌 부트리 힙 생성
rBuildHeap(rChildIdx); // 현재 부트리의 우 부트리 힙 생성
downHeap(idx); // 현재 부트리의 루트 + 좌우 부트리 힙 생성
}
void buildHeap() { // 비재귀버전의 상향식 힙 생성
for (int idx = g_n / 2; idx >= 1; idx--) {
// 마지막 내부노드부터 역방향으로 루트까지
downHeap(idx);
}
}
// 인덱스 1부터 시작하여 힙을 재구성
void downHeap(int idx) {
int temp;
int largerChildIdx; // lChildIdx or rChildIdx
int lChildIdx, rChildIdx;
while (2 * idx <= g_n) { // lChildIdx <= g_n
lChildIdx = 2 * idx;
rChildIdx = 2 * idx + 1;
if (rChildIdx <= g_n && g_heap[rChildIdx] > g_heap[lChildIdx])
largerChildIdx = rChildIdx;
else
largerChildIdx = lChildIdx;
if (g_heap[idx] >= g_heap[largerChildIdx]) {
break;
}
temp = g_heap[idx];
g_heap[idx] = g_heap[largerChildIdx];
g_heap[largerChildIdx] = temp;
idx = largerChildIdx;
}
}
void printHeap() {
for (int i = 1; i <= g_n; i++) {
printf(" %d", g_heap[i]);
}
printf("\n");
}
/*
3
209 400 77
6
24 17 33 50 60 70
8
5 15 10 20 30 25 31 29
*/
출처 및 참고: 알고리즘-원리와 응용(국형준교수님), Algorithm Design(Jon Kleinberg, Eva Tardos), Foundations of Algorithms using C++(Richard Neapolitan), 자료구조: 우선순위 큐(Priority Queue)와 힙(Heap) 10분 핵심 요약(유튜브 동빈나), 파이썬 알고리즘 인터뷰(박상길)
'Computer Science > 알고리즘' 카테고리의 다른 글
| [알고리즘] ep1-6) 퀵정렬(quick sort) (0) | 2024.07.07 |
|---|---|
| [알고리즘] ep1-5) 병합정렬(merge sort) (0) | 2024.07.05 |
| [알고리즘] ep1-4) 힙정렬(heap sort) (0) | 2024.07.04 |
| [알고리즘] ep1-1) 우선순위 큐 (0) | 2024.07.03 |
| [알고리즘] ep1-2) 버블정렬, 선택정렬, 삽입정렬 (1) | 2024.07.02 |
