우선순위 큐와 덱

우선순위 큐(Priority Queue)

• 기존의 큐가 FIFO 로서 먼저 들어온 요소가 먼저 나가는 구조였다면, 우선순위 큐는 요소 간에 우선순위가 있어서 우선순위가 높은 요소가 먼저 나가는 구조입니다.
• 예를 들어, 각 요소가 순서대로 나열되어 있을 때, 마지막에 들어온 요소가 시급하게 처리해야 하는 작업이라면 대기열의 젤 앞으로 해당 요소를 옮기는 것을 생각할 수 있습니다.
• 우선순위 큐는 우선순위이라는 기능 때문에, 이진 힙을 사용해야 하므로 시간복잡도가 O(log n) 으로 늘어나게 됩니다.
• 우선순위 큐에는 중복되는 우선순위를 가질 수는 있지만, 내부적으로 실제 우선순위를 판단하기 곤란한 점이 있으므로 최대한 중복이 없는 것이 좋습니다.
• 최소 힙으로 만든 후, 일반 노드는 1,2,3,4 로 표시하고, 급하게 꺼내야 하는 노드는 -100 을 우선순위로 두는 것을 추천합니다.

구현

우선순위 큐는 이진 힙으로 구현됩니다. 차이점은 priority 가 추가된 {우선순위, 값} 형태로 배열에 저장되는 점과 비교 대상이 value 이 아니라 priority 가 된다는 점 입니다.

class  PriorityQueue{

    arr=[]

