힙이란 무엇입니까?
힙은 일종의 완전한 이진 트리입니다.
주로 우선 순위 큐를 구현하기 위한 기본 데이터 구조로 사용됩니다.
트리 구조이기 때문에 삽입과 삭제에 O(logN) 시간이 걸린다.
개념 자체는 그리 어렵지 않습니다.
힙은 최대 힙과 최소 힙으로 구분할 수 있으며 최대값 또는 최소값을 짧은 시간 내에 찾을 수 있습니다.
이러한 힙 구조는 주로 배열을 이용하여 구현할 수 있지만, 다른 언어의 경우 힙 구조 자체는 기본적으로 다른 라이브러리에서 제공한다.
예를 들어 Java에는 주로 PriorityQueue가 있고 Python3에는 힙을 구성하는 heapq 또는 heapify 함수가 있지만 물론 JS는 이를 지원하지 않습니다.
물론 코딩 테스트 영역 밖에 있는 경우 JS는 외부 라이브러리 O를 통해 힙을 사용할 수도 있습니다.
![[기획] HTTP 상태 코드 정리](https://see.main.seoul.kr/wp-content/plugins/contextual-related-posts/default.png "[기획] HTTP 상태 코드 정리")
힙의 부모-자식 관계
힙은 배열을 사용하여 전체 이진 트리로 구현됩니다.
이진 트리이기 때문에 자연스럽게 부모 노드와 자식 노드가 발생하는데, 힙의 경우 일반적인 완전 이진 트리와 달리 세미 정렬 상태(느슨하게 정렬된 상태)를 유지합니다.
즉, 최대 힙이면 큰 값이 상위 노드에, 최소 힙이면 작은 값이 상위 노드에 배치됩니다.
그렇다면 배열로 힙을 구현하려면 어떻게 해야 할까요? 알고리즘 문제가 있는 경우 배열의 첫 번째 값이 비어 있는 경우가 많습니다.
배열의 첫 번째 요소의 인덱스가 0이므로 “first”라는 단어와 인지 부조화가 있으므로 계산하기 쉽도록 그렇게 하는 경향이 있습니다.
물론 이런 부조화에 익숙하다면 시작을 비워 둘 필요는 없지만, 이 포스팅에서는 계산을 쉽게 하기 위해 첫 번째 배열 값을 비워두었습니다.
class Heap {
constructor() {
this.heap = ( null ); // 첫 원소는 사용 X
}
}배열의 첫 번째 요소가 사용되지 않으므로 다음과 같은 부모-자식 관계가 설정됩니다.
일종의 완전 이진 트리이기 때문에 이진 검색 트리의 부모-자식 관계와 유사합니다.
- 왼쪽 자식 인덱스 = 부모 인덱스 * 2
- 오른쪽 자식 인덱스 = (부모 인덱스 * 2) + 1
- 부모 인덱스 = Math.floor(자식의 인덱스 / 2);
끼워 넣다
붙여넣기도 비슷하지만 일단 마지막 노드에 입력한 값을 이동시켜 붙여넣습니다.
이때 재귀든 루프든 부모노드를 체크하여 입력값이 부모노드보다 작거나 큰지 위치를 계속해서 실행하여 정렬한다.
최소 힙 구현 시 삽입 프로세스 고려
// 최대 힙이면 반대 계산 결과를 적용한다.
...
heappush(value) {
this.heap.push(value);
let curIdx = this.heap.length - 1;
let parIdx = (curIdx / 2) >> 0;
// 최소힙이므로 부모노드가 제일 작아야 한다.
즉 부모노드가 현재노드보다 큰 지 검사하며 반복한다.
while(curIdx > 1 && this.heap(parIdx) > this.heap(curIdx)) {
( this.heap(parIdx), this.heap(curIdx) ) = ( this.heap(curIdx), this.heap(parIdx) );
// 구조분해 할당을 이용해 부모와 자식을 swap 한다.
따로 함수로 빼주어 작성해도 좋다.
curIdx = parIdx;
parIdx = (curIdx / 2) >> 0;
}
}
끄다
우선 힙에서는 최소 힙이든 최대 힙이든 항상 루트 노드를 먼저 플러시해야 합니다.
언로드 후 남은 공간은 마지막 노드, 즉 배열의 끝에 있는 값을 가져옵니다.
그런 다음 루트 노드에서 다시 재정렬합니다.
최소 힙에서 제거하는 과정을 코드로 보면,
...
heappop() {
const min = this.heap(1); // 배열 첫 원소를 비워두므로 root는 heap(1)에 항상 위치한다.
if(this.heap.length <= 2) this.heap = ( null );
else this.heap(1) = this.heap.pop();
// 배열 마지막 원소를 root 위치에 먼저 배치하는 과정이다.
// if-else로 분기되는 이유는 추후 heap이 비었는지 아닌지 확인하기 위해 size 체크 함수를 만들때 -1을 통해 0을 만들어주기 때문.
let curIdx = 1;
let leftIdx = curIdx * 2;
let rightIdx = curIdx * 2 + 1;
if(!
this.heap(leftIdx)) return min;
// 왼쪽 자식이 없다는 것은 오른쪽 자식도 없는, 즉 루트만 있는 상태이므로 바로 반환!
if(!
this.heap(rightIdx)) {
if(this.heap(leftIdx) < this.heap(curIdx)) {
( this.heap(leftIdx), this.heap(curIdx) ) = ( this.heap(curIdx), this.heap(leftIdx) );
// 오른쪽 자식이 없다면 왼쪽 자식하나만 있다는 것을 의미한다.
}
return min;
}
// 위에 조건에 걸리지 않는 경우 왼쪽과 오른쪽 자식이 모두 있는 경우이다.
// 따라서 현재 노드가 왼쪽 또는 오른쪽 보다 큰 지 작은지를 검사하며 반복한다.
while(this.heap(leftIdx) < this.heap(curIdx) || this.heap(rightIdx) < this.heap(curIdx)) {
// 왼쪽과 오른쪽 자식 중에 더 작은 값과 현재 노드를 교체하면 된다.
const minIdx = this.heap(leftIdx) > this.heap(rightIdx) ? rightIdx : leftIdx;
( this.heap(minIdx), this.heap(curIdx) ) = ( this.heap(curIdx), this.heap(minIdx) );
curIdx = minIdx;
leftIdx = curIdx * 2;
rightIdx = curIdx * 2 + 1;
}
return min;
}
전체 코드
삽입 및 삭제의 두 가지 핵심 논리 구현을 완료했습니다.
나머지는 지우지 않고 현재 힙 크기와 값에 대해 알려주는 도우미 함수를 구현합니다.
주석이 없는 전체 코드는 다음과 같습니다.
class MinHeap {
constructor() {
this.heap = ( null );
}
size() {
return this.heap.length - 1;
}
getMin() {
return this.heap(1) ? this.heap(1) : null;
}
swap(a, b) {
( this.heap(a), this.heap(b) ) = ( this.heap(b), this.heap(a) );
}
heappush(value) {
this.heap.push(value);
let curIdx = this.heap.length - 1;
let parIdx = (curIdx / 2) >> 0;
while(curIdx > 1 && this.heap(parIdx) > this.heap(curIdx)) {
this.swap(parIdx, curIdx)
curIdx = parIdx;
parIdx = (curIdx / 2) >> 0;
}
}
heappop() {
const min = this.heap(1);
if(this.heap.length <= 2) this.heap = ( null );
else this.heap(1) = this.heap.pop();
let curIdx = 1;
let leftIdx = curIdx * 2;
let rightIdx = curIdx * 2 + 1;
if(!
this.heap(leftIdx)) return min;
if(!
this.heap(rightIdx)) {
if(this.heap(leftIdx) < this.heap(curIdx)) {
this.swap(leftIdx, curIdx);
}
return min;
}
while(this.heap(leftIdx) < this.heap(curIdx) || this.heap(rightIdx) < this.heap(curIdx)) {
const minIdx = this.heap(leftIdx) > this.heap(rightIdx) ? rightIdx : leftIdx;
this.swap(minIdx, curIdx);
curIdx = minIdx;
leftIdx = curIdx * 2;
rightIdx = curIdx * 2 + 1;
}
return min;
}
}