섹션 24 : 이진힙

max 이진힙은,

• 최대 자식 2개를 가지고 있다.
• 크기에 상관없이 왼쪽부터 채운다.
• 부모 노드는 항상 자식 노드보다 크다.

배열에서 부모, 자식 노드 찾는 법

부모 노드 찾는 법

• Math.floor((자식 노드idx - 1)/2)
  자식 노드 찾는 법
• 왼쪽 자식 찾기 : (부모 idx * 2) + 1
• 오른쪽 자식 찾기 : (부모 idx * 2) +2

insert 메소드

• 배열 끝에 push 한 후,
• bubble up을 통해 제자리를 찾는다
  => 부모노드를 찾아서 부모보다 해당노드가 더크면 자리를 바꾼다. [반복적으로]

class MaxBinaryHeap(){
	constructor(){
    	this.values = []; 
    }
  	insert(element){
    	this.values.push(element);
        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 < parent) break; 
          this.values[idx] = parent; 
          this.values[parentIdx] = element; 
          idx = parentIdx;  
}

ExtractMax 메소드

class MaxBinaryHeap(){
	constructor(){
    	this.values = []; 
    }
  	insert(element){
    	this.values.push(element);
        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 < parent) break; 
          this.values[idx] = parent; 
          this.values[parentIdx] = element; 
          idx = parentIdx;  
}
      
     extraMax(){
     	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; 
        const length = this.values.length; 
        const element = this.values[0]
        while(true){
          let leftChildIdx = idx * 2 +1; 
          let rightChildIdx = idx *2 +2; 
          let leftChild, rightChild; 
          let swap = null; 
          if(leftChildIdx < length){
            leftChild = this.values[leftChildIdx];
            if(leftChild > element){
            	swap = leftChildIdx; 
            }
      }
          if(
            (swap === null && rightChild > element) || 
            (swap !== null && rightChild > leftChild)
            ){
          		swap = rightChildIdx; 
          }
        }
        if(swap === null) break; 
        this.value[idx] = this.values[swap]; 
        this.values[swap] = element; 
        idx = swap; 
      }
    } 
}

우선순위 큐

우선순위 큐 : 각 요소가 우선순위를 가지고 있는 데이터 구조다.
더 높은 우선순위를 가진 요소들이 먼저 처리된다.
=>
언제사용 하는가?

• 서로 다른 우선순위를 가지는 데이터나 정보를 관리할 필요가 있을 때
• 무언가를 입력하는데 입력하는 것이 순서대로 낮은 우선순위를 가져야 할 때
• 순서에 맞추어 데이터를 입력해야 할 때
• 무언가를 응급실과 같은 방식으로 추가하게 될 때 사용