힙(Heap)이란?
힙 트리(Heap Tree), 보통 줄여서 힙(Heap)이라고 부른다.
힙은 부모 노드의 값이 항상 하위 노드의 값보다 작거나 큰 구조의 트리이다.
트리의 일종으로 완전 이진 트리(트리 문서 참고)이면서, 부모 노드의 값이 항상 하위 노드의 값보다 작거나 큰 구조의 트리이다.
힙의 사전적인 의미가 '쌓아 올린 더미'인 것 처럼, 데이터가 위에서부터 규칙적으로 쌓여있는 구조이다.
데이터가 정렬되는 방식에 따라 최대 힙(Max Heap), 최소 힙(Min Heap)으로 구분된다.
힙은 노드를 정렬하는 방식에 따라 최대 힙(Max Heap), 최소 힙(Min Heap)으로 나뉜다.
최대 힙 Max Heap
부모 노드의 값이 항상 하위 노드의 값보다 크다.
최소 힙 Min Heap
부모 노드의 값이 항상 하위 노드의 값보다 작다.
힙은 우선 순위 큐를 구현하는 가장 효율적인 자료구조이다.
최소값/최대값이 항상 배열의 첫번째 요소에 저장되므로 쉽고 빠르게(O(1)시간) 최소값/최대값을 찾을 수 있다.
삽입/삭제는 루트 노드에 대해서만 가능하지만 O(log n)으로 매우 빠르다.
이런 특성은 우선 순위 큐(큐 문서 참고)를 구현하는데 매우 유리하여, 구현하는데 가장 효율적인 자료구조로 알려져있다.
인터페이스
- insert(key) - 노드를 추가한다.
- remove() - root노드를 삭제한다.(큐 자료구조의 pop()과 유사)
구현 - JavaScript에서의 힙
힙은 완전 이진 트리이므로 배열로 효율적으로 구현할 수 있다.
배열의 index와 노드의 위치를 맵핑해서 사용한다.
깊이는 위에서 아래로, 왼쪽에서 오른쪽 방향으로 차례대로 index가 할당된다.
규칙적으로 index가 할당되므로 아래와 같은 규칙성이 있다.
- 왼쪽 자식의 index: 부모 idnex * 2
- 오른쪽 자식의 index = 부모 idnex * 2 + 1
- 부모의 인덱스 = 자식 index / 2 (몫만 사용)
최대힙 Max Heap
class MaxHeapTree {
// 편리한 구현을 위해 index는 1부터 사용
constructor() {
this._items = [""];
}
get items() {
return this._items;
}
get root() {
return _items[1];
}
/**
* 구현 절차
* - 1) 힙의 가장 마지막 위치(배열의 마지막)에 노드에 추가한다
* - 2) 힙의 조건을 만족시키도록 연산 (부모노드와 교환)
* - 새로 추가한 노드와 부모 노드를 비교하여 부모노드가 더 작으면 위치를 바꾼다
* - (더 큰 부모노드가 없을때까지 반복)
*/
insert(key) {
this._items.push(key);
this._allignAfterInsert();
}
/**
* 힙의 삭제는 루트 노드 삭제만 구현한다. (queue의 pop 연산이라고 생각하면 됨)
*
* 구현 절차
* - 1) 루트노드를 제거
* - 2) 제거한 루트노드자리에 마지막 노드를 삽입
* - 3) 힙의 조건을 만족시키도록 연산
* - 루트노드의 자식노드 중 더 큰 값과 교환한다.
* - (더 큰 자식노드가 없을때까지 반복)
*/
remove() {
this._items[1] = this._items.pop();
this._allignAfterRemove();
}
_allignAfterInsert() {
let childIndex = this._items.length - 1;
let child = this._items[childIndex];
let parentIndex = Math.floor(childIndex / 2) || 1;
let parent = this._items[parentIndex];
let newChildIndex;
while (parent < child) {
newChildIndex = parentIndex;
this._items[newChildIndex] = child;
this._items[childIndex] = parent;
parentIndex = Math.floor(newChildIndex / 2) || 1;
parent = this._items[parentIndex];
childIndex = newChildIndex;
}
}
_allignAfterRemove() {
let parentIndex = 1;
let parent = this._items[parentIndex];
let leftChild = this._items[parentIndex * 2];
let rightChild = this._items[parentIndex * 2 + 1];
let bigChild = leftChild > rightChild ? leftChild : rightChild;
let bigChildIndex = this._items.indexOf(bigChild);
let newParentIndex;
while (parent < bigChild) {
newParentIndex = bigChildIndex;
this._items[newParentIndex] = parent;
this._items[parentIndex] = bigChild;
leftChild = this._items[newParentIndex * 2];
rightChild = this._items[newParentIndex * 2 + 1];
bigChild = leftChild > rightChild ? leftChild : rightChild;
bigChildIndex = this._items.indexOf(bigChild);
parentIndex = newParentIndex;
}
}
}
// Test
it("MaxHeapTree 클래스는 잘 동작한다.", () => {
const heap = new MaxHeapTree();
heap.insert(9);
heap.insert(3);
heap.insert(5);
heap.insert(10);
heap.insert(6);
expect(heap.items).toEqual(["", 10, 9, 5, 3, 6]);
heap.insert(8);
expect(heap.items).toEqual(["", 10, 9, 8, 3, 6, 5]);
heap.remove();
expect(heap.items).toEqual(["", 9, 6, 8, 3, 5]);
heap.remove();
expect(heap.items).toEqual(["", 8, 6, 5, 3]);
});최소힙 Min Heap
class MinHeapTree {
// 편리한 구현을 위해 index는 1부터 사용
constructor() {
this._items = [""];
}
get items() {
return this._items;
}
get root() {
return _items[1];
}
/**
* 구현 절차
* - 1) 힙의 가장 마지막 위치(배열의 마지막)에 노드에 추가한다
* - 2) 힙의 조건을 만족시키도록 연산 (부모노드와 교환)
* - 새로 추가한 노드와 부모 노드를 비교하여 부모노드가 더 크면 위치를 바꾼다
* - (더 큰 부모노드가 없을때까지 반복)
*/
insert(key) {
this._items.push(key);
this._allignAfterInsert();
}
/**
* 힙의 삭제는 루트 노드 삭제만 구현한다. (queue의 pop 연산이라고 생각하면 됨)
*
* 구현 절차
* - 1) 루트노드를 제거
* - 2) 제거한 루트노드자리에 마지막 노드를 삽입
* - 3) 힙의 조건을 만족시키도록 연산
* - 루트노드의 자식노드 중 더 작은 값과 교환한다.
* - (더 작은 자식노드가 없을때까지 반복)
*/
remove() {
this._items[1] = this._items.pop();
this._allignAfterRemove();
}
_allignAfterInsert() {
let childIndex = this._items.length - 1;
let child = this._items[childIndex];
let parentIndex = Math.floor(childIndex / 2) || 1;
let parent = this._items[parentIndex];
let newChildIndex;
while (parent > child) {
newChildIndex = parentIndex;
this._items[newChildIndex] = child;
this._items[childIndex] = parent;
parentIndex = Math.floor(newChildIndex / 2) || 1;
parent = this._items[parentIndex];
childIndex = newChildIndex;
}
}
_allignAfterRemove() {
let parentIndex = 1;
let parent = this._items[parentIndex];
let leftChild = this._items[parentIndex * 2];
let rightChild = this._items[parentIndex * 2 + 1];
let smallChild = leftChild < rightChild ? leftChild : rightChild;
let smallChildIndex = this._items.indexOf(smallChild);
let newParentIndex;
while (parent > smallChild) {
newParentIndex = smallChildIndex;
this._items[newParentIndex] = parent;
this._items[parentIndex] = smallChild;
leftChild = this._items[newParentIndex * 2];
rightChild = this._items[newParentIndex * 2 + 1];
smallChild = leftChild < rightChild ? leftChild : rightChild;
smallChildIndex = this._items.indexOf(smallChild);
parentIndex = newParentIndex;
}
}
}
// Test
it("MinHeapTree 클래스는 잘 동작한다.", () => {
const heap = new MinHeapTree();
heap.insert(9);
heap.insert(3);
heap.insert(5);
heap.insert(10);
heap.insert(6);
expect(heap.items).toEqual(["", 3, 6, 5, 10, 9]);
heap.insert(2);
expect(heap.items).toEqual(["", 2, 6, 3, 10, 9, 5]);
heap.remove();
expect(heap.items).toEqual(["", 3, 6, 5, 10, 9]);
heap.remove();
expect(heap.items).toEqual(["", 5, 6, 9, 10]);
});활용 사례
- 우선순위 큐 구현 (가장효율적인 우선순위 큐 구현 자료구조)
- 무손실 압축 알고리즘인 허프만 코드
- 아디트야 바르가바, 『Hello Coding 그림으로 개념을 이해하는 알고리즘』, 김도형, 한빛미디어(2017)
- 스기우라 켄, 『그림으로 배우는 알고리즘』, 서재원, 영진(2016)
- 이소 히로시, 『모던 자바스크립트 입문』, 서재원, 길벗(2018)
- Martin Erwig, 『그들은 알고리즘을 알았을까?』, 송원형, 영진(2017)
- Loiane Groner, 『자바스크립트 자료 구조와 알고리즘』, 이일웅, PACKT-에이콘(2015)
글쓴이쿠스, Qus
직업은 소프트웨어 개발자.
기술로 사회문제를 해결하는 시빅해킹(Civic Hacking)에 관심이 많고,
이것저것 생각나는 것들을 글로 정리하는 것을 좋아합니다.
기술로 사회문제를 해결하는 시빅해킹(Civic Hacking)에 관심이 많고,
이것저것 생각나는 것들을 글로 정리하는 것을 좋아합니다.
'자료구조/알고리즘' 시리즈의 다른 이야기들