[알고리즘] 힙 , 우선 순위 큐 , 백준 11279

오늘은 자료 구조 힙(Heap)과 우선순위 큐(Priority Queue)에 대해 알아보겠습니다.

⭐️ 힙(Heap)이란 ?

Heap이란 완전 이진 트리의 일종으로 , 부모 노드와 자식 노드 간의 특정한 순서 관계를 유지하는 자료 구조입니다. 힙은 최대 힙 (Max Heap) , 최소 힙 (Min Heap) 두 가지 종류로 나뉩니다.

1. 최소 힙 (Min Heap)

• 각 노드의 값이 해당 자식 노드의 값보다 작거나 같은 완전 이진 트리입니다.
• 즉 , 최상위 노드가 트리 내에서 가장 작은 값을 가집니다.
• 특정 노드의 값이 그 자식 노드의 값보다 작은 트리를 말합니다.

최대 힙은 반대라고 생각하면 되겠습니다.

힙에 요소를 삽입할 때는 O(log n) , 삭제할 때도 O(log n)의 시간 복잡도가 소요됩니다. 삽입할 때는 트리의 상위에 항상 최소 혹은 최댓값을 유지해야 하기 때문에 heapifyUp이라는 과정을 거치고 , 삭제할 때 또한 구조를 유지하기 위해 HeapifyDown의 과정을 거쳐야 하기 때문에 log n의 시간 복잡도를 거칩니다.

힙은 주로 우선 순위 큐를 구현하는 데에 사용됩니다.

⭐️ 우선 순위 큐(Priority Queue)란 ?

우선 순위 큐는 가장 높은 우선 순위를 가진 요소가 항상 먼저 나오는 자료 구조입니다. 우선 순위가 가장 높은 노드가 트리의 root node에 위치하고 있는 것이죠.

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    
    getLeftChildIdx(index) {
        return 2 * index + 1;
    }
    getRightChildIdx(index) {
        return 2 * index + 2;
    }
    getParentIdx(index) {
        return Math.floor((index - 1) / 2);
    }

    insert(value) {
        this.heap.push(value);
        this.heapifyUp();
    }
    heapifyUp() {
        let index = this.heap.length - 1;
        const lastInsertedNode = this.heap[index];
        
        // 루트 노드에 도달할 때까지 비교를 진행합니다. 
        while (index > 0) {
            const parentIdx = this.getParentIdx(index);
            
            // 부모 인덱스 노드의 값이 마지막 삽입 노드의 값보다 작다면 자리를 교체해줍니다. 
            if (this.heap[parentIdx] < lastInsertedNode) {
                this.heap[index] = this.heap[parentIdx];
                index = parentIdx;
            } else break;
        }
        this.heap[index] = lastInsertedNode;
    }

    // 반환과 삭제를 동시에 진행해줍니다. 
    remove() {
        if (this.heap.length === 0) return null;

        const rootNode = this.heap[0];
        if (this.heap.length === 1) this.heap = [];
        else {
            this.heap[0] = this.heap.pop();
            this.heapifyDown();
        }
        return rootNode;
    }
    heapifyDown() {
        let index = 0;
        const count = this.heap.length;

        const rootNode = this.heap[0];
		
        // 왼쪽 자식 노드의 존재 유무는 자식 노드의 존재 유무이기 때문에
        // 오른쪽 자식 노드의 존재 유무는 반복 조건으로 치지 않습니다. 
        while (this.getLeftChildIdx(index) < count) {
            const leftChildIdx = this.getLeftChildIdx(index);
            const rightChildIdx = this.getRightChildIdx(index);
			
            // rightChildIdx < count가 거짓이 되면 leftChildIdx가 자동으로 들어오게 됩니다. 
            // 반복문 조건으로 leftChildIdx의 존재 유무를 알고 있기에 다른 조건문이 필요하지 않습니다. 
            
            const biggerIdx =
                rightChildIdx < count &&
                this.heap[rightChildIdx] > this.heap[leftChildIdx]
                    ? rightChildIdx
                    : leftChildIdx;

            if (this.heap[biggerIdx] >= rootNode) {
                this.heap[index] = this.heap[biggerIdx];
                index = biggerIdx;
            } else break;
        }
        this.heap[index] = rootNode;
    }
}

// heap 상속
class PriorityQueue extends Heap {
    constructor() {
        super();
    }

    enqueue = (value) => this.insert(value);
    dequeue = () => this.remove();
    isEmpty = () => this.heap.length <= 0;
}

⭐️ 백준 11279

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    //힙이 잘 정렬됐는지 확인할 때 사용합니다. 
    logHeap() {
        console.log(this.heap);
    }
    getLeftChildIdx(index) {
        return 2 * index + 1;
    }
    getRightChildIdx(index) {
        return 2 * index + 2;
    }
    getParentIdx(index) {
        return Math.floor((index - 1) / 2);
    }

    insert(value) {
        this.heap.push(value);
        this.heapifyUp();
    }
    heapifyUp() {
        let index = this.heap.length - 1;
        const lastInsertedNode = this.heap[index];
        while (index > 0) {
            const parentIdx = this.getParentIdx(index);
            if (this.heap[parentIdx] < lastInsertedNode) {
                this.heap[index] = this.heap[parentIdx];
                index = parentIdx;
            } else break;
        }
        this.heap[index] = lastInsertedNode;
    }

    // return and remove
    remove() {
        if (this.heap.length === 0) return null;

        const rootNode = this.heap[0];
        if (this.heap.length === 1) this.heap = [];
        else {
            this.heap[0] = this.heap.pop();
            this.heapifyDown();
        }
        return rootNode;
    }
    heapifyDown() {
        let index = 0;
        const count = this.heap.length;

        const rootNode = this.heap[0];

        while (this.getLeftChildIdx(index) < count) {
            const leftChildIdx = this.getLeftChildIdx(index);
            const rightChildIdx = this.getRightChildIdx(index);

            const biggerIdx =
                rightChildIdx < count &&
                this.heap[rightChildIdx] > this.heap[leftChildIdx]
                    ? rightChildIdx
                    : leftChildIdx;

            if (this.heap[biggerIdx] >= rootNode) {
                this.heap[index] = this.heap[biggerIdx];
                index = biggerIdx;
            } else break;
        }
        this.heap[index] = rootNode;
    }
}

function solution(input) {
    const n = +input[0];
    const arr = input.slice(1);

    const maxHeap = new MaxHeap();
    let answer = "";

    for (let i = 0; i < arr.length; i++) {
        const x = arr[i];

        if (x === 0) {
            const max = maxHeap.remove();
            max ? (answer += `${max}`) : (answer += "0");

            if (i !== arr.length - 1) {
                answer += "\n";
            }
        } else {
            // heap에 추가
            maxHeap.insert(x);
        }
    }
    // console.log()는 시간이 많이 걸리는 작업이기 때문에 , 반복문에서 실행하는 것이 아닌
    // heap 정렬이 끝난 후 한 번만 출력해주는 것이 시간 단축에 도움이 됩니다. 
    console.log(answer);
}

const rl = require("readline").createInterface({
    input: process.stdin,
    output: process.stdout,
});

const input = [];

rl.on("line", (line) => {
    input.push(parseInt(line));
}).on("close", () => {
    solution(input);
    process.exit();
});