힙 + 우선 순위 큐

힙

이진 탐색 트리와 비슷

- 왼쪽을 먼저 채워야 한다 (왼쪽 -> 오른쪽)

- 우선 순위 큐 같은 데이터 구조를 코딩하는데도 유용하다

 

- 배열의 인덱스 순서로 부모의 인덱스가 n이라고 했을때 왼쪽 자식은 2n+1 / 오른쪽 자식은 2n+2에 저장된다

[100,19,36,17,3,25,1,2,7] -> 19의 인덱스는 1 / 왼쪽자식은 17 인덱스는 3 /오른쪽 자식은 3 인덱스는 4

반대의 경우(자식에서 부모를 찾는경우) 자식의 인덱스가 n일때 부모의 인덱스는 floor((n-1)/2)이다

 

- 이진 탐색 트리처럼 큰 값이 오른쪽 / 작은 값이 왼쪽에 배치된다는 약속을 가지고 있지 않다.

 

[모든 참조]

https://en.wikipedia.org/wiki/Binary_heap

Binary heap - Wikipedia

Big O

삽입 - O(log N)

제거 - O(log N)

탐색 - O(N)

 

최대 이진 힙

부모 노드가 자식 노드보다 항상 큰 값을 가짐 ( 부모 노드 > 자식 노드)
형제 노드에서는 규칙이 따로 없다
가능한 가장 적은 공간을 차지한다(모든 left,right가 채워지면서 내려가고)
한 줄에서는 왼쪽 자식이 언제나 먼저 채워짐

https://ko.wikipedia.org/wiki/%ED%9E%99_%28%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0%29

삽입 + 버블 업

Insert로 요소가 맨 뒤에 추가되었을때 위치가 잘못되어 있어면 버블업을 통해 올바른 위치로 옮겨준다

버블 업은 부모와 요소의  값을 비교해서 위치를 바꿔주는 기능을 가진 함수이다

class MaxBinaryHeap{
  constructor(){
    this.values=[]
  }
  insert(ele){
    this.values.push(ele)
    this.bubbleUp()
  }
  bubbleUp(){
    let idx=this.values.length-1;
    const element=this.values[idx]
    while(true){
      let parentIdx=Math.floor((idx-1)/2)
      let parent=this.values[parentIdx]
      if(element<=parent) break
        this.values[parentIdx]=element
        this.values[idx]=parent
        idx=parentIdx
    }
  }
}

제거(extractMax)

The procedure for deleting the root from the heap (effectively extracting the maximum element in a max-heap or the minimum element in a min-heap) and restoring the properties is called down-heap (also known as bubble-own, percolate-down, sift-down, sink-down, trickle down, heapify-down, cascade-down, extract-min or extract-max, or simply heapify)

순서

1. root와 마지막 레벨에 있는 마지막 요소와 바꾼다

2. down-heap(...)을 호출해서 아래 요소와 계속 비교해서 자리를 맞춰준다

[!] 값을 바꿀 때 왼쪽,오른쪽 노드의 값 중에서 더 큰 노드와 자리를 바꾼다(한번만 실행)

  remove(){
    const max=this.values[0]
    const end=this.values.pop()
    if(this.values.length>0){
    	this.values[0]=end
    	this.downHeap()
    }
    return max
  }
        0  1  2
  힙 : [33,40,51,19,22,11]
  
  !) [33,51,40...] 
  downHeap(){
    let idx=0
    const length=this.values.length
    const element=this.values[0]
    while(true){
      let leftChildIdx=2*idx+1
      let rightChildIdx=2*idx+2
      let letfChild,rightChild
      let swap=null;
      인덱스범위가 배열을 넘어서면 안되므르
      if(leftChildIdx<length){
        letfChild=this.values[leftChildIdx]
        if(letfChild>element){
        //33 과 40을 비교했을 때 40이 크므로 swap은 1
          swap=leftChildIdx
        }
      }
      if(rightChildIdx<length){
        rightChild=this.values[rightChildIdx]
        
        !) element인 33보다 left,right의 값이 더 크기에 이 코드 순서상 swap=leftChildIdx를 지난후
        여기 rightChildIdx와 비교를 해서 swap 값이 2가 되는데 여기 배열에서는 swap이 2가되는 순간
        최대 이진 힙이 성립하지 않으므로 아래 2가지 조건을 만들었다
        
        if(swap === null && rightChild > element || (swap !== null && rightChild>letfChild)){
          swap=rightChildIdx
        }
      }

      if(swap===null) break
      this.values[idx]=this.values[swap]
      this.values[swap]=element
      idx=swap
    }
  }

 

우선 순위 큐(Queue)

- 데이터 모음의 각 노드,요소가 각각에 대한 우선순위 값을 가지고 있는 것

-  우선순위가 높은 데이터가 먼저 빠져나간다

- 우선 순위 큐는 힙과 별개다 -> 일반적으로 힙으로 만든다고 생각

- 보통 낮은 숫자가 더 높은 우선순위를 의미함

 

최소 이진 힙 사용

# insert() -> enqueue()

# priority-> 우선순위를 추가

# 최대 이진 힙에서 사용했던 코드의 부등호 방향을 반대로 바꿔줬다
# remove() -> dequeue()

# const max -> const min

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;
        const element = this.values[idx];
        while(idx > 0){
            let parentIdx = Math.floor((idx - 1)/2);
            let parent = this.values[parentIdx];
            if(element.priority >= parent.priority) break;
            this.values[parentIdx] = element;
            this.values[idx] = parent;
            idx = parentIdx;
        }
    }
    dequeue(){
        const min = this.values[0];
        const end = this.values.pop();
        if(this.values.length > 0){
            this.values[0] = end;
            this.sinkDown();
        }
        return min;
    }
    sinkDown(){
        let idx = 0;
        const length = this.values.length;
        const element = this.values[0];
        while(true){
            let leftChildIdx = 2 * idx + 1;
            let rightChildIdx = 2 * idx + 2;
            let leftChild,rightChild;
            let swap = null;

            if(leftChildIdx < length){
                leftChild = this.values[leftChildIdx];
                if(leftChild.priority < element.priority) {
                    swap = leftChildIdx;
                }
            }
            if(rightChildIdx < length){
                rightChild = this.values[rightChildIdx];
                if(
                    (swap === null && rightChild.priority < element.priority) || 
                    (swap !== null && rightChild.priority < leftChild.priority)
                ) {
                   swap = rightChildIdx;
                }
            }
            if(swap === null) break;
            this.values[idx] = this.values[swap];
            this.values[swap] = element;
            idx = swap;
        }
    }
}

class Node {
    constructor(val, priority){
        this.val = val;
        this.priority = priority;
    }
}

let ER = new PriorityQueue();
ER.enqueue("common cold",5)
ER.enqueue("gunshot wound", 1)
ER.enqueue("high fever",4)
ER.enqueue("broken arm",2)
ER.enqueue("glass in foot",3)

 

 

최소 이진 힙

자식 노드 > 부모 노드

udemy 강의자료