인프런 커뮤니티 질문&답변

최소 힙 insert

#reheapUp(index) {
  // index 0은 root

  if (index > 0) {
    // 부모 노드가 root가 아니면 계속 비교
    const parentIndex = Math.floor((index - 1) / 2);

    if (this.arr[index] < this.arr[parentIndex]) {
      // 값 바꾸기
      const temp = this.arr[index];
      this.arr[index] = this.arr[parentIndex];
      this.arr[parentIndex] = temp;
      this.#reheapUp(parentIndex);
    }
  }
}

// O (log n)
insert(value) {
  this.arr.push(value);

  this.#reheapUp(this.arr.length - 1);
}

const heap = new MinHeap();
// insert는 큰 값부터 넣고, root가 8이 되는지 확인
heap.insert(78);
heap.insert(56);
heap.insert(45);
heap.insert(32);
heap.insert(23);
heap.insert(19);
heap.insert(8);
// [8, 32, 19, 78, 45, 56, 23]
heap;

최대 힙 insert

#reheapUp(index) {
  // index 0은 root

  if (index > 0) {
    // 부모 노드가 root가 아니면 계속 비교
    const parentIndex = Math.floor((index - 1) / 2);

    if (this.arr[index] > this.arr[parentIndex]) {
      // 값 바꾸기
      const temp = this.arr[index];
      this.arr[index] = this.arr[parentIndex];
      this.arr[parentIndex] = temp;
      this.#reheapUp(parentIndex);
    }
  }
}

// O (log n)
insert(value) {
  this.arr.push(value);

  this.#reheapUp(this.arr.length - 1);
}

const heap = new MaxHeap();
// insert는 작은 값부터 넣고, root가 78이 되는지 확인
heap.insert(8);
heap.insert(19);
heap.insert(23);
heap.insert(32);
heap.insert(45);
heap.insert(56);
heap.insert(78);
// [78, 32, 56, 8, 23, 19, 45]
heap;

최대 힙 -> 최소 힙

// 최소 힙 유지 함수
#heapifyMin(index) {
  // 수정, 삭제

  const leftIndex = index * 2 + 1;
  const rightIndex = index * 2 + 2;

  const smallerIndex =
    (this.arr[leftIndex] || 0) < (this.arr[rightIndex] || 0)
      ? leftIndex
      : rightIndex;

  if (this.arr[index] > this.arr[smallerIndex]) {
    // 값 바꾸기
    const temp = this.arr[index];
    this.arr[index] = this.arr[smallerIndex];
    this.arr[smallerIndex] = temp;
    // 재귀적으로 최소 힙 유지
    this.#heapifyMin(smallerIndex);
  }
}

toMinHeap() {
  // O(1/2n)
  for (let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i--) {
    this.#heapifyMin(i);
  }
}

const heap = new MaxHeap();
// insert는 작은 값부터 넣고, root가 78이 되는지 확인
heap.insert(8);
heap.insert(19);
heap.insert(23);
heap.insert(32);
heap.insert(45);
heap.insert(56);
heap.insert(78);
// [78, 32, 56, 8, 23, 19, 45]
heap.toMinHeap();
// [8, 23, 19, 32, 78, 56, 45]
heap;

// 최소 힙 insert 결과 값
[8, 32, 19, 78, 45, 56, 23]

// 최대 힙 insert 결과 값
[78, 32, 56, 8, 23, 19, 45]

// 최대 힙 -> 최소 힙 결과 값
[8, 23, 19, 32, 78, 56, 45]

최소힙 insert 결과 값과 최대 힙 -> 최소 힙 결과 값은 서로 다른데 최소 힙의 조건은 아래가 크고, 위가 작다. 라고 하셨으니 결과 값은 달라도 최소 힙의 조건이 맞으니 최대 힙 -> 최소 힙 변환 코드가 맞는걸까요?