이진 힙 (Binary Heap)

• 트리 구조중 하나로 이진 탐색 트리와 매우 비슷하나 다른 규칙을 가진다.
• 최대 이진 힙에서는 부모 노드가 항상 자식 노드보다 큰 값을 가진다. (모든 자식 노드가 부모보다 작다)
• 최소 이진 힙에서는 부모 노드가 항상 자식 노드보다 작은 값을 가진다.
• 각각의 부모 노드들은 최대 두개의 자식을 가진다.

시간 복잡도

• Insertion : O(log N)
• Removal : O(log N)
• Search : O(N) (순서가 없기 때문에 전체 다 탐색)

현재 위치에서 자식 노드 찾기

• left : 2n + 1
• right : 2n +2

현재 위치에서 부모 노드 찾기

• Math.floor((n-1)/2)

최대 이진 힙

class MaxBinaryHeap{
    constructor(){
        this.values = []
    }
}

Insert method 구현

1. 가장 끝에 값을 추가한뒤 부모의 위치를 찾아 값을 비교한다 만약에 부모가 자신보다 작다면 bubbleUp을 한다
2. 부모가 자신보다 클때까지 반복한다.

Bubble up

• 추가한 값과 부모의 값을 비교한뒤 작은경우 스왑한다. (부모의 값이 추가한 값보다 큰 경우까지)

bubbleUp(){
        let currentIndex = this.values.length-1
        let parentIndex = Math.floor((currentIndex-1)/2)
        while(true){
            parentIndex = Math.floor((currentIndex-1)/2)
            if(this.values[parentIndex] < this.values[currentIndex]){
                [this.values[parentIndex],this.values[currentIndex]] = [this.values[currentIndex],this.values[parentIndex]]
                currentIndex = parentIndex
            }else break
        }
    }
insert(val){
    this.values.push(val)
    this.bubbleUp()
    return this
}

ExtractMax method 구현

-최대 이진 힙일경우 최대값(루트) 최소 이진 힙일경우 최소값(루트)를 제거

Sink down

1. 루트를 제거하고 가장 끝에 있는값을 루트로 설정한다
2. 자식 노드들중 가장 큰값과 비교하여 자신보다 큰경우 스왑한다
3. 반복

sinkDown(){
        let idx = 0
        let len = this.values.length
        let element = this.values[0]
        while(true){
            let leftChildIdx = idx*2 + 1
            let rightChildIdx = idx*2 + 2
            let leftChild,rightChild
            let swap = null
            if(leftChildIdx < len){
                leftChild = this.values[leftChildIdx]
                if(leftChild > element){
                    swap = leftChildIdx
                }
            }
            if(rightChildIdx < len){
                rightChild = this.values[rightChildIdx]
                if((swap===null && rightChild > element) ||
                  (swap!==null && rightChild > element)){
                      swap = rightChildIdx
                  }
            }
            if(swap === null) break
            this.values[idx] = this.values[swap]
            this.values[swap] = element
            idx = swap
        }    
    }
    extractMax(){
        let max = this.values[0]
        let end = this.values.pop()
        if(this.values.length !== 0){
            this.values[0] = end
        }
        this.sinkDown()
        return max
    }

우선 순위 큐 (응급실)

• 더 높은 우선순위를 가진 요소가 더 낮은 우선순위를 가진 요소보다 먼저 처리된다.
• 각 노드에 우선순위와 값이 저장된다.
• 최대이진힙 또는 최소이진힙을 사용하여 구현할수 있다. (배열로 구현하는거 보다 훨씬 빠르다)

class Node{
    constructor(val,priority){
        this.val = val
        this.priority=priority
    }
}
class PriorityQueue{
    constructor(){
        this.values = []
    }
    enqueue(val,priority){
        let newNode = new Node(val,priority)
        this.values.push(newNode)
        this.bubbleUp()
    }
    bubbleUp(){
        let idx = this.values.length-1
        let element = this.values[idx]
        while(idx > 0){
            let parentIdx = Math.floor((idx-1)/2)
            let parent = this.values[parentIdx]
            if(parent.priority > element.priority) break;
            this.values[parentIdx] = element
            this.values[idx] = parent
            idx = parentIdx
        }
    }
    dequeue(){
        const max = this.values[0]
        const end = this.values.pop()
        if(this.values.length !== 0){
            this.values[0] = end
            this.sinkDown()
        } 
        return max
    }
    sinkDown(){
        let idx = 0 
        let element = this.values[0]
        let length = this.values.length

        while(true){
            let swap = null
            let leftIdx = idx*2+1
            let rightIdx = idx*2+2
            if(leftIdx < length ){
                let leftChild = this.values[leftIdx]
                if(element.priority < leftChild.priority){
                    swap = leftIdx
                }
            }
            if(rightIdx <length){
                let rightChild = this.values[rightChild]
                if((swap === null && element.priority < rightChild.priority)||
                (swap!==null && element.priority < rightChild.priority)){
                    swap = rightIdx
                }
            }
            if(swap === null) break
            this.values[idx] = this.values[swap] 
            this.values[swap] = element
            idx = swap
        }
    }
}