[알고리즘 정리] 03. Heap

📌 이번시간에는 Heap 자료구조에 대해 정리할 것 이다.

Heap 이란?

우선순위 큐(Priority Queue)를 구현하기 위한 자료구조.
힙은 일종의 완전 이진 트리이다.
종류에는 Max-heap, Min-heap이 존재한다.

Max-heap : 부모노드가 가장 큰 값을 가진다.
Min-heap : 부모노드가 가장 작은 값을 가진다.

구현

구현은 크게 두가지로 나뉜다.
1. 삽입 (insert)
2. 제거 (delete)

기본 골격

// 기본 힙 클래스 생성
class heap(){
	constructor(){
      this.heap = [];
    }
  	swap(a,b){
     	// 구조화할당을 이용하여 값을 swap 한다.
    	[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]]
    }
  	size(){
    	return this.heap.length;
    }
}

삽입코드

먼저 Max-heap 구현을 먼저 하자.
Max-heap에서 부모노드가 무조건 자식 노드보다 커야한다.
아래와 같은 트리를 배열로 나타내면 [7,6,5,4,3,2,1] 순으로 들어간다.

여기서 알 수 있는 것은 부모노드와 자식노드간의 인덱스 규칙이다.

좌측 자식 노드(leftChildNode) = (부모노드(parentIdx) * 2) + 1

우축 자식 노드(RightChildNode) = (부모노드(parentIdx) * 2) + 2

EX) 완전이진트리라고 가정했을때 부모인덱스 = 7 일경우 좌측 자식노드 = 15, 우측 자식노드 = 16이다.

이를 코드로 구현하자

	...
    insert(value){
      this.heap.push(value);
      let idx = this.heap.length-1;
      let parentIdx = Math.floor((idx-1)/2)
      while(this.heap[parentIdx] < value){
        this.swap(parentIdx,value);
        idx = parentIdx;
        parentIdx = Math.floor((idx-1)/2);
      }
    }

제거코드

Max-heap에서 제거코드는 최댓값을 제거하는 것이다.
즉 루트노드가 가장 큰 값이므로, 루트노드를 지워주는 것
과정은 아래와 같다

1. 루트노드를 제거한다.

2. 힙에 들어있는 가장 마지막 인덱스의 원소를 루트노드의 자리로 옮긴다.

3. Max-heap의 원리에 의거하여 heap을 재구성한다.

3번의 경우가 까다롭기 때문에, 경우의 수를 따져서 생각해보자.

1. 더 이상 자식노드가 없을 경우
2. 좌측 자식노드만 존재할 경우
3. 양쪽 자식노드가 존재할 경우
   3-1 좌측 자식노드가 우측 자식노드보다 클 경우
   3-2 우측 자식노드가 좌측 자식노드보다 클 경우

	...
    
    
    delete(){
      let idx = 0;
      let lastIdx = this.heap.length;
      this.swap(idx, lastIdx);
      let value = this.heap.pop();
      while(idx < lastIdx){
        let leftChildIdx = (idx*2)+1;
        let rightChildIdx = (idx*2)+2;
        // 더 이상 자식노드가 없는 경우
        if(leftChildIdx == lastIdx ){
          break;
        }else if(rightChildIdx == lastIdx){
          //좌측 노드만 존재
          if(this.heap[idx] <  this.heap[leftChildIdx]{
             	this.swap(idx, leftChildIdx);
          		idx = leftChildIdx;
          }else{
            break;
          }
        }else{
          //양쪽 노드가 다 존재
          //둘다 루트가 클 경우 -> 더 큰 값과 교체
          if(this.heap[leftChildIdx] > this.heap[idx] && this.heap[rightChildIdx] > this.heap[idx]){
            if(this.heap[leftChildIdx] > this.heap[rightChildIdx]){
              this.swap(leftChildIdx, idx);
              idx = leftChildIdx;
            }else{
              this.swap(rightChildIdx, idx);
              idx = rightChildIdx;
            }
          }else if(this.heap[leftChildIdx] > this.heap[idx] && this.heap[rightChildIdx] < this.heap[idx]){
          	this.swap(leftChildIdx, idx);
            idx = leftChildIdx;
          }else if(this.heap[leftChildIdx] < this.heap[idx] && this.heap[rightChildIdx] > this.heap[idx]){
            this.swap(rightChildIdx, idx);
            idx = rightChildIdx
          }else{
            break;
          }
        }
      }
    }