    // 부모 인덱스
    #parentIndex(index) {
        return Math.floor((index-1)/2)
    }

    // 왼쪽 자식 인덱스
    #leftChildIndex(index) {
        return 2*index + 1
    }

    // 오른쪽 자식 인덱스
    #rightChildIndex(index) {
        return 2*index + 2
    }

    #heapifyUp(index){
        if(index === 0 ) return 
        
        if( this.arr[this.#parentIndex(index)].priority < this.arr[index].priority ) {
            const temp = this.arr[index]
             this.arr[index] =  this.arr[this.#parentIndex(index)]
            this.arr[this.#parentIndex(index)] = temp

            this.#heapifyUp(this.#parentIndex(index))
        }
    }

    insert(priority, value){
        const index = this.arr.length // 인덱스
        this.arr[index] = {priority, value} // 마지막 리프 노드 자리에 새로운 노드 추가
        this.#heapifyUp(index) // 리프 -> 루트 방향으로 상향식 스왑
        
    }

    #heapifyDown(index){
        // if(this.#leftChildIndex(index)<this.arr.length) return

        const bigIndex = this.arr[this.#leftChildIndex(index)]?.priority > this.arr[this.#rightChildIndex(index)]?.priority
            ? this.#leftChildIndex(index)
            : this.#rightChildIndex(index)

        if(this.arr[index]?.priority< this.arr[bigIndex]?.priority){
            const temp = this.arr[index]        
            this.arr[index] = this.arr[bigIndex];
            this.arr[bigIndex] = temp;

            this.#heapifyDown(bigIndex)
            }
    }

   // 루트 노드 제거(루트 제거 시 마지막 리프 노드가 루트로 오고, 상향식 스왑 연산이 이루어짐)
    removeRoot(){
        if(this.arr.length<1) return 

        const root = this.arr[0] // 루트 요소 제거
        if(this.arr.length === 1) return this.arr.pop()
        this.arr[0] = this.arr.pop() // 마지막 요소 꺼내서 루트 자리로

        // 최대 힙이 무너진 경우 맞추기 위해  루트 인덱스 -> 리프 인덱스 방향으로
        this.#heapifyDown(0)
        
        return root
    }

    // 힙 정렬
    sort(){
        const sortedArr = []
        while(this.arr.length>0) {
            sortedArr.push(this.removeRoot())
        }

        return sortedArr
    }
    // 노드 탐색
    search(value) {
        if(this.arr.length === 0) return false

        for(let i =0;i< this.arr.length; i++) {
            if(this.arr[i].value === value) {
                return i
            }
        }
    }

    // 특정 노드 수정
    update(value, newValue){
        const index = this.search(value);
        if(index === null) return false;

        this.arr[index] = newValue // 새로운 노드로 대체
        
        let parentIndex = Math.floor((this.arr.length/2-1)) // 오른쪽 서브 트리 리프노드의 부모 인덱스
        for(let i = parentIndex; i>=0; i-- ) { // 루트 노드에 도달할 때 까지 부모와 자식 노드 간의 스왑 연산 수행(1/2n)
         this.#heapify(i)       // 상수 시간(1)
        }
    }

    // 특정 노드 삭제
    removeValue(value){
        const index = this.search(value) // 삭제할 노드의 인덱스
        if(index === null) return false;

        this.arr.splice(index,1)
       let parentIndex = Math.floor((this.arr.length/2-1)) // 오른쪽 서브 트리 리프노드의 부모 인덱스
        for(let i = parentIndex; i>=0; i-- ) { // 루트 노드에 도달할 때 까지 부모와 자식 노드 간의 스왑 연산 수행(1/2n)
             this.#heapify(i)       // 상수 시간(1)
        }
    }

    // 히피파이
    #heapify(index){
        const bigIndex = this.arr[this.#leftChildIndex(index)]?.priority > this.arr[this.#rightChildIndex(index)]?.priority 
            ? this.#leftChildIndex(index)
            : this.#rightChildIndex(index)

        if(this.arr[index]?.priority < this.arr[bigIndex]?.priority) {
            let temp = this.arr[bigIndex]
            this.arr[bigIndex]  = this.arr[index]
            this.arr[index] = temp
        }
    }
}

const pq = new PriorityQueue();
pq.insert(3,'three')
pq.insert(6,'six')
pq.insert(2,'two')
pq.insert(7,'seven')
pq.insert(1,'one')
pq.insert(4,'four')
pq.insert(5,'five')

console.log(pq)
/*
{priority: 7, value: 'seven'}
{priority: 6, value: 'six'}
{priority: 5, value: 'five'}
{priority: 3, value: 'three'}
{priority: 1, value: 'one'}
{priority: 2, value: 'two'}
{priority: 4, value: 'four'}
*/

console.log(pq.sort())
/*
{priority: 7, value: 'seven'}
{priority: 6, value: 'six'}
{priority: 5, value: 'five'}
{priority: 4, value: 'four'}
{priority: 3, value: 'three'}
{priority: 2, value: 'two'}
{priority: 1, value: 'one'}
*/

덱(Deque)

• 덱은 일반적인 큐와 다르게 양쪽으로 인큐와 데큐가 가능한 자료구조 입니다.
• 자바스크립트 함수로 따지면**, push(), pop() : 뒤에서 넣고, 뒤에서 빼기 와 unshift(), shift() : 앞에서 넣고, 앞에서 빼기** 가 모두 가능합니다. 자바스크립트에 특화된 자료구조라고 볼 수 있습니다.

덱 구현

뒤에서 넣고, 앞에서만 빼는게 가능했던 일반적인 큐에서 양방향으로 추가, 삭제가 가능해졌습니다. 이를 위해 push, pop, unshift, shift 함수를 모두 사용합니다.

class Deque{
    arr=[]

    // 뒤로 넣기
    push(value){
        this.arr.push(value)
    }

    // 뒤로 빼기
    pop(){
        this.arr.pop()
    }

    // 앞으로 넣기
    unshift(value){
        this.arr.unshift(value)
    }

    // 앞으로 빼기
    shift(){
        this.arr.shift()
    }
    

    peek(){
        return this.arr.at(0)
    }

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

const deque = new Deque();

deque.push(2)
deque.push(5)
console.log(deque) // [2, 5]

deque.push(3)
deque.push(7)
console.log(deque) // [2, 5, 3, 7]

deque.unshift(6)
console.log(deque) //  [6, 2, 5, 3, 7]

deque.shift()
console.log(deque) //  [2, 5, 3, 7]

deque.pop()
console.log(deque) //  [2, 5, 3]