[프로그래머스 Lv.3] 힙(Heap) - 이중우선순위큐

✨ 문제 ✨

✨ 정답 ✨

function solution(operations){
    let answer=[];
    for (let i=0;i<operations.length;i++){
        if (operations[i][0]==='I'){
            let number=+operations[i].split(' ')[1];
            answer.push(number);
        }else if (operations[i]==='D -1'){
            if (answer.length>0){
                answer.sort((a,b)=>a-b);
                answer.shift();
            }
        }else if (operations[i]==='D 1'){
            if (answer.length>0){
                answer.sort((a,b)=>a-b);
                answer.pop();
            }
        }
    }
     if (answer.length>0){
        let max=Math.max(...answer);
        let min=Math.min(...answer);
        answer=[max, min]
        return answer
    }else{
        return [0,0]
    }
}

🧵 참고한 정답지 🧵

💡💡 기억해야 할 점 💡💡

힙: 완전 이진 트리의 일종, 우선순위 큐를 위해 만들어진 자료구조. 힙은 완전히 정렬된 것은 아니지만 전혀 정렬되지 않은 상태도 아닌 반정렬 상태를 유지한다.
최소 힙: 값이 낮은 데이터가 먼저 삭제된다. 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리
최대 힙: 값이 큰 데이터가 먼저 삭제된다. 모든 노드가 자식 노드보다 작거나 같은 값을 가지는 힙. 루트 노드는 최소값을 가짐
힙의 삽입/삭제 시간 복잡도: O(NlogN)

출처: https://chamdom.blog/heap-using-js/