비전공자의 전공자 따라잡기 - 자료구조(with JavaScript)

heapify

[숙제] minHeap 구현, maxHeap -> minHeap , minHeap -> maxHeap

해결된 질문

작성

128

수정됨

minHeap 구현

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 (this.arr[i] === value) {
        return i;
      }
    }
    return null;
  }

  // 특정값 수정
  update(value, newValue) {
    const index = this.search(value);
    if (index === null) {
      return false;
    }
    this.arr[index] = newValue;
    for (let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i--) {
      this.#heapify(i);
    }
  }

  // 특정값 삭제
  removeValue(value) {
    const index = this.search(value);
    if (index === null) {
      return false;
    }

    // 특정값의 index를 splice를 이용하여 없애버린다.
    this.arr.splice(index, 1);

    for (let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i--) {
      // 이렇게 했을때 힙이 깨질 수 있기 떄문에 heapify 해준다
      this.#heapify(i);
    }
  }

  transFormMaxHeap() {
    for (let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i--) {
      // i가 2부터 시작
      // 이렇게 했을때 힙이 깨질 수 있기 떄문에 heapify 해준다
      this.#maxHeapify(i);
    }
    return this.arr;
  }

  // 특정값을 수정하거나 특정값을 삭제하거나
  #heapify(index) {
    const leftIndex = index * 2 + 1; // 왼쪽 Index 78의 왼쪽 5: 23
    const rightIndex = index * 2 + 2; // 오른쪽 6: undefined

    const smaller =
      (this.arr[leftIndex] || Number.MAX_SAFE_INTEGER) <
      (this.arr[rightIndex] || Number.MAX_SAFE_INTEGER)
        ? 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.#heapify(smaller);
    }
  }

  #maxHeapify(index) {
    const leftIndex = index * 2 + 1; // 왼쪽 Index
    const rightIndex = index * 2 + 2;
    const bigger =
      (this.arr[leftIndex] || 0) > (this.arr[rightIndex] || 0)
        ? leftIndex
        : rightIndex;

    if (this.arr[index] < this.arr[bigger]) {
      const temp = this.arr[index];
      this.arr[index] = this.arr[bigger];
      this.arr[bigger] = temp;

      // 재귀 호출 해주어야 된다!
      this.#maxHeapify(bigger);
    }
  }
}

최소 힙 insert

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);

// 결과 [8, 32, 19, 78, 45, 56, 23]

결과 그림

최소힙 remove

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);

minheap.remove();
minheap.remove();
minheap.remove();
minheap.remove();
minheap.remove();
minheap.remove();

// 8 , 32, 19, 78, 45 ,56, 23
// 19, 32, 23, 78, 45, 56
// 23, 32, 56, 78, 45
// 32, 45, 56, 78
// 45, 78, 56
// 56, 78
// 78

최소힙 update

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);

minheap.update(32, 90);
// [8, 32, 19, 78, 45, 56, 23]
// 결과 -> [8, 45, 19, 78, 90, 56, 23]

최소힙 removeValue

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);

minheap.removeValue(19);
// [8, 45, 19, 78, 90, 56, 23]
// 결과 -> [8, 45, 23, 90, 56, 78]

최소힙 -> 최대힙

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.transFormMaxHeap());
// [ 8, 32, 19, 78, 45, 56, 23 ]
// 결과 -> [78, 45, 56, 32, 8, 19, 23]

최대힙 -> 최소힙

class MaxHeap {
  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 bigger =
        this.arr[leftIndex] > this.arr[rightIndex] ? leftIndex : rightIndex;
      if (this.arr[index] < this.arr[bigger]) {
        const temp = this.arr[index];
        this.arr[index] = this.arr[bigger];
        this.arr[bigger] = temp;
        this.#reHeapDown(bigger);
      }
    }
  }

  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 (this.arr[i] === value) {
        return i;
      }
    }
    return null;
  }

  // 특정값 수정
  update(value, newValue) {
    const index = this.search(value);
    if (index === null) {
      return false;
    }
    this.arr[index] = newValue;
    for (let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i--) {
      this.#heapify(i);
    }
  }

  // 특정값 삭제
  removeValue(value) {
    const index = this.search(value);
    if (index === null) {
      return false;
    }

    // 특정값의 index를 splice를 이용하여 없애버린다.
    this.arr.splice(index, 1);

    for (let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i--) {
      // 이렇게 했을때 힙이 깨질 수 있기 떄문에 heapify 해준다
      this.#heapify(i);
    }
  }

  transFromMinHeap() {
    for (let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i--) {
      // i가 2부터 시작
      // 이렇게 했을때 힙이 깨질 수 있기 떄문에 heapify 해준다
      this.#minHeapify(i);
    }
    return this.arr;
  }

  // 특정값을 수정하거나 특정값을 삭제하거나
  #heapify(index) {
    const leftIndex = index * 2 + 1; // 왼쪽 Index
    const rightIndex = index * 2 + 2;
    const bigger =
      (this.arr[leftIndex] || 0) > (this.arr[rightIndex] || 0)
        ? leftIndex
        : rightIndex;

    if (this.arr[index] < this.arr[bigger]) {
      const temp = this.arr[index];
      this.arr[index] = this.arr[bigger];
      this.arr[bigger] = temp;

      this.#heapify(bigger);
    }
  }

  // 특정값을 수정하거나 특정값을 삭제하거나
  #minHeapify(index) {
    const leftIndex = index * 2 + 1; // 왼쪽 Index 78의 왼쪽 5: 23
    const rightIndex = index * 2 + 2; // 오른쪽 6: undefined

    const smaller =
      (this.arr[leftIndex] || Number.MAX_SAFE_INTEGER) <
      (this.arr[rightIndex] || Number.MAX_SAFE_INTEGER)
        ? 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.#minHeapify(smaller);
    }
  }
}

