[프로그래머스] Lv.2 더 맵게

최소힙을 구현해서 풀어야 하는 문제 !!

function solution(scoville, K) {

let answer = 0;
class Heap {
  //배열로써 힙을 구현함
  constructor() {
    this.items = [];
  }
  
  //값을 서로 바꾸는 함수
  swap(index1,index2) {
    [this.items[index1], this.items[index2]] = 
      [this.items[index2], this.items[index1]];
  }
       
  parentIndex(index) {
    return Math.floor((index-1)/2);
  }
    
  leftChildIndex(index){
    return index * 2 + 1;
  }
    
  rightChildIndex(index){
    return index * 2 + 2;
  }
  
    //부모 노드 구하는 메소드
    parent(index){
        return this.items[this.parentIndex(index)];
    }

    //왼쪽 자식 노드 구하는 메소드
    leftChild(index){
        return this.items[this.leftChildIndex(index)];
    }

    //오른쪽 자식 노드 구하는 메소드
    rightChild(index){
        return this.items[this.rightChildIndex(index)];
    }
    
    peek(){
    return this.items[0];
     }
  
  size(){
    return this.items.length;
  }
}

  //최소힙 구현하기
class MinHeap extends Heap{
  //맨 마지막자리에 새로 들어온 원소로 인해 오름차순 정렬을 시작
  bubbleUp(){
    let index = this.items.length - 1;
    //부모가 더 작아야 하는데 큰 경우에 정렬함
    while(this.parent(index) !== undefined && this.items[index] < this.parent(index)){
      //부모와 자리바꿈
      this.swap(index,this.parentIndex(index));
      index = this.parentIndex(index);
    }
  }
  
  //원소를 뺀 이후에 오름차순으로 정렬하는 방법
  bubbleDown(){
    let index = 0;
    //부모가 가장 작아야 하는데 자식들이 더 작을 경우에 정렬을 시작함
    while(this.leftChild(index) !== undefined && this.leftChild(index) < this.items[index] || this.rightChild(index) < this.items[index]){
      let smallIndex = this.leftChildIndex(index);
      //만약 오른쪽 자식이 왼쪽 보다 작으면 바꿔줌
      if(this.rightChild(index) !== undefined 
         && this.rightChild(index) < this.items[smallIndex]){
        smallIndex = this.rightChildIndex(index);
      }
      this.swap(index,smallIndex);
      index = smallIndex;
 
    }
    
  }
  
  //힙에 원소를 추가하는 함수
  add(item){
    this.items[this.items.length] = item;
    this.bubbleUp();
  }
  
  //힙에서 원소를 빼는 함수, 최소힙이라면 최솟값이 나오게 됨
  poll(){
    let item = this.items[0];
    this.items[0] = this.items[this.items.length - 1];
    this.items.pop();
    this.bubbleDown();
    
    return item;
  }
}
  
const minHeap = new MinHeap();

scoville.forEach((item) => {
  minHeap.add(item);
})

while(minHeap.size() >= 2 && minHeap.peek() < K){
  let first = minHeap.poll();
  let second = minHeap.poll();
  minHeap.add(first + (second * 2));
  answer++;
}

return(minHeap.peek() >= K ? answer : -1)
}

++ 공부하는 차원으로 최대힙 구현해보기

//위에서 구현한 Heap 클래스를 상속받은 최대힙
class MaxHeap extends Heap{
  
  bubbleUp(){
    let index = this.items.length - 1;
    while(this.parent(index) !== undefined && this.parent(index) < this.items[index]){
      this.swap(index , this.parentIndex(index));
      index = this.parentIndex(index);
    }
  }

  bubbleDown(){
    let index = 0; //루트부터 비교하니까
    //부모가 자식들보다 작은 경우에는 스왑을 하세요
    while(this.leftChild(index) !== undefined && this.leftChild(index) > this.items[index] || this.rightChild(index) > this.items[index]){
      let biggerIndex = this.leftChildIndex(index);
      if(this.rightChild(index) > this.leftChild(index)){
        biggerIndex = this.rightChildIndex(index);
      }
      this.swap(index,biggerIndex);
      index = biggerIndex;
    }
  }
  
  add(item){
    this.items[this.items.length] = item;
    this.bubbleUp()
  }
  
  poll(){
    let item = this.items[0]; //맨 첫번째가 나감
    this.items[0] = this.items[this.items.length - 1];// 맨 밑 아이템을 루트로 올림
    this.items.pop();
    this.bubbleDown();
    
    return item;
  }
  
}

let maxHeap = new MaxHeap();

maxHeap.add(1);
maxHeap.add(10);
maxHeap.add(5);
maxHeap.add(100);
maxHeap.add(8);

console.log(maxHeap) // {"items": [100,10,5,1,8]}
console.log(maxHeap.poll()) // 100
console.log(maxHeap.poll()) // 10