[Algorithm] 최대 이진 힙 구현하기 Node.js/Javascript

자료구조 중 이진 힙(Binary Heap)은 노드 값들이 순서를 가지고 있는 완전 이진 트리(Complete Binary Tree)로 구성됩니다. 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨의 노드들이 가득 채워져 있는 형태입니다. 마지막 레벨의 경우 왼쪽 부터 차례 대로 채워져 있게 됩니다. 

 

 

 

 

이진 힙은 최대 힙(Max Heap), 최소 힙(Min Heap)으로 구분됩니다. 만약 부모 노드의 값이 자식 노드의 값보다 큰 경우는 최대 힙, 작은 경우는 최소 힙이 됩니다. 완전 이진 트리의 경우 노드가 낮은 레벨 부터 채워집니다. 또한 같은 레벨에서는 왼쪽 부터 채워지는 특징을 가집니다. 이런 특성 때문에 배열로 구현하는게 수월합니다. 

 

완전 이진 트리의 경우 왼쪽 부터 자식 노드가 채워집니다.

완전 이진 트리와 포화 이진 트리는 동일한 모양입니다.

 

왼쪽이 채워지지 않은 이진 트리의 경우 완전 이진트리가 아닙니다.

 

이진 힙의 경우 자식 노드가 2개인 트리 구조로 구성되어 있으므로, 이진 힙으로 정렬할 경우 시간복잡도는 O( log N)이 됩니다. 최대 힙과 이진 검색 트리 모두 완전 이진 트리로 구성되지만 차이점은 이진 검색 트리에서는 모든 노드가 정렬되는 것에 비해, 최대 힙에서는 부모 노드와 자식 노드간의 관계만 명시됩니다. 즉, 부모 노드의 값은 자식 노드 2개의 값보다 크게 됩니다. 

 

이진 힙 구현

이진 힙을 구현하는 방법은 크게 2가지가 있습니다. 첫번째 방법은 객체를 사용하는 방법입니다. 트리 객체를 이용해 구현하는 경우 직관적으로 이해하기 쉽지만 저장공간을 희생해야 하고 오버헤드가 발생합니다. 

이진 힙을 구현하는 두번째 방법은 배열을 사용하는 방법입니다. 모든 트리 자료구조는 배열로 구현이 가능합니다. 데이터가 선형적으로 저장되므로 저장공간을 절약할 수 있고, 오버헤드(재귀호출, 반복문)가 줄어드는 장점이 있습니다. 하지만 트리 자료구조를 배열로 구현할 경우 인덱스 관리가 까다롭습니다. 

 

 

 

 

트리 구조를 어떤 방식으로 구현할지는 알고리즘 문제의 요구사항을 꼼꼼히 읽어 보고 구현하는 습관을 가져야 합니다. 

 

문제

 

정수로 구성된 배열을 입력 받아 이진 힙(Binary Heap)을 구현해 반환합니다.

 

입/출력

 

입력 1 : arr

• Number 타입 요소로 구성된 배열
• -100,000 <= arr[i] <= 100,000
• arr.length <= 100,000

 

출력 

Number 타입 요소를 가진 배열

 

주의사항

 

• 최대 힙(Max Heap)을 구현합니다.
• 입력값은 중첩되지 않은 1차원 배열입니다.
• getParentIdx, insert 함수를 모두 사용해야 합니다.
• insert 의 시간복잡도는 O(log N)입니다.

 

풀이

 

이진 힙을 배열로 구현할 경우 먼저 가장 마지막 레벨 왼쪽 부터 새로운 요소를 추가합니다. 최대 힙을 구현하는 것이 목적이므로, 먼저 자식 노드를 추가한 후 부모 노드와 값을 비교합니다. 새로운 요소가 부모 노드보다 큰 경우 swap을 하게 되고, Root Node 까지 비교를 이어갑니다. 

먼저 Swap 함수를 구현합니다. 배열은 Reference Type 변수이므로 주소값을 이용해 다음과 같이 2개의 요소를 swap 할 수 있습니다. 

function swap(idx1, idx2, arr){
    // Destructuring Assignment;
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}

 

getParentIdx() 함수를 구현합니다. 이진 힙에서의 부모 노드는 2개의 자식 노드보다 큰 요소가 위치해야 합니다.

function getParentIdx(idx){
    return Math.floor((idx-1)/2);
}

 

 

 

 

insert() 함수를 구현합니다. 

1. 새로운 요소를 배열에 추가한다.
2. 마지막 위치를 currentIdx로 잡는다.
3. parentIdx는 currentIdx를 getParentIdx() 함수를 통해 구한다.
4. parentIdx가 0보다 크고, 배열의 부모 노드가 자식 노드보다 클 때 까지 반복을 진행한다.

function insert(heap, item){
    heap.push(item);
    let currentIdx = heap.length-1;
    let parentIdx = getParentIdx(currentIdx);
    while(parentIdx >= 0 && heap[currentIdx] > heap[parentIdx]){
        swap(currentIdx, parentIdx, heap);
        currentIdx = parentIdx;
        parentIdx = getParentIdx(currentIdx);
    }
    return heap;
}

 

binaryHeap() 함수를 구현합니다. 주어진 배열 arr을 순회하면서 insert 함수를 통해 이진 힙을 구현합니다.

function binaryHeap(arr){
    return arr.reduce((heap, item)=>{
        return insert(heap, item);
    }, []);
}

 

이진 힙을 확인하면 최대 힙이므로 Root Node는 10이 되고 자식 노드들이 하위 레벨에 구성됩니다.

output = binaryHeap([4, 10, 3, 5, 1]);
console.log(output); // --> [10, 5, 3, 4, 1]

 

 

주어진 배열의 0번째 idx인 4가 Heap에 추가됩니다.

 

 

두번째 Idx인 10이 자식노드로 추가되고 부모노드와 비교를 진행합니다. 10이 더 크므로 swap이 발생합니다.

3번째 Idx인 3이 오른쪽 자식 노드에 추가됩니다. 부모 노드보다 작으므로 그대로 유지됩니다.

4번째 Idx인 5가 3번째 레벨 자식 노드로 추가됩니다. 부모노드인 4와 비교했을 때 더 크므로 swap이 발생합니다. 10을 부모 노드로 가지게 되며, 10보다 작으므로 그대로 유지됩니다.

 

마지막으로 1이 자식 노드에 추가되고 부모 노드보다 작으므로 그대로 유지됩니다.

 

 

 

 

 

[Algorithm] Gossip Protocol 알고리즘 문제 Node.js

 

[Algorithm] 기수 정렬 계수 정렬 Node.js

 

 

[Algorithm] Balance Brackets in JS ( 스택(stack) 알고리즘 활용 )