const heap = new MaxHeap();
heap.insert(8);
heap.insert(19);
heap.insert(23);
heap.insert(32);
heap.insert(45);
heap.insert(56);
heap.insert(78);

console.log(heap.transFormMinHeap());
// [78, 32, 56, 8, 23, 19, 45]
// -> 결과 [8, 23, 19, 32, 78, 56, 45]

질문1) maxheap(minheap) 코드 구현시 heapify 메서드에서 재귀호출 되어야 되지 않는가요?

강의에서는 heapify 메서드 구현시 재귀 호출 부분이 빠져있는것 같아서 질문 드립니다. 아니라면 죄송합니다.

#heapify(index) {
    const leftIndex = index * 2 + 1; // 왼쪽 Index
    const rightIndex = index * 2 + 2;
    const bigger =
      (this.arr[leftIndex] || 0) > (this.arr[rightIndex] || 0)
        ? leftIndex
        : rightIndex;

    if (this.arr[index] < this.arr[bigger]) {
      const temp = this.arr[index];
      this.arr[index] = this.arr[bigger];
      this.arr[bigger] = temp;

      // 여기 빠진것 같습니다!
      this.#heapify(bigger);
    }
  }

javascript 코딩-테스트 알고리즘

답변 1

제로초(조현영)

지식공유자

heapify는 재귀 안 해도 됩니다. 그냥 for문 안에서 heapify 호출하면 끝입니다.

rhkdtjd_12

질문자

아하 그렇군요. 생각 해보니까 heapify는 이미 최대힙(또는 최소힙)을 보장하는 힙에 특정값을 update하거나 remove 하는 경우이기 때문에 그냥 for문 안에서 heapify 호출하면 되는거고

숙제중에서 제가 작성한 코드에서 최소힙 -> 최대힙으로 변경할때 minHeapify 메서드로 변환할때는 최소힙을 최대힙으로 다시 변경 하는거기 때문에 insert나 remove때처럼 재귀호출이 필요한거 제가 이해한게 맞을까요?

rhkdtjd_12

질문자

제가 이부분이 왜 궁금했었냐면요

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 (this.arr[i] === value) {
        return i;
      }
    }
    return null;
  }

  // 특정값 수정
  update(value, newValue) {
    const index = this.search(value);
    if (index === null) {
      return false;
    }
    this.arr[index] = newValue;
    for (let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i--) {
      this.#heapify(i);
    }
  }

  // 특정값 삭제
  removeValue(value) {
    const index = this.search(value);
    if (index === null) {
      return false;
    }

    // 특정값의 index를 splice를 이용하여 없애버린다.
    this.arr.splice(index, 1);

    for (let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i--) {
      // 이렇게 했을때 힙이 깨질 수 있기 떄문에 heapify 해준다
      this.#heapify(i);
    }
  }

  transFormMaxHeap() {
    for (let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i--) {
      // i가 2부터 시작
      // 이렇게 했을때 힙이 깨질 수 있기 떄문에 heapify 해준다
      this.#maxHeapify(i);
    }
    return this.arr;
  }

  // 특정값을 수정하거나 특정값을 삭제하거나
  #heapify(index) {
    const leftIndex = index * 2 + 1; // 왼쪽 Index 78의 왼쪽 5: 23
    const rightIndex = index * 2 + 2; // 오른쪽 6: undefined

    const smaller =
      (this.arr[leftIndex] || Number.MAX_SAFE_INTEGER) <
      (this.arr[rightIndex] || Number.MAX_SAFE_INTEGER)
        ? leftIndex
        : rightIndex;

    if (this.arr[index] > this.arr[smaller]) {
      const temp = this.arr[index];
      this.arr[index] = this.arr[smaller];
      this.arr[smaller] = temp;

      
    }
  }

  #maxHeapify(index) {
    const leftIndex = index * 2 + 1; // 왼쪽 Index
    const rightIndex = index * 2 + 2;
    const bigger =
      (this.arr[leftIndex] || 0) > (this.arr[rightIndex] || 0)
        ? leftIndex
        : rightIndex;

    if (this.arr[index] < this.arr[bigger]) {
      const temp = this.arr[index];
      this.arr[index] = this.arr[bigger];
      this.arr[bigger] = temp;

      // 재귀 호출 해주어야 된다!
      this.#maxHeapify(bigger);
    }
  }
}

