📔 [스터디] 학습노트 - Heap

 

 

 

 

 

 

---

 

 

✨ 힙(Heap)

1.1 정의

트리의 자료구조로, 특수한 종류의 이진트리이다.

가장 크거나 작은 원소를 알아내야 할 때 유리하다. 우선순위 큐를 구현할 때 효율적으로 쓰이는 자료구조이다.

 

 

 

1.2. js로 최소힙 구현하기

class MinHeap {
  constructor() {
    this.heap = [null]
  }

  push(value) {
    this.heap.push(value)
    let currentIndex = this.heap.length - 1
    let parentIndex = Math.floor(currentIndex / 2)

    // 현재 값보다 부모 값이 더 작을 떄 까지 (=최소힙의 형태를 만들 때 까지) swap 한다.
    while (parentIndex !== 0 && this.heap[currentIndex] < this.heap[parentIndex]) {
      this.swap(currentIndex, parentIndex)
      currentIndex = parentIndex
      parentIndex = Math.floor(currentIndex / 2)
    }
  }

  pop(deleteTarget) {
    if (this.isEmpty()) return
    if (this.heap.length === 2) return this.heap.pop() // 루트 정점만 남은 경우

    if (deleteTarget === TYPE.최댓값) {
      const parentIndex = Math.floor((this.heap.length - 1) / 2);
      const lastLeaf = this.heap.slice(parentIndex);
      const max = Math.max(...lastLeaf);
      this.swap(parentIndex + lastLeaf.indexOf(max), this.heap.length - 1);
      return this.heap.pop();
    }

    const returnValue = this.heap[1]
    this.heap[1] = this.heap.pop()

    let currentIndex = 1
    let leftIndex = 2
    let rightIndex = 3

    while (
        this.heap[leftIndex] && this.heap[currentIndex] > this.heap[leftIndex] ||
        this.heap[rightIndex] && this.heap[currentIndex] > this.heap[rightIndex]
        ) {

      switch (true) {
        case this.heap[leftIndex] === undefined:
          this.swap(rightIndex, currentIndex)
          break

        case this.heap[rightIndex] === undefined:
          this.swap(leftIndex, currentIndex)
          break

        case this.heap[leftIndex] > this.heap[rightIndex]:
          this.swap(currentIndex, rightIndex)
          currentIndex = rightIndex;
          break

        case this.heap[leftIndex] <= this.heap[rightIndex]:
          this.swap(currentIndex, leftIndex)
          currentIndex = leftIndex;
          break
      }

      leftIndex = currentIndex * 2
      rightIndex = currentIndex * 2 + 1
    }

    return returnValue
  }

  isEmpty() {
    return this.heap.length === 1
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  return() {
    return this.heap
  }
}