정의
- 완전 이진트리(Complete Binary Tree)의 일종으로, 부모 노드와 자식 노드 간에 특정한 조건을 만족하는 자료구조
- 최대 힙(Max Heap): 부모 노드가 항상 자식 노드보다 크거나 같은 값을 가지는 힙
- 최소 힙(Min Heap): 부모 노드가 항상 자식 노드보다 작거나 같은 값을 가지는 힙
특성
- 힙은 완전 이진트리이다.
- 완전 이진트리란 부모 노드 밑에 자식 노드가 최대 2개까지 있을 수 있고, 마지막 레벨을 제외한 모든 레벨에 노드가 완전히 채워져 있는 트리구조
- 모든 레벨이 완전히 채워져 있으며 마지막 레벨은 왼쪽부터 오른쪽으로 순서대로 채워져 있다.
- 힙에서는 항상 루트 노드가 가장 크거나(최대 힙) 가장 작은(최소 힙)을 가진다.
- 시간 복잡도
O(n log n)- 힙의 높이만큼 재귀 호출을 하기 때문
- 예를 들어,
노드가 4개일 때 높이는 2 (h = log2(4) = 2)
노드가 8개일 때 높이는 3 (h = log2(8) = 3) - 힙에서 삽입과 삭제 를 할 때, 트리의 높이만큼 이동하면 되기 때문에 연산의 시간복잡도는
O(log n)이다. 즉, 노드가 많아질수록 높이는 로그 형태로 증가한다.
힙의 구조
- 힙은 보통 배열을 이용하여 구현(배열 인덱스를 사용하여 부모와 자식 노드 간의 관계를 표현
- 인덱스
i의 부모 노드 인덱스는(i-1)/2. - 인덱스
i의 왼쪽 자식 노드 인덱스는2*i + 1. - 인덱스
i의 오른쪽 자식 노드 인덱스는2*i + 2.
- 인덱스
최소힙(minHeap)
class MinHeap {
constructor() {
this.heap = [];
}
private getParentIndex(index: number): number {
return Math.floor((index - 1) / 2);
}
private getLeftChildIndex(index: number): number {
return 2 * index + 1;
}
private getRightChildIndex(index: number): number {
return 2 * index + 2;
}
// 힙의 루트값(최소값)반환
public peek(): number | undefined {
return this.heap[0];
}
// 힙에서 루트 값을 제거하고 반환
// 루트에 힙의 마지막 요소를 이동시키고 heapifyDown 호출해 힙의 구조를 유지
public pop(): number | undefined {
if (this.heap.length === 1) return this.heap.pop();
const root = this.heap[0];
this.heap[0] = this.heap.pop()!;
this.heapifyDown(0);
return root;
}
public push(value: number): void {
this.heap.push(value);
this.heapifyUp(this.heap.length - 1);
}
public size(): number {
return this.heap.length;
}
// 힙에 새 요소가 추가 된 후, 힙의 구조를 유지하기 위해 부모 노드와 비교하며 위로 올라가는 작업 수행
// 루트에 도달하거나 부모 노드가 더 작을때까지 반복
private heapifyUp(index: number): void {
// 현재 위치 추적
let currentIndex = index;
while (currentIndex > 0) {
const parentIndex = this.getParentIndex(currentIndex);
if (this.heap[currentIndex] < this.heap[parentIndex]) {
[this.heap[currentIndex], this.heap[parentIndex]] = [
this.heap[parentIndex],
this.heap[currentIndex],
];
currentIndex = parentIndex;
} else break;
}
}
private heapifyDown(index: number): void {
// 현재 위치 추적
let currentIndex = index;
// 왼쪽 노드에 자식이 존재할 때 반복
while (this.getLeftChildIndex(currentIndex) < this.size()) {
const leftChildIndex = this.getLeftChildIndex(currentIndex);
const rightChildIndex = this.getRightChildIndex(currentIndex);
// 왼쪽 인덱스로 초기화
let smallerChildIndex = leftChildIndex;
// 오른쪽이 더 작다면 오른쪽으로 업데이트
if (
rightChildIndex < this.size() &&
this.heap[rightChildIndex] < this.heap[leftChildIndex]
) {
smallerChildIndex = rightChildIndex;
}
// 자식 노드 중 더 작은 값을 가진 노드와 현재 노드를 비교하여
// 현재 노드가 더 크다면 두 노드를 교환
if (this.heap[currentIndex] > this.heap[smallerChildIndex]) {
[this.heap[currentIndex], this.heap[smallerChildIndex]] = [
this.heap[smallerChildIndex],
this.heap[currentIndex],
];
currentIndex = smallerChildIndex;
} else break;
}
}
}활용
1. 우선순위 큐
- 우선순위 큐는 각 요소에 우선순위가 부여된 큐를 말한다.
- 우선순위가 높은 요소가 먼저 처리되며 힙은 우선순위 큐를 구현하는 데 자주 사용된다.
2. 힙 정렬(Heap Sort)
- 힙을 이용해 배열을 정렬하는 알고리즘
- 정렬되지 않은 배열을 최대 힙이나 최소 힙으로 구성하고, 루트 노드를 가장 마지막 노드와 교환 한 후 힙 크기를 줄이는 방식으로 정렬한다.
- 시간복잡도:
O(n log n)(힙 생성O(n)+ 힙 제거O(log n))
- 별도의 메모리를 사용하지 않는 제자리 정렬(in-place sorting)방식을 사용하는데, 이는 일정한 성능과 메모리를 사용하지 않는 이점이 있다.
- 각 원소가 k위치만큼 떨어져 있는 배열인 k-sort 배열을 정렬할 때 가장 효율적인 방법이다.
- 숫자가 같은 경우에 스왑이 일어날 수 있기 때문에, 안정적이지 않은 정렬 방법으로 분류된다.
문제에 적용하기
프로그래머스 문제 중 "더 맵게" 라는 문제에 적용할 수 있다.
https://school.programmers.co.kr/learn/courses/30/lessons/42626
1 차 풀이
function solution(scoville: number[], k: number) {
let count = 0;
scoville.sort((a, b) => a - b);
while (scoville[0] < k) {
if (scoville.length < 2) return -1;
const first = scoville.shift();
const second = scoville.shift();
if (!first || !second) return;
const newScrovile = first + second * 2;
scoville.push(newScrovile);
scoville.sort((a, b) => a - b);
count++;
}
}코드 비효율 분석
sort()함수의 평균 시간복잡도는O(n log n)- 최선일땐
O(n)이지만 최악일땐O(n log n)
- 최선일땐
- 반복문(
while) 에서shift()는O(n)sort()는O(n log n)O(n log n)*O(n)=O(n^2 log n)
- 반복문(
while)에서 매 루프마다shift()와sort()하는 것이 비효율적이다.
최소힙으로 개선
function solution(scoville, k) {
let count = 0;
// 최소 힙 구성
const minHeap = new MinHeap();
for (const sco of scoville) minHeap.push(sco);
while (minHeap.peek() < k) {
if (minHeap.size() < 2) return -1;
const first = minHeap.pop();
const second = minHeap.pop();
const newScoville = first + second * 2;
minHeap.push(newScoville);
count++;
}
return count;
}
힙으로 어떤 점을 개선?
매 루프마다 shift()와 sort() 했던 것을 heap 을 이용하여 불필요한 정렬을 계산하지 않는다.
heap은 항상 최솟값이 루트에 위치하도록 유지(O(1))하고 깊이 만큼만 루프를 반복하게 되는데, heap 이 완전 이진트리이기 때문에 heap의 깊이(높이)는 log2 n에 비례하여 시간복잡도가 O(log n)이 된다.