제일 첫번째 8을 90으로 update를 하게 됬을때

재귀호출 없을때

minheap.update(8, 90);
// [8, 32, 19, 78, 45, 56, 23]
// -> [19, 32, 90, 78, 45, 56, 23]

재귀 호출을 넣었을때

minheap.update(8, 90);
// [8, 32, 19, 78, 45, 56, 23]
// -> [19, 32, 23, 78, 45, 56, 90]

이러한 결과가 나오는데 재귀 호출을 넣었을때처럼 90이 마지막이 되어야 하는게 아닌가 해서 궁금해서 질문 드렸습니다. 결론적으로 제일 작은 수인 19만 맨위로 오고
오른쪽 자식이 90 -> 56, 90 -> 23 이렇게 되는건 딱히 상관 없는건가 해서요!

제로초(조현영)

지식공유자

아뇨 최소힙으로 바꾸는 것도 그냥 for문 안에서 minHeapify를 한번만 돌리면 됩니다. 재귀 필요없습니다. minHeapify 코드의 문제인 것 같네요

rhkdtjd_12

질문자

감사합니다.! 코드를 다시 한번 보겠습니당!

rhkdtjd_12

질문자

귀찮게 해드려서 죄송합니다. 또 질문하러 와버렸습니다 ㅠㅠ

class MaxHeap {
  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 bigger =
        this.arr[leftIndex] > this.arr[rightIndex] ? leftIndex : rightIndex;
      if (this.arr[index] < this.arr[bigger]) {
        const temp = this.arr[index];
        this.arr[index] = this.arr[bigger];
        this.arr[bigger] = temp;
        this.#reHeapDown(bigger);
      }
    }
  }

  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 (this.arr[i] === value) {
        return i;
      }
    }
    return null;
  }

  // 특정값 수정
  update(value, newValue) {
    const index = this.search(value);
    if (index === null) {
      return false;
    }
    this.arr[index] = newValue;
    for (let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i--) {
      this.#heapify(i);
    }
  }

  // 특정값 삭제
  removeValue(value) {
    const index = this.search(value);
    if (index === null) {
      return false;
    }

    // 특정값의 index를 splice를 이용하여 없애버린다.
    this.arr.splice(index, 1);

    for (let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i--) {
      // 이렇게 했을때 힙이 깨질 수 있기 떄문에 heapify 해준다
      this.#heapify(i);
    }
  }

  // 특정값을 수정하거나 특정값을 삭제하거나
  #heapify(index) {
    const leftIndex = index * 2 + 1; // 왼쪽 Index
    const rightIndex = index * 2 + 2;
    const bigger =
      (this.arr[leftIndex] || 0) > (this.arr[rightIndex] || 0)
        ? leftIndex
        : rightIndex;

    if (this.arr[index] < this.arr[bigger]) {
      const temp = this.arr[index];
      this.arr[index] = this.arr[bigger];
      this.arr[bigger] = temp;
    }
  }

}

const heap = new MaxHeap();
heap.insert(8);
heap.insert(19);
heap.insert(23);
heap.insert(32);
heap.insert(45);
heap.insert(56);
heap.insert(78);

heap.update(78, 1);

강의 코드 그대로 가져와서 update를 했는데 아래와 같은 결과가 나오는데

[ 78, 32, 56, 8, 23, 19, 45 ]

-> 결과 [ 56, 32, 1, 8, 23, 19, 45 ]

이것도 최대힙을 보장하지 않는거 아닌가 해서요.
제생각에는 결과가 [ 56, 32, 45, 8,23, 19, 1] 이렇게 되어야 되는게 아닌가 해서요.

제로초(조현영)

지식공유자

아 죄송합니다 이거 재귀하는 게 맞네요!

rhkdtjd_12

질문자

오!!!! 유레카 그렇군요. 감사합니다 😀

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

[숙제] minHeap 구현, maxHeap -> minHeap , minHeap -> maxHeap

minHeap 구현

최소 힙 insert

최소힙 remove

최소힙 update

최소힙 removeValue

최소힙 -> 최대힙

최대힙 -> 최소힙

질문1) maxheap(minheap) 코드 구현시 heapify 메서드에서 재귀호출 되어야 되지 않는가요?