[7주차] 우선순위 큐 & 덱

Queue는 선입선출

우선순위 큐

VIP 새치기

큐 시간복잡도 O(1) => 우선순위 큐는 이진 힙으로 구현하므로 O(logN)
Kinda 단점, but 우선순위 큐 구현하려면 어쩔 수 없음

cf. 이진 힙 조금 변형한거라 별 차이점 없음

덱 (Deque)

Stack(후입선출) + Queue(선입선출)
push, pop, unshift, shift 다 가능

자바스크립트 리스트와 거의 똑같

우선순위 큐 구현하기

이진힙.js 변경사항

const pq = new PriorityQueue();
pq.insert(3, 'one');
pq.insert(7, 'two');
pq.insert(2, 'three');
pq.insert(8, 'four');
pq.insert(5, 'five');
pq.insert(6, 'six');
pq.insert(9, 'king');
pq.remove(); // return 루트니까 'king' 
pq;

insert(priority, value){ // O(logN) 이런 애들은 보통 재귀 사용, 부모랑 비교해서 바꾼다
        const index = this.arr.length; // 배열의 마지막에 값 insert 하고
        this.arr[index] = {
            priority, value, // **** 객체로 ****
        };
        this.#reheapUp(index);
    }

// *** priority 보호해주기 ***

#reheapUp(index){
        if(index > 0){ // 루트가 아닐 때까지
            const parentIndex = Math.floor((index - 1) / 2);
            if(this.arr[index].priority > this.arr[parentIndex].priority){ // 부모보다 클 때 ***priority 끼리 비교***
                // 값(자리) 바꾸기
                const temp = this.arr[index];
                this.arr[index] = this.arr[parentIndex];
                this.arr[parentIndex] = temp;
                this.#reheapUp(parentIndex); // 부모자리에서 다시 재귀함수 호출
            }
        }        
    }

// *** priority 보호해주기 ***

#reheapDown(index){
        const leftIndex = index * 2 + 1;
        if(leftIndex < this.arr.length){ // 자식이 없을 때까지
            const rightIndex = index * 2 + 2;
            const bigger = this.arr[leftIndex]?.priority > this.arr[rightIndex]?.priority ? leftIndex : rightIndex; // *** priority끼리 비교
            if(this.arr[index]?.priority < this.arr[bigger]?.priority){ // 본인이 자식보다 작을 경우
                const temp = this.arr[index];
                this.arr[index] = this.arr[bigger];
                this.arr[bigger] = temp;
                this.#reheapDown(bigger);
            }
        }
    }

우선순위큐에 heapify는 없어야 맞는 거지만, 굳이 해주겠다면 ?.priority 추가

pq.remove(); // return 루트니까 'king' 

Q. 이진힙은 중복된 값 가능?

ㅇㅇ가능은 한데 힙에서는 중복 구별하기 어려움..
최소힙으로 만든 다음 => 일반 노드들은 1, 2, 3, 4로 만들고 급한 애들은 -100같은 값 주는 걸 추천

덱(Deque) 구현하기

Stack.js 변경사항
shift(), unshift(), peek() 메소드 추가

class Deque {
    arr = [];

    push(value) {
        return this.arr.push(value);
    }

    pop() {
        return this.arr.pop();
    }

    shift(){
        return this.arr.shift();
    }

    unshift(value){
        return this.arr.unshift(value);
    }

    peek() { // 제일 앞에 거 확인
        return this.arr.at(0);
    }

    top() {
        return this.arr.at(-1); // 최신 문법
        // this.arr[this.arr.length -1] 옛날 방식
    }

    get length() {
        return this.arr.length;
    }
}

const deque = new Deque();
deque.push(1);
deque.push(3); 
deque.push(5);
deque.unshift(2);
deque.unshift(4); 
// 4, 2, 1, 3, 5
console.log(deque.length), // 5
deque.pop(); // 5
deque.shift(); // 2
console.log(deque.peek()); // 2

결론 :
Stack + Queue라서 자바스크립트 리스트랑 정말 가까운 자료구조