[자료구조|알고리즘 개념] Greedy 알고리즘 (최대힙, 최소힙)

👨‍🌾 그리디(Greedy)

• 현재 상태에서 가장 좋은 것을 선택한다.
• 정렬 된 상태에서 많이 사용한다.

ex) 동전 잔돈 문제 - 1600원을 거슬러줘야 할 때 , 잔돈의 종류가 [1000,500,100,50]이 있다면 50원 여러개 주기보다는 1000원 1장,500원 1개, 100원 1개로 돌려준다.

(단, 잔돈 문제는 큰 금액이 작은 금액의 배수여야 한다. 배수가 아니라면, Knapsack, DP로 풀이해야 한다.)

• Greedy의 정렬
  - Greedy 에서 정렬은 가장 중요하다. 앞에서부터 정렬할 것인지, 뒤에서부터 정렬할 것인지 결정해야한다. (결정하는 방법 : 증명하기 어려우니 반례를 생각할 것)
  

🗣 최대힙(Max Heap)

그래프 구조지만, 배열로 사용한다.

parent 노드에 있는게 가장 큰 수이다.

• left child = 부모노드 * 2
• right child = 부모노드 * 2 + 1
• 부모 : 자식노드 / 2 (js에서는 소숫점으로 나오기 떄문에 parseInt 처리 필요)
  
  ( 배열의 [0] 은 1e9 로, 그냥 아무 큰 수를 넣어준다.)

1) UPHEAP

• Heap에 새로운 값이 추가되었을 때

예를 들어
maxHeap.insert(3) 을 해준다면 배열의 마지막 자리에 들어가게 된다 . 만약, parents 보다 현재 insert한 값이 크다면 올라가주어야 한다.

2) DOWNHEAP

• max(root값)이 삭제될 때

max 값을 꺼내게 되면 마지막에 있는 요소를 pop 해서 루트 노드에 가져다 놓는다. 그리고 부모 노드보다 작을 때까지 반복해서 내려간다.

3) MaxHeap 구현 - JavaScript

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