- 현재 상태에서 가장 좋은 것을 선택한다.
- 정렬 된 상태에서 많이 사용한다.
ex) 동전 잔돈 문제 - 1600원을 거슬러줘야 할 때 , 잔돈의 종류가 [1000,500,100,50]이 있다면 50원 여러개 주기보다는 1000원 1장,500원 1개, 100원 1개로 돌려준다.
(단, 잔돈 문제는 큰 금액이 작은 금액의 배수여야 한다. 배수가 아니라면, Knapsack, DP로 풀이해야 한다.)
그래프 구조지만, 배열로 사용한다.
parent 노드에 있는게 가장 큰 수이다.
- left child = 부모노드 * 2
- right child = 부모노드 * 2 + 1
- 부모 : 자식노드 / 2 (js에서는 소숫점으로 나오기 떄문에
parseInt
처리 필요)
( 배열의 [0] 은 1e9 로, 그냥 아무 큰 수를 넣어준다.)
예를 들어
maxHeap.insert(3)
을 해준다면 배열의 마지막 자리에 들어가게 된다 . 만약, parents 보다 현재 insert한 값이 크다면 올라가주어야 한다.
max 값을 꺼내게 되면 마지막에 있는 요소를
pop
해서 루트 노드에 가져다 놓는다. 그리고 부모 노드보다 작을 때까지 반복해서 내려간다.
class maxHeap {
constructor() {
this.heap = [];
this.heap[0] = Number.MAX_SAFE_INTEGER;
}
// <---1. 데이터삽입 함수 --->
insert(value) {
this.heap.push(value);
this.upHeap(this.heap.length - 1);
}
upHeap(pos) {
// pos는 insert된 위치이다.(heap)
let tmp = this.heap[pos];
while (tmp > this.heap[parseInt(pos / 2)]) {
// tmp(입력된 값)이 올라갈 수 있을만큼(parents) 올라간다.
this.heap[pos] = this.heap[parseInt(pos / 2)];
pos = parseInt(pos / 2);
}
this.heap[pos] = tmp;
// 마지막으로 멈춘 곳에 tmp값 삽입
}
// <---1. 데이터제거 함수 --->
get() {
// 1) 노드가 한 개 남았을 때
if (this.heap.length === 2) return this.heap.pop();
// 2) 노드가 한 개 이상 남았을 때
else {
let res = this.heap[1];
this.heap[1] = this.heap.pop();
this.downHeap(1, this.heap.length - 1);
return res;
}
}
downHeap(pos, len){
let tmp=this.heap[pos];
while(tmp<=this.heap[parseInt(pos*2)]){
let child=pos*2;
if(child<len && this.heap[child] < this.heap[child+1]) child++;
if(tmp>=this.heap[child]) break;
this.heap[pos]=this.heap[child];
pos=child;
}
this.heap[pos]=tmp;
}
}
//<---데이터값 확인---->
let max = new maxHeap();
max.insert(3);
max.insert(10);
max.insert(1);
max.insert(11);
max.get();
console.log(max);