[자료구조] 힙 Heap - 자바스크립트로 구현하기

힙 Heap

이진 트리(binary tree)의 일종으로 항상 완전 이진 트리 형식을 유지한다. 

완전 이진 트리란 왼쪽 노드부터 차례대로 값이 채워지는 형식이다. 부모와 자식 노드의 값 크기에 따라 최대 힙과 최소 힙으로 나눠진다.

최대 힙 (Max Heap)

부모 노드의 값이 자식 노드의 값보다 크거나 같은 경우. 상위 노드(root)가 제일 큰 값을 가짐.

최소 힙 (Min Heap)

부모 노드의 값이 자식 노드의 값보다 작거나 같은 경우. 상위 노드(root)가 제일 작은 값을 가짐.

사용 예제

 

• 우선순위 큐 (ex: 처리 순서가 정해진 작업)
• 다익스트라(Dijkstra) 알고리즘 (최단 경로 구하기)
• 힙 정렬 (Heap Sort)

 

예시

[9, 7, 6, 5, 4, 3, 2, 1] 배열을 heap으로 나타내 보자.

손으로 끄적인거라 깔끔하지 않은 점 주의

해당 배열을 토대로 트리를 그릴 경우 위와 같이 그릴 수 있다. 최상위 노드(root) 값이 9로 제일 큰 값이다. Max Heap에 해당하는 경우이다.

이제 노드의 각 인덱스를 살펴보자.

그림과 같이 트리에 각 노드의 인덱스를 표시해주면 이제 부모와 자식 인덱스 간의 규칙이 보인다. 이를 토대로 부모, 자식 인덱스를 구하는 코드를 작성해보자.

 

부모 노드의 왼쪽 자식 인덱스 구하기

값이 7인 인덱스 1인 노드의 왼쪽 자식 노드는 값 5를 가지고 인덱스 값은 3을 가진다. 

인덱스 1인 노드의 왼쪽 자식 노드의 인덱스 값은 1 ✕ 2 + 1 = 3 즉, 왼쪽 자식 노드의 인덱스 = 부모 노드 인덱스 ✕ 2 + 1 식을 이용하여 구할 수 있다. 코드는 다음과 같다.

function getLeftChildIndex(parentIndex){
	return parentIndex * 2 + 1;
}

부모 노드의 오른쪽 자식 인덱스 구하기

값이 7인 인덱스 1인 노드의 왼쪽 자식 노드는 값 4를 가지고 인덱스 값은 4을 가진다.

인덱스 1인 노드의 왼쪽 자식 노드의 인덱스 값은 1 ✕ 2 + 2 = 4 즉, 왼쪽 자식 노드의 인덱스 = 부모 노드 인덱스 ✕ 2 + 2 식을 이용하여 구할 수 있다. 코드는 다음과 같다.

function getRightChildIndex(parentIndex){
	return parentIndex * 2 + 2;
}

부모 노드의 인덱스 구하기

왼쪽 노드 자식의 인덱스 = 부모 노드 * 2 + 1

오른쪽 노드 자식의 인덱스 = 부모 노드 * 2 + 2

였으므로 부모 노드의 인덱스를 구하는 식은 

부모 노드 인덱스 = (자식 노드 인덱스 - 1) / 2 의 정수값

임을 알 수 있다.

function getParentIndex(childIndex){
	return parseInt((childIndex - 1) / 2);
}

 

Max heap 기준으로 새로운 노드를 추가하고 삭제하는 과정에 대해 코드를 작성해보자.

힙에 값 추가하기(Insert)

새로운 값을 추가하는 경우 맨 끝에 새로운 값을 담은 노드를 추가하게 된다.

이 때 새롭게 추가된 노드는 부모 노드의 값과 비교하여 더 큰 경우 부모 노드와 자리를 바꾼다. 즉, 부모 노드가 자식 노드가 되고 자식 노드였던 노드는 부모 노드가 되는 것이다.

이와 같이 부모 노드와 값을 비교하고 자리를 바꾸는 과정을 반복하여 Max heap 조건이 성립하도록 노드를 정리한다.

예제

[9, 7, 6, 5, 4, 3, 2, 1] 에 8이라는 값을 추가할 경우에 대해 생각해보자.

값 8을 가진 노드는 부모 노드의 값 4보다 크므로 서로 교체한다.

그 후 부모 노드 값 7보다 8의 값이 더 크므로 또 교체한다.

이제 부모 노드 값 9 > 비교할 노드 값 8이므로 더 이상 값을 교체하지 않아도 되는 완전한 heap에 성립된다.

이와 같은 과정을 토대로 코드는 다음과 같이 작성할 수 있다.

let heap = [9, 7, 6, 5, 4, 3, 2, 1];

function insertion(value){
    heap.push(value);
	let index = heap.length - 1;

    while(index > 0){
    	let parentIdx = getParentIndex(index); // 위에서 작성한 getParentIndex를 사용한다.
        
   		if(heap[parentIdx] >= heap[index]) break;
        
		[heap[parentIdx], heap[index]] = [heap[index], heap[parentIdx]];
        index = parentIdx;
    }
}

 

root 노드 삭제하기

[9, 7, 6, 5, 4, 3, 2, 1] 에서 root 노드를 삭제하는 경우에 대해 생각해보자.

배열에 대해 트리 구조를 그리면 위와 같다.

이제 값 9를 가진 상위 노드를 삭제한다. 그럼 상위 노드 자리게 비게 되는데 최하위 노드 값을 상위 노드에 부여한다.

이 후 최상위 노드 값이 heap 조건에 성립하는지 판별하며 올바른 자리를 찾아주자.

상위 노드 값 2 < 자식 노드 값 7 이므로 둘의 자리를 교체한다.

이번엔 부모 노드 값 2 < 자식 노드 값 5이므로 또 자리를 교체해준다.

그럼 이제 최대힙 조건에 성립하게 된다.

이와 같은 과정을 코드로 작성하면 다음과 같다.

let heap = [9, 7, 6, 5, 4, 3, 2, 1];

function remove(){
	let index = 0;
	let lastValue = heap.pop();
    heap[0] = lastValue;
    
    while(index < heap.length){
    	let left = getLeftChildIndex(index), right = getRightChildIndex(index);
        let child;
		if(left < heap.length && right < heap.length){
        	child = heap[left] > heap[right]? left : right;
        } else if (left < heap.length){
        	child = left;
        }
        
        if(child !== null && heap[child] > heap[index]){
        	[heap[child], heap[index]] = [heap[index], heap[child]];
            index = child;
        } else break;
    }
}

 

높이

heap의 높이 h는 n이 노드의 개수인 경우 log n이라고 표현할 수 있다. 

층별로 (2^층수)개의 노드가 위치하게 되어 1 + 2^1 + 2^2 + ... + 2^h = n 이다.

따라서 push와 pop 연산 시 최대이동거리는 O(log n)이라고 표현할 수 있다.

💡 Heap을 사용해야하는 문제 특징

문장/상황	힙을 떠올릴 수 있는 힌트
"가장 작은 / 가장 큰" 요소를 반복해서 사용한다	✅ 힙 사용하라는 신호
"계속 정렬된 상태를 유지하면서 삽입/삭제"한다	✅ 정렬된 구조 유지 → 힙
"최댓값/최솟값을 빠르게 꺼내야 하는 연산이 많다"	✅ 배열보다 힙이 훨씬 효율적
리스트에 값을 넣고, 다시 정렬하거나 정렬 기준으로 꺼낸다	✅ PriorityQueue(=Heap) 적합