일단 힙(Heap)이라는 단어가 매우 생소하므로, 이에 대하여 익숙해질 필요가 있다. Heap의 사전적 의미는 무엇인가 차곡차곡 쌓여있는 더미
를 의미한다. 건초 더미, 모래 더미, 산 더미처럼 말이다. 이를 통해, 자료 구조에서 힙(Heap)은 모래 더미처럼 삼각형으로 쌓여 있는 구조임을 추측할 수 있다.
참고로 메모리 영역 Heap
과 자료구조 Heap
은 서로 상관관계가 없다. 메모리 영역 Stack
은 자료구조 Stack
를 사용하기에 Stack
이라고 불리는 것과 달리, 메모리 영역 Heap
은 자료구조 Heap
을 사용하지 않는다. 단지, 영단어 힙(heap)은 '무엇인가 차곡차곡 쌓여있는 더미'라는 뜻을 지니고 있어, 사용 가능한 메모리 풀을 관용적으로 ‘Heap’이라고 불렀다고 한다.
https://softwareengineering.stackexchange.com/questions/186705/why-is-the-main-memory-for-object-allocation-called-the-heap
Several authors began about 1975 to call the pool of available memory a "heap." But in the present series of books, we will use that word only in its more traditional sense related to priority queues. (The Art of Computer Programming - Fundamental Algorithms, 3rd ed., p. 435)
몇몇 저자들은 1975년경에 사용 가능한 메모리 풀을 "힙"이라고 부르기 시작했습니다.그러나 현재 시리즈의 책에서는 우선 순위 대기열과 관련된 보다 전통적인 의미로만 이 단어를 사용할 것입니다. (컴퓨터 프로그래밍의 기술 - 기본 알고리즘, 3판, 435페이지)
힙(Heap)도 트리 자료 구조의 일종이다. 힙이 다른 트리와는 달리 데이터가 한 쪽으로 쏠리지 않고 모래 더미처럼 삼각형의 형태를 유지할 수 있는 이유는, 부모 노드가 항상 자식 노드들보다 크거나(최대이진힙) 작아야(최소이진힙) 한다는 규칙이 있고 형제 노드들 간의 관계에는 그러한 규칙이 없기 때문이다.
힙에도 여러 종류가 있는데 이번 포스팅에서는 그 중에서도 이진 힙(Binary Heap)에 집중해서 살펴보려고 한다.
이진 힙
아래 이미지와 같은 트리가 최대 이진 힙(MaxBinaryHeap)
이다. 부모 노드들이 항상 자식 노드들보다 크며, 형제 노드들 간에는 특별한 순서가 없다.
이진 힙
은 자료구조에서 자주 사용되는 우선순위 큐(Priority Queues)
를 코딩할 때 사용된다.이진 힙
은 그래프 순회(Graph Traversal)
알고리즘 등에서도 자주 사용된다.left child
인덱스 : 2n+1right child
인덱스 : 2n+2parent
인덱스 : Math.floor((n-1)/2)최대이진힙(MaxBinaryHeap)
클래스만 만들어보므로, 이하 메서드는 모두 최대이진힙의 메서드이다.class MaxBinaryHeap {
constructor() {
this.values = [];
}
}
this.values.push(element);
this.bubbleUp();
[41,39,33,18,27,12]
이진 힙 데이터에 55
를 Insert했을 때 발생하는 과정을 시각화한 것이다.insert(element) {
// 삽입하려는 요소를 기존 배열의 끝에 push한다.
this.values.push(element);
// bubbleUp 메서드 호출
this.bubbleUp();
}
bubbleUp() {
// 삽입한 요소의 현재 인덱스를 idx 변수로 정의한다.
let idx = this.values.length - 1;
// idx는 element의 인덱스이며, idx가 0이 되기 전까지 반복문을 돌린다.
// 인덱스 0이 되면 삽입한 요소가 이미 root 자리에 도착했다는 것이므로 더 올라갈 곳이 없다.
while (idx > 0) {
// 삽입한 요소와 비교해야 하는 부모 요소를 찾아서 변수로 할당한다.
// 위에서 살펴본 자식의 위치로 부모 위치 찾는 공식(n-1/2)을 사용한다.
const parentIdx = Math.floor((idx - 1) / 2);
// 삽입한 요소보다 비교하려는 부모 요소가 같거나 크면 자리를 바꿀 필요가 없으므로 반복문 깨기
if (this.values[idx] <= this.values[parentIdx]) break;
// 삽입한 요소보다 비교하려는 부모 요소가 작으면 자리를 서로 바꿔준다.
this.values[parentIdx] = this.values[idx];
// 자리를 바꿨으니 인덱스도 서로 바꾼다.
idx = parentIdx;
}
}
[41,39,33,18,27,12]
이진 힙에서 ExtractMax()를 했을 때, 발생하는 과정을 시각화한 것이다.extractMax() {
// 이진 힙의 max와 end 변수 정의
const max = this.values[0];
const end = this.values.pop();
// pop한 후에 남은 요소가 있으면
if (this.values.length > 0) {
// root 자리에 가장 최근에 삽입됐던 end를 넣고
this.values[0] = end;
// root 자리에 올라간 end의 sinkDown()을 시작한다.
this.sinkDown();
}
// pop한 후에 남은 요소가 없으면 바로 return하고 종료한다.
return max;
}
sinkDown() {
let idx = 0;
const length = this.values.length;
while (true) {
// sinkDown할 주인공 element 변수 설정
const element = this.values[idx];
// 부모 위치로부터 자식 위치 찾는 공식을 이용해서 left, right 자식의 위치를 구한다.
const leftChildIdx = 2 * idx + 1;
const rightChildIdx = 2 * idx + 2;
let leftChild;
let rightChild;
let swap = null;
// 찾은 자식의 인덱스가 실제로 존재할 때에만, 그 값을 변수로 할당한다.
// 먼저 leftChild 변수가 element와 비교해서 더 크면, 그 인덱스를 swap에 할당한다.
if (leftChildIdx < length) {
leftChild = this.values[leftChildIdx];
if (leftChild > element) {
swap = leftChildIdx;
}
}
// rightChild도 위에서 leftChild에게 한 것처럼, 비교하고 swap에 할당하려고 하는데,
// leftChildIdx가 존재하지 않아서 swap이 여전히 null일 수 있으므로
// 그러한 경우를 고려하여 조건을 추가한다.
// swap이 null이고 rightChild가 element보다 크거나,
// swap에 값(leftChildIdx)이 있고 rightChild가 leftChild보다 큰 경우에,
// 그 인덱스를 swap에 할당한다.
if (rightChildIdx < length) {
rightChild = this.values[rightChildIdx];
if ((swap === null && rightChild > element) || (swap !== null && rightChild > leftChild)) {
swap = rightChildIdx;
}
}
// 만약 여전히 swap이 null이면 element는 이미 제 자리에 있는 것이므로 반복문을 break
if (swap === null) break;
// 그렇지 않고 swap 값이 있다면, element와 swap할 대상의 자리를 서로 바꾼다.
[this.values[idx], this.values[swap]] = [this.values[swap], this.values[idx]];
// while문의 다음 턴에서 사용할 element의 새 인덱스를 swap으로 재할당해서 최신화해준다.
idx = swap;
}
}
최소이진힙
으로 구현하고 value 외에도 priority 클래스를 함께 담기 위해 Node 클래스를 사용한다. 코드는 아래와 같다. 로직은 위의 이진힙과 거의 같고, 다른 점은 주석을 달았다.class Node { // value 외에도 priority 클래스를 함께 담기 위해 Node 클래스를 사용한다.
constructor(val, priority) {
this.val = val;
this.priority = priority;
}
}
class PriorityQueue {
constructor() {
this.values = [];
}
enqueue(val, priority) { // 이진 힙에서 만든 Insert 메서드에서 이름을 바꿨다.
const newNode = new Node(val, priority);
this.values.push(newNode);
this.bubbleUp();
}
bubbleUp() {
let idx = this.values.length - 1;
while (idx > 0) {
const parentIdx = Math.floor((idx - 1) / 2);
if (this.values[idx].priority >= this.values[parentIdx].priority) break;
[this.values[idx], this.values[parentIdx]] = [this.values[parentIdx], this.values[idx]];
idx = parentIdx;
}
}
dequeue() { // 이진 힙에서 만든 extractMax 메서드에서 이름을 바꿨다.
const min = this.values[0];
const end = this.values.pop();
if (this.values.length > 0) {
this.values[0] = end;
this.sinkDown();
}
return min;
}
sinkDown() {
let idx = 0;
const length = this.values.length;
const element = this.values[0];
while (true) {
const leftChildIdx = 2 * idx + 1;
const rightChildIdx = 2 * idx + 2;
let leftChild;
let rightChild;
let swap = null;
if (leftChildIdx < length) {
leftChild = this.values[leftChildIdx];
// 최소이진힙이라 최대이진힙과 달리 부등호 방향이 반대고, 비교하는 값은 priority 프로퍼티다.
if (leftChild.priority < element.priority) {
swap = leftChildIdx;
}
}
if (rightChildIdx < length) {
rightChild = this.values[rightChildIdx];
if ((swap === null && rightChild.priority < element.priority) || (swap !== null && rightChild.priority < leftChild.priority)) {
swap = rightChildIdx;
}
}
if (swap === null) break;
this.values[idx] = this.values[swap];
this.values[swap] = element;
idx = swap;
}
}
}