Inflearn コミュニティ Q&A

rhkdtjd124829

投稿した質問数

非専攻者の専攻者追いつく - 資料構造(with JavaScript)

heapify

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

解決済みの質問

作成

223

編集済み

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

zerocho

インストラクター

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

rhkdtjd124829

質問者

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

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

rhkdtjd124829

質問者

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

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 이렇게 되는건 딱히 상관 없는건가 해서요!

zerocho

インストラクター

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

rhkdtjd124829

質問者

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

rhkdtjd124829

質問者

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

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] 이렇게 되어야 되는게 아닌가 해서요.

zerocho

インストラクター

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

rhkdtjd124829

質問者

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

rhkdtjd124829

投稿した質問数

質問する