이진 힙(Binary Heaps)
목차
1. 힙 (Heaps) 소개
2. 힙 (Heaps) 정렬
3. 힙 : Insert 메소드 소개
4. 힙 : Insert 메소드 솔루션
5. 힙 : ExtractMax 메소드 소개
6. 힙 : ExtractMax 메소드 솔루션
7. 우선 순위 큐(Queue) 소개
8. 우선 순위 큐(Queue) 의사코드
9. 우선 순위 큐(Queue) 솔루션
10. 이진 힙의 빅오(BIG O)
1. 힙 (Heaps) 소개
슬라이드 : Binary Heaps (slides.com)
Binary Heaps
A presentation created with Slides.
cs.slides.com
이진 힙(Binary Heap)은 이진 탐색 트리(BST)와 매우 비슷하지만, 다른 규칙이 있다.
1. 최대 이진 힙(MaxBinaryHeap)에서는, 부모 노드가 항상 자식 노드보다 큰 값을 가진다.
2. 최소 이진 힙(MinBinaryHeap)은 부모 노드가 언제나 양쪽의 자식보다 작다.
3. 그리고 이진 힙의 각 노드는 언제나 최대 두 개의 자식을 가진다.
4. 하지만, 이진 탐색 트리와는 다르게 왼쪽과 오른쪽에는 순서가 존재하지 않는다. (형제들 사이에는 특별한 순서X)
5. 이진 탐색 트리는 노드를 한 쪽으로 치우치게 할 수 있지만,
이진 힙은 한 줄에서는 왼쪽 자식이 언제나 먼저 채워지기 때문에,
다음 레벨로 내려가기 전에 모든 left와 right가 다 채워짐 (언제나 가장 적은 공간을 차지함)
Q. 왜 힙(Heap)을 배워야 하는가?
1. 우선순위 큐(Priority Queues)에서 이진 힙(Binary Heap)이 사용된다.
자료구조에서 우선순위 큐는 자주 사용된다.
기본적으로 큐(Queue)는 요소를 추가하고 제거하면서 무언가의 순서를 추적하는 기능을 한다.
그리고 거기에 우선순위를 부여하게 된다. 즉, 각 요소에 대한 중요도를 부여해서 큐 안에 적절한 장소에 배치하게 된다.
2. 특히 그래프 순회(Graph Traversal Algorithms)라는 것에 자주 쓰인다.
힙은 여기서 보조용도로 사용된다.
2. 힙 (Heaps) 정렬
규칙
배열 안에 있는 모든(n) 인덱스에 대해,
왼쪽 자식은 2n+1에 저장되어 있고,
오른쪽 자식은 2n+2에 저장되어 있다.
자식의 노드 인덱스를 가지고 부모의 인덱스를 알 수 있다.
인덱스 n에 대한 부모의 인덱스 : (n - 1) / 2 (나눈 후 내림)
ex) childNode Index : n (14) => parentNode Index : (14 - 1) / 2 => 6.5 => ∴ 6
3. 힙 : Insert 메소드 소개
Vlsualgo Binary Heap : Binary Heap (Priority Queue) - VisuAlgo
Binary Heap (Priority Queue) - VisuAlgo
VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only "payment" that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Facebook/Twitte
visualgo.net
Insert 의사코드
1. 입력된 값을 배열 끝에 push
2. 무조건 1번 이후에, 알맞은 자리로 갈때까지 버블 업을 해줌
2-1. 마지막 인덱스 자리(배열의 맨 뒤)에 있는 요소를 가지고 옴
2-2. 추가가 되면 그 부모의 자리를 찾음. 공식: (index-1)/2 한 후에 값 내림
2-3. 부모 인덱스 자리에 있는 요소가 자식 인덱스 자리에 있는 요소 보다 작을 때 까지 반복문을 돌림
2-3-a. 추가한 값이 부모 인덱스 자리 값보다 작다면 그냥 멈춤
2-3-b. 추가한 값이 더 크다면 두 값의 자리를 바꿈 & 인덱스를 부모 인덱스로 다시 설정
4. 힙 : Insert 메소드 솔루션
// Max_Binary_Heap_Insert.js
class MaxBinaryHeap {
constructor(){
this.values = [];
}
insert(element){
this.values.push(element);
this.bubbleUp();
}
bubbleUp(){
let idx = this.values.length - 1;
const element = this.values[idx];
while(idx > 0){
let parentIdx = Math.floor((idx - 1)/2);
let parent = this.values[parentIdx];
if(element <= parent) break;
this.values[parentIdx] = element;
this.values[idx] = parent;
idx = parentIdx;
}
}
}
let heap = new MaxBinaryHeap();
heap.insert(41);
heap.insert(39);
heap.insert(33);
heap.insert(18);
heap.insert(27);
heap.insert(12);
heap.insert(55);5. 힙 : ExtractMax 메소드 소개
① root 요소 제거
② 가장 맨 뒤에 있는 값과 자리 바꿈
③ 그리고 조정(sink down)하기
조정(SINK DOWN)?
힙에서 루트를 제거하는 과정,
즉 최대 힙에서는 최대값을 그리고 최소 힙에서는 최소값을 제거한 다음에 프로퍼티를 정리한다.
모든 것이 알맞은 자리에 있게 하는 것이다.
이 과정을 down-heap (bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down, extract-min/,max) 이라고 부른다.
removing (extractMax) 의사코드
1. 마지막 값과 첫 번째 값을 바꿈
2. pop으로 제일 뒤로간 root 값 꺼냄, 이걸 마지막에 리턴해줌
3. 새 root 값으로 조정 (SINK DOWN) 해서 정확한 자리에 위치시킴
3-1. 부모 인덱스는 0 (root) 부터 시작함
3-2. 왼쪽 자식의 인덱스를 찾음 : 2 * index + 1 (값이 경계에 넘지 않도록 조심)
3-3. 오른쪽 자식의 인덱스를 찾음 : 2 * index + 2 (값이 경계에 넘지 않도록 조심)
3-4. 만약 왼쪽 or 오른쪽 자식이 새 root 보다 크면 바꿈.
만약 두 값 모두 root보다 크면, 둘 중에 더 큰값과 root를 바꿈
3-5. 바꾼 자식 인덱스가 새로운 부모 인덱스가 됨
3-6. 왼쪽과 오른쪽 자식이 부모보다 작은 값일 때까지 루프를 돌리고 바꾸는 과정을 계속함
(결국 루트에 올렸던 그 요소가 제대로 자리를 찾아 가라앉을 때까지 루프 반복)
3-7. 예전 root(2번)값 리턴
6. 힙 : ExtractMax 메소드 솔루션
// Max_Binary_Heap_Extract_Max.js
class MaxBinaryHeap {
constructor(){
this.values = [];
}
insert(element){
this.values.push(element);
this.bubbleUp();
}
bubbleUp() {
let idx = this.values.length - 1;
const element = this.values[idx];
while (idx > 0) {
let parentIdx = Math.floor((idx-1)/2);
let parent = this.values[parentIdx];
if (element <= parent) break;
this.values[idx] = parent;
this.values[parentIdx] = element;
idx = parentIdx;
}
}
extractMax() {
// EDGE CASE COME BACK TO THIS !!
const max = this.values[0];
const end = this.values.pop();
if (this.values.length > 0) {
this.values[0] = end;
this.sinkDown();
}
return max;
}
sinkDown() {
let idx = 0;
const length = this.values.length;
const element = this.values[0];
while (true) {
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIdx < length) {
leftChild = this.values[leftChildIdx];
if (leftChild > element) {
swap = leftChildIdx;
}
}
if (rightChildIdx < length) {
rightChild = this.values[rightChildIdx];
if (
(swap === null && rightChild > element) ||
(swap !== null && rightChild > leftChild)
)
{
swap = rightChildIdx;
}
}
if (swap === null) break;
this.values[idx] = this.values[swap];
this.values[swap] = element;
idx = swap;
}
}
}
let heap = new MaxBinaryHeap();
heap.insert(41);
heap.insert(39);
heap.insert(33);
heap.insert(18);
heap.insert(27);
heap.insert(12);
heap.insert(55);
console.log(heap.values); // (7) [55, 39, 41, 18, 27, 12, 33]
heap.extractMax(); // 55
console.log(heap.values); // (6) [41, 39, 33, 18, 27, 12]
heap.extractMax(); // 41
console.log(heap.values); // (5) [39, 27, 33, 18, 12]
heap.extractMax(); // 39
console.log(heap.values); // (4) [33, 27, 12, 18]
heap.extractMax(); // 33
console.log(heap.values); // (3) [27, 18, 12]
heap.extractMax(); // 27
console.log(heap.values); // (2) [18, 12]
heap.extractMax(); // 18
console.log(heap.values); // [12]
heap.extractMax(); // 12
console.log(heap.values); // [ ]
7. 우선 순위 큐(Queue) 소개
우선 순위 큐 :
각 요소가 그에 해당하는 우선순위를 가지는 데이터 구조이다.
특징:
더 높은 우선순위를 가진 요소가 더 낮은 우선순위를 가진 요소보다 먼저 처리된다.
데이터 모음이 있는 각 노드, 또는 요소가 각각에 대한 우선순위 값을 가지고 있다.
리스트 사용
힙 사용
8. 우선 순위 큐(Queue) 의사코드
우선순위 큐 의사코드
1. 최소 이진 힙(Min Binary Heap)작성 - 낮은 값이 높은 우선순위를 가짐
2. 각 노드는 값과 우선순위를 하나씩 가짐. 우선순위를 사용해서 힙을 구성함
3. Enqueue 메서드는 값과 우선순위를 가지고, 무언가 삽입되면 새 노드를 만들고, 우선순위 비교해 올바른 위치에 놓음
4. Dequeue 메서드는 루트 요소를 제거하고, 이걸 리턴함. 그리고 우선순위를 이용해서 힙을 재정비함
9. 우선 순위 큐(Queue) 솔루션
// Priority_Queue.js
class PriorityQueue {
constructor(){
this.values = [];
}
enqueue(val, priority){
let newNode = new Node(val, priority);
this.values.push(newNode);
this.bubbleUp();
}
bubbleUp(){
let idx = this.values.length - 1;
const element = this.values[idx];
while(idx > 0){
let parentIdx = Math.floor((idx - 1)/2);
let parent = this.values[parentIdx];
if(element.priority >= parent.priority) break;
this.values[parentIdx] = element;
this.values[idx] = parent;
idx = parentIdx;
}
}
dequeue(){
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){
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
let leftChild,rightChild;
let swap = null;
if(leftChildIdx < length){
leftChild = this.values[leftChildIdx];
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;
}
}
}
class Node {
constructor(val, priority){
this.val = val;
this.priority = priority;
}
}
let ER = new PriorityQueue();
ER.enqueue("common cold",5)
ER.enqueue("gunshot wound", 1)
ER.enqueue("high fever",4)
ER.enqueue("broken arm",2)
ER.enqueue("glass in foot",3)10. 이진 힙의 빅오(BIG O)
삽입과 제거가 빠른편이다.
Insertion - O(log N)
Removal - O(log N)
Search - O(N)
이진 힙이나 어떠한 이진 트리 구조에서든지 한 칸을 내려갈 때마다 2배의 노드가 생긴다.
1 -> 2 -> 4 -> 8 -> 16 -> ...
여기서 200을 찾는다고 할 때 트리의 끝까지 올라가서 첫 요소인 100과 비교해야한다.
힙에 있는 레벨 하나당 한 번의 비교이다.
결국, 16개의 요소를 4번만 비교하게됨. (log16 === log2^4 === 4)
그럼 32개의 요소가 있다면? 32는 2의 5제곱이니까 5번 비교하게 된다.
새로운 층이 하나씩 생길 때마다 걸리는 시간은 한 단위씩 늘어난다.
2^1 (2) ~ 2^2 (4) ~ 2^3 (8) ~ 2^4 (16) ~ 2^5 (32) ~ 2^6 (64) ~ 2^7 (128)
노드가 64개가 되면, 6번의 연산을 해야 한다.
최악의 경우는 어떨까?
최악의 경우에도 빅오는 언제나 삽입과 제거에 대해 log N 이 된다.
회고
1. 이진 힙(Binary Heap)은 그 자체로도 유용하지만, 우선순위 큐(priority queues)와 같은 다른 데이터 구조를 코딩하는데에도 유용하다.
2. 이진 힙은 크게 최대 이진 힙(MaxBinaryHeaps)과 최소 이진 힙(MinBinaryHeap)으로 나뉜다.
2-1. 힙은 항상 왼쪽에서 오른쪽으로 채운다. (피라미드 구조)
3. 약간의 수학 공식을 사용하면, 배열을 가지고 힙을 쉽게 표현할 수 있다.
포인터나 next,left,right,child를 가리키는 노드를 하나하나 만들 필요가 없다.
그냥 배열에 저장하면 된다.(추천)
직접 클래스를 만들어서 힙을 만들어도 된다. (이진 탐색 트리에서 처럼 많은 노드가 필요함)