힙(Heap)

: 이진 트리(Binary Tree) 형태를 가지며, 우선순위가 높은 요소를 루트에 두고 먼저 나가게 하기 위해 요소가 삽입, 삭제될 때 바로바로 정렬되는 특징이 있다.

힙의 특징

• 우선순위가 높은 요소가 먼저 나가는 특징을 가진다. (우선순위 큐)
• 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 루트가 가장 작은 값이 되는 최소 힙(Min Heap)이 있다.
• JavaScript에서는 직접 구현해서 사용해야 한다.

힙의 종류

최대 힙(Max Heap)

부모 노드는 자식 노드보다 항상 크다.

최소 힙(Min Heap)

부모 노드는 자식 노드보다 항상 작다.

힙의 연산

Insert O(log N)

1. 요소가 추가될 때는 트리의 가장 마지막에 정점에 위치한다.
2. 추가된 요소가 부모 정점보다 우선순위가 높다면, 부모 정점과 swap한다.
3. 이 과정을 반복(버블링)하면 결국 가장 우선순위가 높은 정점이 루트가 된다.

➡️ 완전 이진 트리의 높이는 log N이기 때문에, 힙의 요소 추가 알고리즘은 O(log N)의 시간복잡도를 가진다.

Delete O(log N)

1. 힙에서는 항상 루트 노드가 제거된다.
2. 그런 다음 트리의 가장 마지막에 있는 정점을 루트로 설정한다.
3. 이때 다시 우선순위대로 트리가 재정렬될 때까지 swap이 일어난다.

➡️ 마찬가지로 O(log N)의 시간복잡도를 가진다.

Top

• O(1) : 루트 요소 혹은 arr[0]을 반환하면 된다.

JavaScript로 힙 구현하기

• 트리구조의 힙을 배열로 나타내면, 다음처럼 index를 가지게 된다.
• 이때 부모 요소의 index는 자식 요소의 index를 2로 나눈 값이다.
  e.g. index가 6, 7인 요소의 부모 요소의 index는 3이다.

 class MaxHeap {
   constructor() {
     this.heap = [null]; // 배열의 0번째 요소는 편의상 null을 준다.
   }
   
   // Insert
   insert(value) {
     this.heap.push(value); // 배열의 마지막에 요소를 추가한다.
     let currentIndex = this.heap.length - 1; // 추가된 요소의 인덱스와
     let parentIndex = Math.floor(currentIndex / 2); // 부모 요소의 인덱스를 구한다.
     
     // 만약 부모 요소가 추가된 요소보다 크다면, 부모 요소의 인덱스가 0이 될 때까지 아래 코드를 반복한다.(루트까지 비교)
  	 while (parentIndex !== 0 && this.heap[parentIndex] < value) {
       [this.heap[currentIndex], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[currentIndex]]; // 둘을 swap한다.
       currentIndex = parentIndex; // 추가된 요소의 인덱스를 업데이트한다.
       parentIndex = Math.floor(currentIndex / 2); // 부모 요소의 인덱스도 업데이트한다.
     }
   }
   
   // Delete
   delete() {
     const returnValue = this.heap[1]; // 루트 요소를 반환하기 위해 변수에 저장한다.
     this.heap[1] = this.heap.pop(); // 루트 요소를 가장 마지막 요소로 대체한다.
     
     let currentIndex = 1;
     let leftIndex = 2;
     let rightIndex = 3; // 루트에서부터 아래로 내려가기 위한 변수들을 설정해준다.
     
     while ( // 하위 요소들이 현재 정점보다 크다면 아래 코드를 실행한다.
       this.heap[currentIndex] < this.heap[leftIndex] ||
       this.heap[currentIndex] < this.heap[rightIndex]  
     ) {
       if (this.heap[leftIndex] < this.heap[rightIndex]) { // 왼쪽 요소와 오른쪽 요소중 더 큰 요소를 현재 요소와 swap한다.
       [this.heap[currentIndex], this.heap[rightIndex]] = [this.heap[rightIndex], this.heap[currentIndex]];
       } else {
         [this.heap[currentIndex], this.heap[leftIndex]] = [this.heap[leftIndex], this.heap[currentIndex]];
       }
       leftIndex = currentIndex * 2;
       rightIndex = currentIndex * 2 + 1; // 한 레벨 아래로 내려간다.
     }
     return returnValue; // 저장해두었던 루트 요소를 반환한다.
   }
 }