힙 (Heap)

Jun 2k (Jun2)·2023년 9월 27일

CS강의 CS지식 WIL 자료구조&알고리즘

자료구조&알고리즘

목록 보기

11/19

우선순위 큐

FIFO인 큐와 달리 우선 순위가 높은 요소가 먼저 나가는 큐이다.
우선순위 큐는 자료구조가 아닌 개념이다.

이러한 우선순위 큐를 구현하기에 적합한 자료구조가 힙이다.

힙 (Heap)

이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제될 때 바로 정렬되는 특징이 있다.
우선 순위 큐와 힙이 같다고 오해할 수 있는 데 두 개는 완전히 다르다.

힙의 특징

우선순위가 높은 요소가 먼저 나가는 특징을 가진다.
루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 루트가 가장 작은 값이 되는 최소 힙(Min Heap)이 있다.

아쉽게도 자바스크립트에서는 힙을 직접 구현해서 사용해야 한다...

Heap 요소 추가

힙 요소 추가 알고리즘

요소가 추가될 때는 트리의 가장 마지막 정점에 위치한다.

요소 추가 후에 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다.

모든 과정을 반복하면 결국 가장 우선순위가 높은 정점이 루트가 된다.

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

Heap 요소 제거

힙 요소 제거 알고리즘

요소 제거는 루트 정점만 가능하다.

루트 정점이 제거된 후 가장 마니막 정점이 루트에 위치한다,

루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꾼다.

두 자식 정점이 우선순위가 더 낮을 때까지 반복한다.

완전 이진 트리의 높이는 log N이기에 힙의 요소 제거 알고리즘은 O(loh N) 시간 복잡도를 가진다.

JavaScript에서 힙 구현

힙 요소 추가 (최대 힙)

class MaxHeap {
  constructor() {
    this.heap = [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) {
      const temp = this.heap[parentIndex];
      this.heap[parentIndex] = value;
      this.heap[currentIndex] = temp;

      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }
}

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 ]

힙 요소 제거 (최대 힙)

pop() {
    // 임시로 루트를 추출하고 이를 마지막 요소로 대체
    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]) {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;
        currentIndex = rightIndex;
      } else {
        // 반대의 경우 왼쪽 정점과 바꿈
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[leftIndex];
        this.heap[leftIndex] = temp;
        currentIndex = leftIndex;
      }
      // 마지막으로 왼쪽, 오른쪽 정점 index를 다시 계산
      leftIndex = currentIndex * 2;
      rightIndex = currentIndex * 2 + 1;
    }

    return returnValue;
}

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