이진 힙(Binary Heap)

1. 이진 힙(Binary Heap)

완전 이진 트리의 일종으로, 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조. 힙은 느슨한 정렬 상태(상위에 있는 노드의 값은 항상 하위 자식 노드의 값보다 큼/작음)를 유지함

 

 

A. 이진 힙의 종류

① 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 이진 힙

② 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 이진 힙

https://blog.naver.com/zoqdlekt/221669871066

 

 

B. 용어

a. 이진 트리: 각 노드가 최대 2개의 자식 노드를 가지는 트리

https://code-lab1.tistory.com/8

b. 완전 이진 트리: 마지막 depth를 제외한 모든 depth가 완전히 채워져 있는 트리로, 마지막 depth는 꽉 차있을 필요는 없지만 노드가 왼쪽에서 차례대로 채워져 있어야 함.

https://code-lab1.tistory.com/8

 

 

 

2. 최대 힙: 삽입(insert)

https://visualgo.net/en/heap

1. 새 노드를 이진 힙의 마지막에 삽입

2. 부모 노드와 새 노드의 값을 비교해, 부모 노드가 작을 경우 부모 노드와 새 노드의 위치를 바꿈

3. 해당 노드가 루트 노드가 되거나, 부모 노드가 더 클 경우 작업을 중단

 

 

A. 부모 노드의 인덱스 탐색하기

모든 트리는 배열로 구현할 수 있는데, 재귀 호출과 반복문을 간단하게 작성할 수 있다는 장점이 있지만 인덱스 관리가 간단하지 않다는 단점이 있음. 배열을 이용하면 상위 노드 → 하위 노드, 같은 depth일 경우 왼쪽 노드 → 오른쪽 노드 순서대로 배열을 채우게 됨. 인덱스가 각각 2i, 2i + 1인 자식 노드의 부모 노드 인덱스는 i이므로 자식 노드의 인덱스를 절반으로 나눈다면 부모 노드의 인덱스를 얻을 수 있음.  

// 부모 노드의 인덱스를 반환하는 함수
function getParentIdx(idx) {
    return Math.floor(((idx || 1) - 1) / 2);  // idx = 0이면 루트 노드이므로 0을 반환해야 함
}

 

 

B. 이진 힙에 노드 삽입하기

function insert(heap, item) {
    heap.push(item);  // 1. 힙의 마지막 위치에 노드 삽입
    let cIdx = heap.length - 1;
    let pIdx = getParentIdx(cIdx);  // 2. 부모 노드의 인덱스 찾음
    
    // 3. 부모 노드, 새 노드의 값을 비교하면서 위치를 바꾸는 작업 반복
    while (pIdx < cIdx && pIdx >= 0) {
        if (heap[cIdx] <= heap[pIdx]) break;
       
       // 4. 부모 노드의 값이 작을 때 부모 노드와 새 노드의 위치를 바꿈
       [heap[cIdx], heap[pIdx]] = [heap[pIdx], heap[cIdx]];
        cIdx = pIdx;
        pIdx = getParentIdx(cIdx);
    }

    return heap;
}

 

 

 

2. 최대 힙: 최댓값 노드 추출(Extract Max)

최대 이진 힙에서는 루트 노드가 최댓값을 가지므로 배열로 표현했을 때 heap[0]을 반환(shift)하면 됨. 하지만, 루트 노드가 사라졌으므로 힙을 정렬해서 새 루트 노드를 만들어줘야 함. 

 

1. 루트 노드를 반환

2. 마지막 노드를 새 루트 노드로 만들어서 두 자식 노드와 크기를 비교해 해당 노드가 작을 경우 해당 노드와 자식 노드의 위치를 바꿈

3. 비교를 할 자식 노드가 없거나, 해당 노드가 두 자식 노드보다 클 경우 작업을 중단

 

 

A. 이진 힙 재정렬하기

function reArrange(heap, point) {
    let rIdx = point;
    let cIdx = [2 * point + 1, Math.min(2 * rIdx + 2, heap.length - 1)];  // 1. 자식 노드의 인덱스 설정

    while (cIdx[0] < heap.length) {
        const max = Math.max(heap[cIdx[0]], heap[cIdx[1]]);

        if (heap[rIdx] >= max) break;  // 2. 해당 노드가 두 자식 노드보다 크면 정렬 완료  
        if (heap[cIdx[0]] >= heap[cIdx[1]]) {  // 3-1. 해당 노드와 가장 큰 자식 노드를 교체 
            swap(rIdx, cIdx[0], heap);
            rIdx = cIdx[0];  // 3-2. 교체한 자식 노드의 인덱스로 해당 노드의 인덱스 재설정
        } else {
            swap(rIdx, cIdx[1], heap);
            rIdx = cIdx[1];
        }
        cIdx = [2 * rIdx + 1, Math.min(2 * rIdx + 2, heap.length - 1)];  // 4. 다음 루프의 자식 노드의 인덱스 재설정
    }
}

 

 

B. 최댓값 추출하기

function extractMax(heap) {
    swap(0, heap.length - 1, heap);  // 1. 루트 노드와 마지막 노드를 교체
    const root = heap.pop();  // 2. 교체 전 루트 노드를 추출(최댓값) 

    reArrange(heap, 0)  // 3. 최대 힙을 유지하도록 힙을 재정렬 

    return root;
}

extractMax() 함수를 실행할 때마다 힙의 최댓값을 순차적으로 반환함.

 

 

 

 

 

 

 

[참고]

[자료구조] 힙(heap)이란

[자료구조] 트리(Tree)의 개념 | 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리, 이진 탐색트리