이진 힙(Binary Heaps)

📌 Binary Heaps

: 이진 탐색 트리(BST)와 유사하지만 다른 규칙이 있다.

• Max Binary Heap : 부모 노드들이 항상 자식 노드들 보다 크다.
• Min Binary Heap : 부모 노드들이 항상 자식 노드들 보다 작다.

참고 | 힙은 트리의 한 종류이다.

Max Binary Heap

• 각각의 부모는 최대 2개의 자식 노드를 가질 수 있다.
• 부모 노드는 자식 노드들보다 항상 크다.
• 언제나 가능한 가장 적은 공간을 차지한다.
• 왼쪽 노드가 오른쪽 노드보다 먼저 채워져야 한다.
• 형제 노드 간에는 관계가 존재하지 않는다.

Min Binary Heap

• 각각의 부모는 최대 2개의 자식 노드를 가질 수 있다.
• 부모 노드는 자식 노드들보다 항상 작다.
• 언제나 가능한 가장 적은 공간을 차지한다.
• 왼쪽 노드가 오른쪽 노드보다 먼저 채워져야 한다.
• 형제 노드 간에는 관계가 존재하지 않는다.

⭐️ 이진 탐색 트리와 이진 힙 구별하기

아래는 이진 탐색 트리로, 이진 힙이 될 수 없다.
부모 노드들보다 자식 노드들이 더 큰 경우가 존재하기 때문에 max binary heap이 될 수 없고, 부모 노드들보다 자식노드들이 더 작은 경우도 존재하기 때문에 min binary heap도 될 수 없기 때문이다.

활용 분야

1. 자주 사용되는 자료 구조중 하나인 우선순위 큐 라는 것을 만들때 사용된다.
2. 트리 순회 알고리즘에 종종 쓰인다.

Max Binary Heap 구현

배열/리스트를 이용해 구현할 수 있다.

1. insert( ) 메소드

원리 : 맨 끝에 새로운 값을 push하고 부모보다 크기가 클 경우 bubble up 해서 자리를 바꾼다.

⭐️ 부모의 위치를 기반으로 자식 찾기

: 부모 위치가 n 일 때 자식의 위치는 2n+1, 2n+2, 자식 위치가 n 일 때는 부모 위치가 (n-1)/2 에 내림한 값

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[parentIdx] = element;
            this.values[idx] = parent;
            idx = parentIdx;
        }
    }
}

let heap = new MaxBinaryHeap();
heap.insert(41);
heap.insert(39);
heap.insert(33);
heap.insert(18);
heap.insert(27);
heap.insert(12);
heap.insert(55);

2. remove( ) 메소드

메소드명은 remove, extractMax 혹은 extractMaximum 등으로 불린다.

1. max binary heap 에서는 최댓값(root)을 제거해 반환하고, min binary heap에서는 최솟값(root)을 제거해 반환한다.
2. 마지막 값을 root에 대신 넣어준다.
3. bubble down(sink down 등 다양한 이름으로 불림) 해준다.(새로운 root를 순서에 맞게 정리)

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[parentIdx] = element;
            this.values[idx] = parent;
            idx = parentIdx;
        }
    }
  	extractMax(){
     	const max = this.values[0];
      	const end = this.values.pop();
      	if(this.values.length > 0){
         	this.values[0] = end;
          	this.sinkDown();
        }
      	return max;
    }
  	bubbleDown(){
     	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 > element){
                 	swap = leftChildIdx; 
                }
            }
            if(rightChildIdx < length){
             	rightChild = this.values[rightChildIdx];
              	if(
                  	(swap === null && rightChild > element) || 
                  	(swap !== null && rightChild > leftChild)
                ){
                  	swap = rightChildIdx;
                }
            }
         	if(swap === null) break;
          	this.values[idx] = this.values[swap];
          	this.values[swap] = element;
          	idx = swap;
        }
    }
}

let heap = new MaxBinaryHeap();
heap.insert(41);
heap.insert(39);
heap.insert(33);
heap.insert(18);
heap.insert(27);
heap.insert(12);
heap.insert(55);

⭐️ 이진 힙의 Big O

삽입,삭제 : O(log n)

탐색 : O(n)

삽입과 삭제에 있어 성능이 매우 좋다.
각 레벨마다 한 번씩만 비교를 하면 되기 때문에 log n 이다.

탐색은 BST를 사용하는 것이 더 좋다. 힙은 좌/우로 대소 관계에 따른 정렬이 되어 있지 않기 때문이다.