자료구조 힙 (heap)
힙은 여러 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 완전 이진 트리를 말한다.
가장 작은 요소가 루트노드에 있는 최소힙,
가장 큰 요소가 루트노드에 있는 최대힙이다.
-
최대힙 : 부모노드의 값은 자식노드의 값보다 항상 큰 규칙을 지키는 힙을 말한다.
-
최소힙 : 부모노드의 값은 자식노드의 값보다 항상 작은 규칙을 지키는 힙을 말한다.
이를 통해 요소 중 가장 작은 값을 O(1)만에 찾을 수 있다.
힙의 데이터 삽입
여기서 규칙이란 최소힙, 최대힙의 규칙을 의미한다.
1. 리프노드에 삽입할 노드를 삽입한다.
2. 해당노드와 부모노드를 서로 비교한다.
3. "규칙"에 맞으면 그대로 두고, 그렇지 않으면 부모노드와 교환한다.
4. 규칙에 맞을 때까지 3번 과정을 반복한다.
힙의 데이터 삭제
루트 노드만을 제거할 수 있으며 다음과 같은 과정이 일어난다.
1. 루트 노드를 제거한다.
2. 루트 자리에 가장 마지막 노드를 삽입한다.
3. 올라간 노드와 그 자식 노드를 비교한다.
4. 규칙을 만족한다면 그대로 두고, 그렇지 않은 경우 자식 노드와 교환한다.
이진 탐색트리와의 차이점
이진 탐색트리는 탐색을 쉽게 하기 위해 왼쪽이 더 작고
오른쪽이 큰 값으로 꼭 구성이 되어야하지만
힙은 그렇지 않다.시간복잡도
- 참조 (최대 또는 최소값을 참조) : O(1) (루트노드만 참조한다.)
- 탐색 : O(n)
- 삽입/삭제 : O(logn)
자바스크립트 구현 (Max heap)
class MaxHeap { // 최대힙
arr = []
#reheapUp (index) {
if (index > 0) {
const parentindex = Math.floor((index - 1) / 2);
if (this.arr[index] > this.arr[parrentIndex]) {
// 값 바꾸기
const temp = this.arr[index];
this.arr[index] = this.arr[parentIndex];
this.arr[parentIndex] = temp;
this.#reheapUp(parentIndex);
}
}
}
insert(value) {
const index = this.arr.length;
this.arr[index] = value;
this.#reheapUp(index);
}
#reheapDown(index) {
const leftIndex = index * 2 + 1;
if (leftIndex < this.arr.length) {
const rightIndex = index * 2 + 2;
const bigger = this.arr[leftIndex] > this.arr[rightIndex] ? leftIndex : rightIndex;
if (this.arr[index] < this.arr[bigger]) {
cons temp = this.arr[index];
this.arr[index] = this.arr[bigger];
this.arr[bigger] = temp;
this.#reheapDown(bigger);
}
}
}
remove() { // 루트를 삭제
if (this.arr.length === 0) {
return false;
}
if (this.arr.length === 1) {
return this.arr.pop();
}
const root = this.arr[0];
this.arr[0] = this.arr.pop();
this.#reheapDown(0);
return root;
}
sort() { // 힙 정렬
const sortedArray = []
while (this.arr.length > 0) {
sortedArray.push(this.remove());
}
return sortedArray;
}
search(value) {
for (let i = 0; i < this.arr.length; i ++) {
if (this.arr[i] === value) {
return i;
}
}
return null;
}
update(value, newValue) {
const index = this.search(value);
if (index === null) {
return false;
}
this.arr[index] = newValue;
for (let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i--) { // O(1/2n)
this.#heapify(i); // O(1)
}
}
removeValue(value) { // 특정 값 삭제
const index = this.search(value);
if (index === null) {
return false;
}
this.arr.splice(index, 1);
for (let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i --) { // 0(1/2n)
this.#heapify(i); // 0(1)
}
}
heapify(index) {
const leftIndex = index * 2 + 1;
const rightIndex = index * 2 + 2;
const bigger = (this.arr[leftIndex] || 0) > (this.arr[rightIndex] || 0)
? leftIndex : rightIndex;
console.log(index, this.arr[index], this.arr[bigger]);
if (this.arr[index] < this.arr[bigger];
const temp = this.arr[index];
this.arr[index] = this.arr[bigger];
this.arr[bigger] = temp;
}
}
}참고
인프런 강의 _ CS 지식의 정석 | 디자인패턴 네트워크 운영체제 데이터베이스 자료구조대시보드
참고
javascript-algoruthms github
