All
힙의 정의
•
완전 이진 트리(Complete Binary Tree) 형태로 정렬됨
•
항상 가장 위(루트)에 있는 값을 우선적으로 꺼내는 구조
•
부모 노드는 항상 자식 노드보다 우선순위가 높음
기본연산 & 시간 복잡도
연산 | 설명 |
insert(element) | 힙에 새로운 데이터 삽입 |
delete() | 루트 노드(최상위 데이터) 삭제 |
peek() | 루트 노드의 데이터 읽기 (삭제 X) |
isEmpty() | 힙이 비어있는지 확인 |
size() | 힙에 저장된 데이터 개수 확인 |
연산 | 시간 복잡도 |
삽입 (insert) | O(log n) |
삭제 (delete) | O(log n) |
최솟값/최댓값 조회 (peek) | O(1) |
전체 정렬 (heap sort) | O(n log n) |
힙의 종류
최소힙
•
루트가 전체 노드 중 가장 작은 값
•
모든 부모 노드는 자식 노드보다 작거나 같다
•
트리의 레벨에 따라 데이터가 정렬되지 않아도 됨
•
탐색 트리와 달리 왼쪽-오른쪽 자식 간 크기 관계는 무관
최대힙
•
루트가 전체 노드 중 가장 큰 값
•
모든 부모 노드는 자식 노드보다 크거나 같다
•
트리의 레벨과 상관없이 우선순위 규칙만 만족하면 됨
힙은 두 가지 조건을 모두 만족해야 함
1.
완전 이진 트리 형태
2.
부모 노드의 우선순위 ≥ 자식 노드의 우선순위
힙과 이진트리 비교
항목 | 힙(Heap) | 이진 탐색 트리(BST) |
구조 | 완전 이진 트리 | 일반 이진 트리 |
정렬 기준 | 부모-자식 간 크기 비교만 | 왼쪽 < 부모 < 오른쪽 |
탐색 속도 | 느림 (정렬 안 되어 있음) | 빠름 (이진 탐색 가능) |
삽입/삭제 | O(log n) | O(log n) |
사용 예 | 우선순위 큐 | 탐색/정렬 중심 |
힙의 삽입 및 삭제 연산
힙의 구현
•
힙은 배열을 이용해 구현함
•
완전 이진트리로 왼쪽부터 순서대로 채워지기 때문에 메모리 낭비가 없어 배열 사용
예시(최소힙)
1
/ \
15 5
/ \ / \
20 16 10 19
/ \ / \ / \
25 30 17 18 12 23
Python
복사
index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
value | 1 | 15 | 5 | 20 | 16 | 10 | 19 | 25 | 30 | 17 | 18 | 12 | 23 |
삭제 연산
•
힙의 삭제 연산은 항상 루트 노드를 제거
삭제 과정
1.
루트 노드 제거
2.
마지막 원소를 루트에 올림
3.
루트부터 자식 노드들과 비교하며 작은 자식과 교환(sit-dowm) 반복
단계 | 배열 상태 | 설명 |
초기 | [ -, 1, 15, 5, 20, 16, 10, 19, 25, 30, 17, 18, 12, 23 ] | 초기 상태 |
step 1 | [ -, 23, 15, 5, 20, 16, 10, 19, 25, 30, 17, 18, 12 ] | 마지막 원소(23) → 루트 |
step 2 | [ -, 5, 15, 23, 20, 16, 10, 19, 25, 30, 17, 18, 12 ] | 23  5 (자식 중 최소와 교환) |
step 3 | [ -, 5, 15, 10, 20, 16, 19, 23, 25, 30, 17, 18, 12 ] | 23 10 |
최종 | [ -, 5, 15, 10, 20, 16, 19, 23, 25, 30, 17, 18 ] | 힙 성질 복구 완료 |
결과
5
/ \
15 10
/ \ / \
20 16 19 23
/ \ / \
25 30 17 18
Python
복사
•
시간 복잡도 O(logn)
C 코드
int deleteMin(Heap* h) {
int data = h->heap[1]; // 루트 값 (반환용)
int temp = h->heap[h->size--]; // 마지막 노드 값
int parent = 1, child = 2;
while (child <= h->size) {
if (child < h->size && h->heap[child] > h->heap[child + 1])
child++; // 더 작은 자식 선택
if (temp <= h->heap[child]) break;
h->heap[parent] = h->heap[child];
parent = child;
child *= 2;
}
h->heap[parent] = temp;
return data;
}
C
복사
삽입 연산
•
새로운 데이터를 배열의 마지막 위치에 추가한 뒤, 부모와 비교하면서 위로 이동(sift-up)
예시 - 값 7 삽입
단계 | 배열 상태 | 설명 |
초기 | [ -, 5, 15, 10, 20, 16, 19, 23, 25, 30, 17, 18 ] | 삭제 후 상태 |
step 1 | [ -, 5, 15, 10, 20, 16, 19, 23, 25, 30, 17, 18, 7 ] | 7을 마지막(13) 추가 |
step 2 | [ -, 5, 15, 10, 20, 7, 19, 23, 25, 30, 17, 18, 16 ] | 7 16 교환 (부모보다 작음) |
step 3 | [ -, 5, 15, 7, 20, 10, 19, 23, 25, 30, 17, 18, 16 ] | 7 10 교환 |
최종 | [ -, 5, 15, 7, 20, 10, 19, 23, 25, 30, 17, 18, 16 ] | 힙 복구 완료 |
결과
5
/ \
15 7
/ \ / \
20 10 19 23
/ \ / \
25 30 17 18
C
복사
•
시간 복잡도 O(logn)
C 코드
void insert(Heap* h, int data) {
int i = ++(h->size); // 마지막 인덱스 확보
while (i != 1 && data < h->heap[i / 2]) {
h->heap[i] = h->heap[i / 2]; // 부모를 아래로 내림
i /= 2; // 위로 이동
}
h->heap[i] = data; // 올바른 위치에 삽입
}
C
복사
힙의 활용
데이터의 우선순위를 빠르게 결정해야 하는 상황에서 자주 사용
•
우선순위 큐
•
작업 스케줄링
•
네트워크 패킷 처리
•
최단경로 탐색 알고리즘
•
힙 정렬
우선순위 큐
•
데이터의 삽입 순서가 아니라 우선순위(priority) 에 따라 처리되는 큐
힙으로 우선순위 큐를 구현하는 이유
•
루트가 항상 최대(최소)값으로 가장 높은 우선순위의 데이터를 즉시 꺼낼 수 있음
•
데이터 삽입/삭제 시 힙 성질을 유지하며 자동으로 재졍렬됨
•
배열로 구현되어 효율적임
•
전체 정렬이 아닌 루트의 우선순위만 보장해 우선순위 큐 목적과 맞음
일반 정렬 vs 힙 구조 비교
구조 | 최댓(최소)값 꺼내기 | 삽입 | 전체 정렬 |
배열 (정렬 X) | O(n) | O(1) | O(n log n) 필요 |
정렬된 배열 | O(1) | O(n) | 항상 정렬 유지 필요 |
힙 (Heap) | O(1) | O(log n) | 부분 정렬만 유지 (루트만 보장) |