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

class MinHeap {
  // 최소힙
  arr = [];

  #reheapUp(index) {
    if (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.arr[index] < this.arr[parentIndex]) {
        const tmp = this.arr[index];
        this.arr[index] = this.arr[parentIndex];
        this.arr[parentIndex] = tmp;

        this.#reheapUp(parentIndex);
      }
    }
  }

  insert(value) {
    const index = this.arr.length;
    this.arr[index] = value; // 마지막에 값을 넣어준다.
    this.#reheapUp(index);
  }

  #reHeapDown(index) {
    const leftIndex = index * 2 + 1; // 왼쪽 Index
    if (leftIndex < this.arr.length) {
      // 만약에 왼쪽 인덱스가 총 배열의 길이보다 작은경우
      const rightIndex = index * 2 + 2;
      const smaller =
        this.arr[leftIndex] > this.arr[rightIndex] ? leftIndex : rightIndex;
      if (this.arr[index] < this.arr[smaller]) {
        const temp = this.arr[index];
        this.arr[index] = this.arr[smaller];
        this.arr[smaller] = temp;
        this.#reHeapDown(smaller);
      }
    }
  }

  remove() {
    // root만 remove
    if (this.arr.length === 0) {
      return false;
    }

    if (this.arr.length === 1) {
      // 마지막 하나 남으면 pop해서 리턴해주기
      return this.arr.pop();
    }

    const root = this.arr[0];
    this.arr[0] = this.arr.pop();
    this.#reHeapDown(0);
    return root;
  }

  sort() {
    // 힙 정렬
    const sortedArray = [];
    while (this.arr.length > 0) {
      sortedArray.push(this.remove());
    }
    return sortedArray;
  }

  search(value) {
    for (let i = 0; i < this.arr.length; i++) {
      if (arr[i] === value) {
        return i;
      }
    }
  }
}

const minheap = new MinHeap();
minheap.insert(78);
minheap.insert(56);
minheap.insert(45);
minheap.insert(32);
minheap.insert(23);
minheap.insert(19);
minheap.insert(8);
console.log(minheap.arr);
minheap.remove();
minheap.remove();
minheap.remove();
minheap.remove();
minheap.remove();
minheap.remove();

최대힙 코드를 최소힙 구하기 코드로 바꿔봤습니다.

질문1) 최소힙 구하기 remove 코드가 맞을까요?

질문2) 최대힙이든 최소힙이든 sort 메서드가 sort 메서드 호출시 remove 메서드를 while문 루프로 호출하여서 sort 메서드 실행 후에 this.arr가 당연하게 빈배열이 되는데 while문 전에 this.arr를 변수에 담아두었다가 while 루프가 끝난후에 다시 this.arr 멤버변수에 넣어주어야 하는거 아닌가 궁금합니다.