힙

해당 내용은 프로그래머스 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 공부하며 정리한 내용입니다.

1. 힙이란?
   이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징이 있다.
   • 우선순위 큐 : 우선 순위가 높은 요소가 먼저 나가는 큐
   • 주의 : 자료구조가 아닌 개념 고로, 우선순위 큐는 힙이 아니다.

=> 내 스스로 생각에 힙이 '조건에 맞게 node를 끼워넣는다' 라는 느낌으로 이해하고 있었는데 조금 틀렸다라는 생각이 들었다. 특히, 코딩테스트에서 힙은 'node에 끼워넣는다'는게 전혀 포인트가 아니라 요소의 삽입, 삭제에 따라 최대, 최소 값을 무대에 올리는 효율적인 자료구조 방식을 뿐이다. Math.max 함수와 효율적인 부분을 제외하고는 목적은 동일하다는 말.

2. 자료들 중에서 최대, 최소을 찾아내는 방법
   => 힙의 목적은 아래의 두가지랑 동일하다 근데 logn의 효율을 낼 수 있을 뿐.
   => 결국 최대, 최소의 것을 가장 루트에 놓고 그것을 pop()을 해주는 것.
   => 이 root 외의 정렬들은 뭉탱이 안에는 왼쪽 오른쪽으로 정렬이 되긴 하지만 큰 뭉텅이의 왼쪽과 오른쪽은 뭔가 특별한 관계를 갖지 않는다.
   - 매 루프마다 함수를 호출 O(n)
   - 매 루프마다 정렬 O(n log n)
   - Heap 이용 O(log n)
   => 이진 트리의 높이(레이어)가 log n 개이다.
   => 처음에 조금 오해했던 조건을 내 맘대로 넣을 수 있는건 아니다. 왜냐하면 이진 트리이기 때문에 트리로 분리가 되면서 각각 뭉탱이를 갖기 때문에 두번째 레이어의 다른 가지의 값과 다른 세번째 레이어의 값이 크기가 일정하지 않을 수 있다.

3. 코테

   • 핵심 키워드 : 매번 큰 값, 작은 값
   • 대표문제
     - 배상 비용 최소화 실습(강의 내 실습 문제)
     

class MaxHeap {
  constructor() {
    this.heap = [null];
  }

  push(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);

    while (parentIndex !== 0 && this.heap[parentIndex] < value) {
      const temp = this.heap[parentIndex];
      this.heap[parentIndex] = value;
      this.heap[currentIndex] = temp;

      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }

  pop() {
    if (this.heap.length ===2) return this.heap.pop();

    const returnValue = this.heap[1];
    // 여기에서 마지막 노드(최대가 아닌데도)를 정점으로 끌어 올리는 이유는
    // 자연스럽게 맨 위에 노드를 채워주고 주루룩 내려줘서 이진트리 구조를 유지시키려함에 있다.
    // => 좀더 설명하자면 비어버린 root에 어떤 값을 넣어야하는데 pop(시간복잡도 n)을 이용해 
    // => 값을 하나 채운셈
    this.heap[1] = this.heap.pop();
    
    // 맨 위에 노드가 일단 타겟이기에 인덱스를 특정할 수 있음
    let currentIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;
    while (this.heap[currentIndex] < this.heap[leftIndex] ||
          this.heap[currentIndex] < this.heap[rightIndex]) {
      if (this.heap[leftIndex] < this.heap[rightIndex]) {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;
        currentIndex = rightIndex;
      } else {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[leftIndex];
        this.heap[leftIndex] = temp;
        currentIndex = leftIndex;
      }
      leftIndex = currentIndex * 2;
      rightIndex = (currentIndex * 2) + 1;
    }

    return returnValue;
  }
}
class MinHeap {
  constructor() {
    this.heap = [null];
  }

  push(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);

    while (parentIndex !== 0 && this.heap[parentIndex] > value) {
      const temp = this.heap[parentIndex];
      this.heap[parentIndex] = value;
      this.heap[currentIndex] = temp;

      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }

  pop() {
    if (this.heap.length ===2) return this.heap.pop();

    const returnValue = this.heap[1];
    // 여기에서 마지막 노드(최대가 아닌데도)를 정점으로 끌어 올리는 이유는
    // 자연스럽게 맨 위에 노드를 채워주고 주루룩 내려줘서 이진트리 구조를 유지시키려함에 있다.
    this.heap[1] = this.heap.pop();
    
    let currentIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;
    while (this.heap[currentIndex] > this.heap[leftIndex] ||
          this.heap[currentIndex] > this.heap[rightIndex]) {
      if (this.heap[leftIndex] > this.heap[rightIndex]) {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;
        currentIndex = rightIndex;
      } else {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[leftIndex];
        this.heap[leftIndex] = temp;
        currentIndex = leftIndex;
      }
      leftIndex = currentIndex * 2;
      rightIndex = (currentIndex * 2) + 1;
    }

    return returnValue;
  }
}

const heap = new MinHeap();
heap.push(45);
heap.push(50);
heap.push(54);
console.log(heap.heap);
heap.pop();
heap.pop();
heap.pop();
heap.pop();
console.log(heap.heap);

출처 : https://school.programmers.co.kr/learn/courses/13213/13213-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EA%B4%91%ED%83%88-%EB%B0%A9%EC%A7%80-a-to-z-javascript