[자료구조 공부] 힙
힙
힙 (Heap) 은 트리와 비슷한 자료 구조의 일종으로, 최대 힙의 경우 부모가 자식보다 크고 최소 힙의 경우 보모가 자식보다 작아요. 이러한 힙의 특성은 자료를 정렬하는데 유용하답니다. 힙은 자식에 대한 포인터를 갖는 대신에 배열 을 사용해 자료를 저장합니다. 힙을 사용하면 부모와 자식 간의 관계를 쉽게 정의 할 수 있기에, 배열에서 힙 노드의 자식 위치(인덱스)를 쉽게 계산할 수 있죠.
힙 에는 다양한 수의 자식을 갖는 다양한 종류가 있습니다. 힙은 배열을 사용해 자료를 저장하기 때문에 배열의 인덱스는 각 항목의 차수/높이를 정의해요. 첫번 째 배열 항목을 루트로 설정한 다음 각 왼쪽 항목과 오른쪽 항목을 순서대로 채움으로써 이진 힙 을 만들 수 있습니다.
최대 힙 은 부모가 모든 자식보다 항상 큰 힙입니다.. 그림과 같은 이진 힙이 존재할 때, 최대 힙의 배열은 [100, 19, 36, 17, 3, 25, 1, 2, 7]
최소 힙 은 부모가 모든 자식보다 항상 작은 힙입니다.. 그림과 같은 이진 힙이 존재할 때, 최소 힙의 배열은 [1, 2, 3, 17, 19, 36, 7, 25, 100]
이진 힙 (Binary Heap)
이진 힙 (Binary Heap) 의 경우 힙을 나타내기 위해 배열이 사용되는데 다음과 같이 인덱스를 사용해요. 이 때, N은 노드의 인덱스입니다.
자신 노드 : N
부모 노드 : (N - 1) / 2
왼쪽 자식 노드 : 2 n + 1
오른쪽 자식 노드 : 2 n + 2
// Binary Heap
function Heap() {
this.items = [];
this.swap = (index1, index2) => {
[this.items[index1], this.items[index2]] = [
this.items[index2],
this.items[index1],
];
};
this.parentIndex = (index) => {
return Math.floor((index - 1) / 2);
};
this.leftChildIndex = (index) => {
return index * 2 + 1;
};
this.rightChildIndex = (index) => {
return index * 2 + 2;
};
this.parent = (index) => {
return this.items[this.parentIndex(index)];
};
this.leftChild = (index) => {
return this.items[this.leftChildIndex(index)];
};
this.rightChild = (index) => {
return this.items[this.rightChildIndex(index)];
};
this.peek = (item) => {
return this.items[0];
};
this.size = () => {
return this.items.length;
};
}삼투 과정
항목을 추가하거나 삭제할 때는 힙의 구조가 유지 되어야 합니다. 이를 위해 항목 간에 교환이 일어나서 마치 비누 거품이 위로 올라가듯이 힙의 꼭대기로 점차 올라가야 합니다. 마찬가지로 일부 항목들은 힙의 구조를 유지하기 위해 올바른 위치로 마치 비누 거품이 땅으로 내려가듯이 내려가야 합니다. 이러한 노드 간 전파의 시간 복잡도는 O(log2(n))입니다.
12, 2, 23, 4, 13 순으로 값을 최소 힙에 삽입해 봅시다.
- 첫 번째 노드 12를 삽입한다.
- 새로운 노드 2를 삽입한다.
- 최소 힙 구조를 유지하기 위해 노드 2가 최상위로 올라간다.
- 새로운 노드 23을 삽입한다.
- 새로운 노드 4를 삽입한다.
- 최소 힙 구조를 유지하기 위해 노드 12와 노드 4의 위치를 교환한다.
- 새로운 노드 12를 삽입한다.
삼투의 위 아래 이동을 구현하기 위해서는 취소 힙 구조의 제일 위에 최솟값 항목이 위치할 때까지 항목들을 교환해야 합니다.
function MinHeap() {
this.items = [];
this.bubbleDown = () => {
let index = 0;
while (this.leftChild(index) && this.leftChild(index) < this.items[index]) {
let smallerIndex = this.leftChildIndex(index);
if (
this.rightChile(index) &&
this.rightChild(index) < this.items[smallerIndex]
) {
smallerIndex = this.rightChildIndex(index);
}
this.swap(smallerIndex, index);
index = smallerIndex;
}
};
this.bubbleUp = () => {
let index = this.items.length - 1;
while (this.parent(index) && this.parent(index) > this.items[index]) {
this.swap(this.parentIndex(index), index);
index = this.parentIndex(index);
}
};
}최대 힙 구현은 최소 힙 구현과 비교자 부분만 달라요. 아래로 이동하기 위해서 최대 힙 노드는 자식이 자신보다 큰 경우에 교환합니다. 마찬가지로 위로 이동하기 위해서 가장 최근에 삽입된 노드는 부모 노드가 자신보다 작은 경우에 부모 노드와 교환됩니다.
힙 정렬
힙 클래스를 생성한 뒤엔 힙을 사용해 정렬 하는 것이 꽤 간단합니다. 힙이 빈 상태가 될 때까지 힙 배열을 pop() 하여 꺼낸 객체를 저장하면 정렬된 배열을 얻을 수 있죠. 이를 힙 정렬이라 한답니다. 힙 정렬의 시간 복잡도는 빠른 정렬이나 병합 정렬과 같은 O(log2(n))입니다.
오름차순 정렬 (최소 힙)
const myMinHeap = new MinHeap();
myMinHeap.add(12);
myMinHeap.add(2);
myMinHeap.add(23);
myMinHeap.add(4);
myMinHeap.add(13);
myMinHeap.items; // [2, 4, 23, 12, 13]위는 최소 힙 클래스를 통해 만들어진 배열입니다. 이제 이 최소 힙 배열을 pop() 을 통해 항목들을 꺼내어 힙을 재구성할거에요. 최종적으로 힙이 빈 상태가 되면 정렬 이 완료된 것입니다.
console.log(myMinHeap.poll()); // 2
console.log(myMinHeap.poll()); // 4
console.log(myMinHeap.poll()); // 12
console.log(myMinHeap.poll()); // 13
console.log(myMinHeap.poll()); // 23
위에서 보듯이 항목을 꺼내는 과정에서 삼투도 같이 일어나고 마침내 정렬이 끝납니다.내림차순 정렬 (최대 힙)도 마찬가지로 하면 됩니다.
const myMaxHeap = new MaxHeap();
myMaxHeap.add(12);
myMaxHeap.add(2);
myMaxHeap.add(23);
myMaxHeap.add(4);
myMaxHeap.add(13);
myMaxHeap.items; // [23, 13, 12, 2, 4]최소 힙과 마찬가지로 위는 최대 힙 클래스를 통해 만들어진 배열입니다. 이 최대 힙 배열도 항목들을 꺼냄에 따라 최대 힙이 재구성돼요. 그리고 최종적으로 최대 힙이 빈 경우 정렬 이 완료됩니다.
console.log(myMaxHeap.poll()); // 23
console.log(myMaxHeap.poll()); // 13
console.log(myMaxHeap.poll()); // 12
console.log(myMaxHeap.poll()); // 2
console.log(myMaxHeap.poll()); // 4출처: https://overcome-the-limits.tistory.com/9#알고리즘에서의-해시-테이블
출처 : https://velog.io/@ijaesin/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-3
