[백준] 1927 최소 힙 JavaScript

1927. 최소 힙

문제

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

배열에 자연수 x를 넣는다.
배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다

예제 입력

예제 출력

최소 힙이라는 처음 보는 유형이 나왔다.

- 최소 힙은 완전 이진 트리 형태를 지니며, 각 부모 노드의 값이 자식 노드들의 값보다 작거나 같은 특성을 가진다. 즉 루트 노드에는 항상 최소값을 지닌다.

- 최소 힙은 항상 완전 이진 트리 형태 여야 하며, 모든 층이 다 채워져 있어야 하고, 마지막 층은 왼쪽으로 오른쪽 순으로 채워져 있어야 한다.

- 부모 노드는 항상 자식 노드보다 작거나 같다.

- 최대 힙은 결국 최소 힙의 반대 유형이므로 함수 식의 반대로 적용하면 된다.

최소 힙을 구하는 단계는 총 4단계로 삽입, 최솟값 제거, 위로 정렬, 아래로 정렬 단계가 있다.

클래스로 구현 하는 방식도 있지만 나는 함수형으로 구현하는게 마음이 편해서 함수형으로 작성하게 되었다.

최종 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = parseInt(input[0], 10);
const operations = input.slice(1).map(Number);

let heap = [];

// 힙에 값 추가
function insert(value) {
    heap.push(value);
    heapifyUp(heap.length - 1);
}

// 힙에서 최소값 추출
function extractMin() {
    if (heap.length === 0) {
        return 0;
    }
    if (heap.length === 1) {
        return heap.pop();
    }
    const min = heap[0];
    heap[0] = heap.pop();
    heapifyDown(0);
    return min;
}

// 힙을 위로 정렬
function heapifyUp(index) {
    let currentIndex = index;
    while (currentIndex > 0) {
        const parentIndex = Math.floor((currentIndex - 1) / 2);
        if (heap[currentIndex] < heap[parentIndex]) {
            [heap[currentIndex], heap[parentIndex]] = [heap[parentIndex], heap[currentIndex]];
            currentIndex = parentIndex;
        } else {
            break;
        }
    }
}

// 힙을 아래로 정렬
function heapifyDown(index) {
    let currentIndex = index;
    const length = heap.length;
    while (true) {
        const leftIndex = 2 * currentIndex + 1;
        const rightIndex = 2 * currentIndex + 2;
        let smallestIndex = currentIndex;

        if (leftIndex < length && heap[leftIndex] < heap[smallestIndex]) {
            smallestIndex = leftIndex;
        }

        if (rightIndex < length && heap[rightIndex] < heap[smallestIndex]) {
            smallestIndex = rightIndex;
        }

        if (smallestIndex !== currentIndex) {
            [heap[currentIndex], heap[smallestIndex]] = [heap[smallestIndex], heap[currentIndex]];
            currentIndex = smallestIndex;
        } else {
            break;
        }
    }
}

const results = [];

for (let i = 0; i < N; i++) {
    const op = operations[i];
    if (op === 0) {
        results.push(extractMin());
    } else {
        insert(op);
    }
}

console.log(results.join('\n'));

힙에 값 추가(insert)

let heap = [];

// 힙에 값 추가
function insert(value) {
    heap.push(value);
    heapifyUp(heap.length - 1);
}

- 힙에 값을 넣어주는 함수로, 값을 배열의 맨 끝에 넣으면 해당 값을 알맞는 위치에 넣기 위해, 부모 노드를 찾는 방식인 힙을 위로 정렬 방식으로 알맞는 위치로 넣어준다.

- heapifyUp에 해당 인덱스를 넣어준다.

최소값 추출(extractMin)

// 힙에서 최소값 추출
function extractMin() {
    if (heap.length === 0) {
        return 0;
    }
    if (heap.length === 1) {
        return heap.pop();
    }
    const min = heap[0];
    heap[0] = heap.pop();
    heapifyDown(0);
    return min;
}

- 최소값을 추출하는 함수로, 배열에서 첫 번째 인덱스가 최소값이니 해당 값을 뽑아준다.

- 최소값을 추출하면, 루트 인덱스의 값이 비어있기 때문에, 제일 큰 값을 첫 번째 인덱스로 넣어준뒤 아래로 정렬을 한다.

위로 정렬(heapifyUp)

// 힙을 위로 정렬
function heapifyUp(index) {
    let currentIndex = index;
    while (currentIndex > 0) {
        const parentIndex = Math.floor((currentIndex - 1) / 2);
        if (heap[currentIndex] < heap[parentIndex]) {
            [heap[currentIndex], heap[parentIndex]] = [heap[parentIndex], heap[currentIndex]];
            currentIndex = parentIndex;
        } else {
            break;
        }
    }
}

- 배열에 값을 새로 넣었으니, 맨 마지막 인덱스부터 시작하여 부모노드를 찾기 시작한다.

- 바꿔준 index는 0보다 작을리는 없기도 하고, break로 while문을 끝낼 것이기 때문에 while문의 조건에 true로 넣어도 무방하다.

- 완전 이진 트리 형식이기 때문에 부모 노드의 인덱스는 Math.floor((index - 1) / 2)로 고정이다.

- 부모 노드보다 작은 값이라면 부모 노드와 위치를 바꿔주고, 부모 노드와 자리를 바꿨기 때문에 부모 인덱스를 기억하고, 다른 부모 노드를 찾아 이를 반복하고, 더 이상 해당 값보다 작은 부모노드가 안나올 때까지 반복해준다.

아래로 정렬(heapifyDown)

// 힙을 아래로 정렬
function heapifyDown(index) {
    let currentIndex = index;
    const length = heap.length;
    while (true) {
        const leftIndex = 2 * currentIndex + 1;
        const rightIndex = 2 * currentIndex + 2;
        let smallestIndex = currentIndex;

        if (leftIndex < length && heap[leftIndex] < heap[smallestIndex]) {
            smallestIndex = leftIndex;
        }

        if (rightIndex < length && heap[rightIndex] < heap[smallestIndex]) {
            smallestIndex = rightIndex;
        }

        if (smallestIndex !== currentIndex) {
            [heap[currentIndex], heap[smallestIndex]] = [heap[smallestIndex], heap[currentIndex]];
            currentIndex = smallestIndex;
        } else {
            break;
        }
    }
}

- 힙을 재구성 할 때의 함수로, 제일 큰 값을 루트 인덱스로 놓고 아래로 비교해가면서 힙을 재구성 한다.

- 자식 노드의 인덱스는 왼쪽은 2n+1, 오른쪽은 2n+2로 고정이다.

- 아래로 탐색을 하면서, 해당 값보다 작은 값을 찾으면 작은 값의 인덱스를 기억하고, 이를 내려가면서 쭉쭉 비교하고, 값의 위치를 바꿔준다.

아래는 최소값을 추출하고 아래로 정렬을 할 때의 예시다.

        1
       / \
      3   5
     / \ / \
    6  7 8  9
   / \
  10  15

        15
       / \
      3   5
     / \ / \
    6  7 8  9
   /
  10

        3
       / \
      15  5
     / \ / \
    6  7 8  9
   /
  10

        3
       / \
      6   5
     / \ / \
    15 7 8  9
   /
  10

        3
       / \
      6   5
     / \ / \
    10  7 8  9
   /
  15

저작자표시 (새창열림)

'백준 문제' 카테고리의 다른 글

[백준 11729] 하노이 탑 이동 순서 Node.js (0)	2022.04.07