힙(Heap)
힙 자료구조란 완전이진트리 자료구조를 활용해 최댓값, 최솟값을 빠르게 찾아낼 수 있도록 해주는 자료구조이다. 힙 자료구조를 구성하는 알고리즘에 따라서 최댓값을 빠르게 찾아내도록 하는 최대 힙, 최솟값을 빠르게 찾아낼 수 있도록 하는 최소 힙 자료구조가 존재한다. 힙 자료구조를 사용하면 데이터를 우선순위를 통해 입출력 할 수 있도록 하는 우선순위 큐(Priority Queue)를 구현할 수 있다.
최대 힙(Max Heap)
최대 힙 자료구조는 부모 Node가 반드시 그의 자식 Node들보다 값이 커야만 한다는 규칙을 가지고 있다. 최대힙을 구현하기 위해서는 다음과 같은 규칙을 따라야 한다.
- 각각의 부모 Node는 최대 2명의 자식 Node들을 가질 수 있다.
- 자식 Node의 값은 반드시 그 부모 Node보다 작아야 한다.
- 형제 Node들 사이에는 어떤 관계도 존재하지 않는다.
- 최대 힙 자료구조는 완전이진트리 구조를 유지해야한다. (반드시 자식 Node들은 트리의 구성 순서대로 채워져야만 하며, 다음 Node의 자식으로 추가되기 위해서는 이전 Node를 포화시켜야 한다.)
힙의 경우 완전이진트리구조를 따르기 때문에, 규칙만 잘 지켜 데이터를 삽입하기만 한다면 트리 자료구조를 만들지 않고도 힙을 구현해낼 수 있다. 우리는 배열을 사용해서 힙 자료구조를 구현해 사용할 수도 있다. 위의 트리구조를 배열을 통해서 구현하면 다음과 같다.
배열을 통해서 힙 구조를 만들기 위해서는 다음과 같이 데이터를 삽입한다.
- Root Node는 반드시 첫 번째에 삽입된다.
- 그 후 해당 부모 Node의 왼쪽 자식 Node들을 삽입한다.
- 해당 부모 Node의 오른족 자식 Node들을 삽입한다.
이러한 규칙을 지킬 경우 어떤 한 Node의 index를 n이라 하면 다음과 같은 index 규칙을 가지게 된다.
- 왼쪽 자식 Node의 index : 2n + 1
- 오른쪽 자식 Node의 index : 2n + 2
- 해당 Node의 부모 Node : floor (n - 1 / 2)
최대 힙구현
위와 같이 배열을 통해 최대 힙을 구현할 수 있다는 것을 알아봤으니 최대 힙을 구현하고 최대 힙을 활용할 수 있도록 하는 메소드를 구현해보도록 하자.
class BMH {
constructor() {
this.values = [];
}
}
// Binary Max Heap의 경우 배열로 구현할 것이므로
// 배열을 단순히 선언해주는 것 만으로 충분하다.
최대 힙 자료구조의 메소드에는 최대 힙 자료구조의 규칙에 맞도록 데이터를 삽입해주는 insert 메소드와 최대 힙에서 최댓값을 뽑아내어 사용할 수 있게 해주는 remove 메소드 두 개를 구현한다. 이 insert-remove 메소드에는 단순히 자료를 삽입하고 제거하는 과정만이 존재하는 것이 아니라 삽입, 제거 후에도 현재 유지하고 있는 힙 자료구조가 규칙에 맞도록 데이터들을 다시 재조작하는 과정들이 포함된다.
insert(value)
insert 메소드는 최대 힙 자료구조에 새로운 값을 추가해 적절한 위치에 자리하도록 만들어주는 메소드이다.
insert 메소드는 다음과 같은 과정을 거친다.
- 새로운 값을 힙의 맨 뒤에 삽입한다.
- 맨 뒤에 삽입된 힙을 기준으로 해당 힙의 부모 노드와 값을 비교한다.
- 만약 값이 올바르다면 해당 위치에 그대로 두고, 그렇지 않다면 부모와의 위치를 교환한다.
- 값이 제 위치를 찾을 때까지 비교-교환 과정을 계속한다.
이 2-4번의 위치 재조정 과정을 'bubble-up'이라고 부르기도 한다.
1. value : 새롭게 삽입할 값
return : 새롭게 값이 추가된 힙
insert(value) {
this.values.push(value);
// 힙의 마지막에 값을 삽입한다.
let curIdx = this.values.length - 1;
let parentIdx = Math.floor((curIdx - 1) / 2);
// 현재 idx 와 부모의 idx를 선언
while(this.values[parentIdx] &&
this.values[curIdx] > this.values[parentIdx]) {
// 부모의 값이 존재하고
// 부모의 값이 새로 추가된 값보다 작을 경우
[this.values[parentIdx], this.values[curIdx] =
[this.values[curIdx], this.values[parentIdx]];
// 위치를 서로 교환한다.
curIdx = parentIdx;
parentIdx = Math.floor((curIdx - 1) / 2);
// 인덱스를 새롭게 교체하고
// 이에 맞게 새로운 부모 idx를 뽑는다.
}
return this.values
}
BMH.insert(9);
// 추가되기 이전: [10, 4, 8, 1, 3, 6, 7]
// return : [10, 9, 8, 4, 3, 6, 7, 1]
remove()
remove 메소드는 insert메소드와 반대로 힙 자료구조에서 값을 하나 출력한다. 이때, 이 값은 반드시 힙 자료구조의 최상단(Root)에 위치해 있는 값을 출력한다.(최대힙자료구조에서 이 값은 최댓값이 된다.) 최댓값을 힙 자료구조에서 뽑아내었기 때문에, 이때에도 힙 자료구조의 재조정이 필요하다. 이때 이 재조정 과정을 'sink-down' 이라고 부른다. remove 메소드는 다음과 같은 과정을 거친다.
- 힙 자료구조에서 Root 값을 뽑아낸다.
- 가장 마지막에 추가된 값을 새로운 Root로 할당한다.
- 새로운 Root와 그의 자식 node들과 값을 비교한다.
- 만약 자식들 중 하나 라도 Root보다 값이 크다면 서로 위치를 교체한다.
- 자리가 재조정될 때까지 3-4의 과정을 반복한다.
return: 힙에서 뽑아낸 최댓값
remove() {
const result = this.values[0];
this.values[0] = this.values.pop();
// 기존 root는 출력을 위해 저장하고
// 제일 마지막 값을 뽑아 새로운 root로 할당한다.
let rootIdx = 0;
let leftChild = 2 * rootIdx + 1;
let rightChild = 2 * rootIdx + 2;
// idx 선언
while(this.values[rootIdx] < this.values[leftChild] ||
this.values[rootIdx] < this.values[rightChild]) {
// 자식들 중 하나라도 값이 자신 보다 클 경우
if(this.values[rootIdx] < this.values[leftChild]) {
[this.values[rootIdx], this.values[leftChild]] =
[this.values[lefttIdx], this.values[rootIdx]];
rootIdx = leftChild;
} else {
[this.values[rootIdx], this.values[rightChild]] =
[this.values[rightChild], this.values[rootIdx]];
rootIdx = rightChild;
}
// 경우에 맞게 값을 교환해주고
// idx도 새롭게 교체한다.
leftChild = 2 * rootIdx + 1;
rightChild = 2 * rootIdx + 2;
// 자식들의 idx도 이에 맞게 지정한다.
if (!this.values[leftChild]) break;
// 만약 leftChild 가 없으면 더 탐색할 자식이 없는 것이다.
// 탐색을 종료한다.
if (!this.values[rightChild]) rightChild = leftChild;
// 아직 탐색하지 못한 leftChild가 남아있을 수 있다.
return result;
}
BMH.remove()
// 제거되기 이전: [10, 9, 8, 4, 3, 6, 7, 1]
// 제거된 이후: [ 9, 4, 8, 1, 3, 6, 7]
// return : 10
