TIL

2024년 11월 1일 TIL

kagan-draca 2024. 11. 2. 22:58

알고리즘 중급 강의 시간으로 

최대 힙(Max Heap)과 최소 힙(Min Heap)을 배웠다.

최대 힙은

 

루트 노드는 항상 최대값을 가지며, 부모 노드는 항상 자식 노드 보다 큰 값을 가지는 이진 탐색 트리 였다.

 

최소 힙은


루트 노드는 항상 최소값을 가지며, 부모 노드는 항상 자식 노드 보다 큰 값을 가지는 이진 탐색 트리 였다.

 

 

최대 힙이라 가정하고 새로운 자식이 추가 될 경우 추가된 자식이 부모 보다

큰 수를 가질 수 있기 때문에 아래와 같은 동작 과정을 거친다.

 

위와 같이 동작 하기 위해 JavaScript로 구현된 코드를 보면 아래와 같이 코드가 구성 되는데,

 

class MaxHeap {
    // 최대 힙(Max Heap)을 구현하기 위한 클래스 정의
    constructor() {
        // 힙을 저장할 배열 초기화
        this.heap = [];
    }

로 MaxHeap을 Class로 구현해 생성자가 호출되면 숫자가 저장될 배열을 생성해줍니다.

 

    insert(value) {
        // 힙에 새 값을 추가하는 메서드
        this.heap.push(value); // 새로운 값을 배열의 마지막 위치에 추가
        this.bubbleUp();       // 최대 힙 조건을 유지하기 위해 'bubbleUp' 호출
    }

만약, MaxHeap 객체에 숫자가 들어올 경우 배열의 맨 뒤(BST 트리의 맨 뒤 가지에)에 숫자를 추가해주고,

 

    bubbleUp() {
        // 새로운 값이 힙 배열의 마지막 위치에 추가된 상태에서 최대 힙 조건을 유지하기 위해 호출되는 메서드

        let index = this.heap.length - 1; // 추가된 값의 초기 인덱스(배열의 마지막 인덱스)
        let parentIndex = Math.floor((index - 1) / 2); // 부모 인덱스는 현재 인덱스의 (index-1)/2 위치에 있음

        // 현재 요소가 루트가 아니면서 부모 요소보다 클 경우 반복
        while (index > 0 && this.heap[parentIndex] < this.heap[index]) {
            // 부모와 현재 요소를 비교하여 부모보다 큰 경우 위치 교환
            [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
            // 교환 후, 인덱스를 부모의 인덱스로 갱신하여 계속해서 위쪽 부모와 비교
            index = parentIndex;
            parentIndex = Math.floor((index - 1) / 2); // 새로운 부모 인덱스를 계산
        }
    }

    printHeap() {
        // 현재 힙의 상태를 출력하는 메서드
        console.log(this.heap);
    }
}

상위 부모들과 새로운 숫자를 비교하며 자리를 교체해줍다.

 

// MaxHeap 인스턴스 생성
const maxHeap = new MaxHeap();

// 최대 힙에 요소 삽입
maxHeap.insert(10);
maxHeap.insert(20);
maxHeap.insert(5);
maxHeap.insert(30);
maxHeap.insert(15);

maxHeap.printHeap();

만약, 위와 같이 숫자가 최대 힙에 들어올 경우

 

maxHeap.insert(10);

 

힙 배열에 아무 숫자도 없기 때문에 index가 0인 위치에 10을 추가해줍니다.

 

배열 결과 : [10]

maxHeap.insert(20);

 

만약, 새로운 숫자 20이 들어올 경우 힙 배열에 [10]이 존재하기 때문에 index가 1인 위치에 20을 추가해주고,

 

20과 부모인 10을 비교해줍니다. 이때, 20 > 10 보다 크기 때문에 

 

20과 10의 위치를 교체해줍니다.

 

배열 결과 : [20, 10]

 
maxHeap.insert(5);

 

또 다시 새로운 숫자인 5가 maxHeap에 들어올 경우, 힙 배열에 [20, 10]이 존재하기 때문에

5를 index 2의 위치에 추가해줍니다. 그 후, 5의 부모(20)과 숫자를 비교하는데

5 < 20 작기 때문에 위치를 교환하지 않습니다.

 

 

배열 결과 : [20, 10, 5]

maxHeap.insert(30);

 

최대 힙에 30이 들어올 경우, 힙 배열에 [20, 10, 5]가 존재하기 때문에 index가 3인 위치에 30을 추가해줍니다. 

그 후, 30과 부모(10)을 비교하는데 30 > 10 크기 때문에, 30과 10 위치를 교체해줍니다.

그 후, 다시 30과 부모(20)을 비교 하는데 30 > 20 크기 때문에, 30과 20 위치를  교체해줍니다.

 

 

배열 결과 : [30, 20, 5, 10]

maxHeap.insert(15);

 

마지막으로, maxHeap에 15가 추가 될 경우, 힙 배열에 [30, 20, 5, 10]이 존재하기 때문에

index가 4인 위치에 15를 추가해줍니다. 15의 부모(20)과 비교했을 때 15 < 20 작기 때문에 위치를 교체하지 않습니다.

 

 

배열 결과: [30, 20, 5, 10, 15]

 

그 결과 MaxHeap의 힙 배열에는 [30, 20, 5, 10, 15] 순으로 숫자가 배치 돼

설명과 코드가 동일하게 동작하는 것을 확인할 수 있습니다.