Heap(힙)

힙이란?

이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징이 있다.

힙의 특징

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

힙은 추가,삭제가 핵심 로직이다.

힘 요소 추가 알고리즘

• 요소가 추가될 때는 트리의 가장 마지막에 정점에 위치한다.
• 추가 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다.
• 이 과정을 반복하면 결국 가장 우선순위가 높은 정점이 루트가 된다.
• 완전 이진 트리의 높이는 log N이기에 힙의 요소 추가 알고리즘은 O(log N) 시간 복잡도를 가진다.

힙 요소 제거 알고리즘

• 요소 제거는 루트 정점만 가능하다.
• 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치한다.
• 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꾼다.
• 두 자식 정점이 우선순위가 더 낮을 때 까지 반복한다.
• 완전 이진 트리의 높이는 log N이기에 힙의 요소 제거 알고리즘은O(log N)시간복잡도를 가진다.

JS 코드로 구현(최대힙)

class MaxHeap {
  constructor() {
    this.heap = [null]; // 인덱스 위치를 1로 시작하기 편하기 0번 위치는 null 로 할당.
  }

  push(value) {
    this.heap.push(value); //처음에 맨 마지막에 값을 넣어준다.
    let currentIndex = this.heap.length - 1; //추가된 값 위치.
    let parentIndex = Math.floor(currentIndex / 2); //추가된 노드의 부모노드의 위치

    while (parentIndex !== 0 && this.heap[parentIndex] < value) {
      // 부모 위치가 0보다 작지 않으면서 부모노드가 새로추가된 값보다 작을때까지 while문 실행.
      const temp = this.heap[parentIndex]; // 임시값으로 부모노드 값 가져온다.
      // 부모노드와 자식노드 스왑.
      this.heap[parentIndex] = value;
      this.heap[currentIndex] = temp;
      // 다음 부모 노드를 찾기위해서 현재노드위치와 부모노드 위치 스왑.
      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }

  pop() {
    const returnValue = this.heap[1]; // root노드 가져오기.
    this.heap[1] = this.heap.pop(); // 맨마지막 노드를 pop하고 rootnode로 삽입.

    let currentIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;
    while (
      this.heap[currentIndex] < this.heap[leftIndex] ||
      this.heap[currentIndex] < this.heap[rightIndex]
    ) {
      // 현재 부모노드가 자기 자식노드(왼쪽노드, 오른쪽노드) 둘중 하나의 값보다 작을때 까지 while문 실행
      if (this.heap[leftIndex] < this.heap[rightIndex]) {
        // 오른쪽이 왼쪽보다 클때 부모노드와 오른쪽노드와 스왑.
        [this.heap[currentIndex], this.heap[rightIndex]] = [
          this.heap[rightIndex],
          this.heap[currentIndex],
        ];
        currentIndex = rightIndex;
      } else {
        [this.heap[currentIndex], this.heap[leftIndex]] = [
          this.heap[leftIndex],
          this.heap[currentIndex],
        ];
        currentIndex = leftIndex;
      }
      leftIndex = currentIndex * 2;
      rightIndex = currentIndex * 2 + 1;
    }
    return returnValue;
  }
}
const heap = new MaxHeap();
heap.push(45);
heap.push(36);
heap.push(54);
heap.push(27);
heap.push(63);
console.log(heap.heap); //[ null, 63, 54, 45, 27, 36 ]

const array = [];
array.push(heap.pop());
array.push(heap.pop());
array.push(heap.pop());
array.push(heap.pop());
array.push(heap.pop());
console.log(array); //[ 63, 54, 45, 36, 27 ]