inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

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

insert 구현하기

숙제 최소힙 만들기

153

rhkdtjd_12

작성한 질문수 138

0

class Heap {
  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);
      }
    }
  }

  #reheapDown(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.#reheapDown(parentIndex);
      }
    }
  }

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

  insertDown(value) {
    const index = this.arr.length;
    this.arr[index] = value;
    this.#reheapDown(index);
  }

  remove() {
    // root만 remove
  }

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

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

const downHeap = new Heap();
downHeap.insertDown(78);
downHeap.insertDown(56);
downHeap.insertDown(45);
downHeap.insertDown(32);
downHeap.insertDown(23);
downHeap.insertDown(19);
downHeap.insertDown(8);
console.log(downHeap.arr);

reheapDown 이라는걸 만들어서 최소힙 만들기를 해보았는데 부모 index의 값과 비교하는 조건문의 부등호 방향만 바꾸니까 되는데 이게 맞나요...?

 

javascript 코딩-테스트 알고리즘

답변 1

1

제로초(조현영)

네네 원래 간단합니다

0

rhkdtjd_12

와우!! 칼답변 감사드립니당 😄

섹션2퀴즈는어디있나요?

0

7

0

연결리스트 삽입삭제 O(1) 아닌가요?

0

10

2

GROUP BY, HAVING 실습 1번문제

1

14

2

4 - A

0

21

2

스택, 큐 연결리스트로 구현 과제 완료입니다!

0

95

1

heapify 안의 bigger 삼항연산자 질문

0

121

2

LinkedList로 스택, 큐 구현하기 숙제

0

126

1

linkedList prev와 tail 사용 후 o(1) 구현.

0

165

1

숙제 : LinkedList로 Stack, Queue 구현하기

0

178

1

연결리스트 숙제

0

242

1

한번에 이해 안가는 제가 비정상 일까요...?

0

237

1

우선순위 큐 질문이 있습니다!

0

155

1

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

1

236

1

최소힙 remove 구현하기

0

247

1

숙제 length return 하기

0

195

1

숙제 : 같은 값을 넣은경우 에러 처리

0

184

1

영상 중간에 0:10 1:23초 수정에 따른 코드 최종본

1

145

1

숙제2 연결리스트를 이용하여 큐 구현하기

0

241

1

숙제1 LinkedList로 스택 구현하기

1

253

1

연결 리스트 구현 숙제 리뷰 부탁드려봅니다

1

346

2

let current = this.head 질문 있습니다!

0

254

1

퀴즈 답안

0

471

1

최소힙의 결과값과 최대힙->최소힙 결과값이 다른게 맞나요?

0

249

1

1주차 숙제에 대한 해답 코드는 따로 제공되지 않나요??

0

499

1