최소힙의 결과값과 최대힙->최소힙 결과값이 다른게 맞나요?
248
33 asked
최소 힙 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 결과 값과 최대 힙 -> 최소 힙 결과 값은 서로 다른데 최소 힙의 조건은 아래가 크고, 위가 작다. 라고 하셨으니 결과 값은 달라도 최소 힙의 조건이 맞으니 최대 힙 -> 최소 힙 변환 코드가 맞는걸까요?
Answer 1
0
안녕하세요, 인프런 AI 인턴입니다.
최소 힙과 최대 힙은 각각 힙의 속성을 만족하는 다른 데이터 구조이기 때문에, 인서트 과정에서 원소들이 서로 다른 위치에 배치될 수 있습니다. 제공해주신 코드를 살펴보면, 최소 힙에 원소를 직접 삽입하는 경우와 최대 힙을 먼저 만들고 이를 최소 힙으로 변환하는 경우에 각각의 힙 속성이 유지됩니다.
최소 힙의 경우 작은 값이 상위 노드에 위치하고, 최대 힙에서는 큰 값이 상위 노드에 위치합니다. 각각의 insert 연산은 힙의 속성을 유지하도록 구현되어 있어 순서대로 원소를 삽입할 경우 힙이 올바른 구조를 이루게 됩니다. 하지만 원소를 삽입하는 순서나 방식이 달라질 경우 힙 내부의 원소 배치는 달라질 수 있습니다. 그러나 모든 경우에서 부모 노드가 자식 노드보다 작다는 최소 힙의 조건은 유지되어야 합니다.
질문하신 최대 힙 -> 최소 힙 변환 코드는 최대 힙에 있는 모든 원소들이 최소 힙의 조건을 만족하도록 재구성하는 과정으로, 변환 후에도 모든 부모 노드는 자식 노드보다 작아야 합니다. 따라서 변환 후 결과값이 처음에 최소 힙을 만들 때의 결과값과 다르더라도, 모든 노드가 최소 힙의 조건을 만족한다면 올바른 결과입니다.
최소 힙의 조건인 ‘아래가 크고, 위가 작다’는 속성이 변환된 최소 힙 결과값 [8, 23, 19, 32, 78, 56, 45]에도 잘 적용되고 있기 때문에, 질문자님께서 제공하신 최대 힙 -> 최소 힙 변환 코드는 맞는 것으로 보입니다.
2주차 개념#12 트리 순회
0
14
2
프론트엔드 학습 수준 문의
0
22
2
백준 사이트 서비스 종료
0
39
3
잠겨버린 사물함 시간초과 관련 질문입니다.
0
17
1
스택, 큐 연결리스트로 구현 과제 완료입니다!
0
93
1
heapify 안의 bigger 삼항연산자 질문
0
116
2
LinkedList로 스택, 큐 구현하기 숙제
0
123
1
linkedList prev와 tail 사용 후 o(1) 구현.
0
165
1
숙제 : LinkedList로 Stack, Queue 구현하기
0
177
1
연결리스트 숙제
0
239
1
한번에 이해 안가는 제가 비정상 일까요...?
0
234
1
우선순위 큐 질문이 있습니다!
0
154
1
[숙제] minHeap 구현, maxHeap -> minHeap , minHeap -> maxHeap
1
235
1
최소힙 remove 구현하기
0
245
1
숙제 최소힙 만들기
0
152
1
숙제 length return 하기
0
194
1
숙제 : 같은 값을 넣은경우 에러 처리
0
181
1
영상 중간에 0:10 1:23초 수정에 따른 코드 최종본
1
143
1
숙제2 연결리스트를 이용하여 큐 구현하기
0
237
1
숙제1 LinkedList로 스택 구현하기
1
251
1
연결 리스트 구현 숙제 리뷰 부탁드려봅니다
1
345
2
let current = this.head 질문 있습니다!
0
251
1
퀴즈 답안
0
469
1
1주차 숙제에 대한 해답 코드는 따로 제공되지 않나요??
0
495
1

