프로그래머스에서 힙 문제를 풀다가 헷갈려 정리차원에서 이 글을 작성하게 되었다.

Heap

힙은 일종의 완전 이진 트리이다.
주로 우선순위 큐를 구현하는데 밑받침이 되는 자료구조로 쓰인다.
트리 구조이기 때문에 삽입과 삭제에 O(logN)의 시간이 소요된다.

최소 힙, 최대 힙
빠른 시간 안에 최대값과 최소값을 찾아낼 수 있다.

파이선 -> heapq heapify 등 라이브러리에서 함수와 구조를 제공

힙에서의 부모-자식 관계

힙은 완전 이진 트리 base 이기 때문에, 노드들 간의 부모-자식 관계가 성립하게 된다. 힙의 경우엔 보통의 완전 이진 트리와는 다르게 반정렬 상태(느슨한 정렬 상태)를 유지한다. 최대힙이라면 큰 값이 부모 노드쪽에, 최소힙이라면 작은 값이 부모 노드 쪽에 배치되는 것만 유지하고 왼쪽 자식과 오른쪽 자식은 부모 노드보다 작은 값을 유지하기만 하면 된다.

구현 - Max Heap

// 기본 세팅
class Heap {
  constructor() {
    this.heap = [null]; // 첫 원소는 사용 X
  }
}

배열의 첫 원소는 사용하지 않으므로 부모와 자식 간 다음의 관계가 성립한다.

완전 이진 트리의 일종이기 때문에 Binary Search tree에서의 부모-자식 간 관계와 유사하다.

• 왼쪽 자식의 index = 부모 index * 2;
• 오른쪽 자식의 index = (부모 index * 2) + 1;
• 부모의 index = Math.floor(자식의 인덱스 / 2);

getParentIndex(i){
    return Math.floor(i / 2);
}

getLeftChildIndex(i){
    return i * 2;
}

getRightChildIndex(i){
    return i * 2 + 1;
}

삽입

마지막 노드에 들어온 값을 push()하여 배열의 맨 마지막에 삽입한다. 이 때 부모노드를 확인하면서 들어온 값이 부모노드보다 작은지 큰지를 확인하면서 위치를 교환 swap()해주며 정렬 heapifyUp()한다.

swap(idx1, idx2){
    const temp = this.heap[idx1];
    this.heap[idx1] = this.heap[idx2];
    this.heap[idx2] = temp;
}

push(value){
    this.heap[this.heap.length] = value; // 배열의 맨 마지막에 값 넣기
    this.heapifyUp();
}

// 최대 힙에 맞게 제일 큰 노드를 최상단으로 맞춰주기 위해 가장 마지막에 들어온 노드의 인덱스를 변수로 둔다.
heapifyUp(){
    let curIndex = this.heap.length - 1;
    // 확인 중의 인덱스의 값이 부모 인덱스의 값보다 크면, swap하고, 현재 인덱스에 부모 인덱스를 재할당하여 while문에서 부모 인덱스를 확인
    while(this.heap[curIndex] > this.heap[this.getParentIndex(curIndex)]){
        this.swap(curIndex, this.getParentIndex(curIndex));
        curIndex = this.getParentIndex(curIndex);
    }
}

삭제/추출

힙에서 루트 노드가 가장 먼저 추출된다. 그 빈 자리는 트리의 맨 마지막에 있는 값을 가져와 채우고, 맨 마지막 노드를 삭제한다. 그리고 다시 트리를 정렬한다. 힙의 원칙에 맞게 정렬이 다 끝나면 처음에 추출했던 루트노드값을 리턴한다.

1. maxVal: 배열의 최상위 노드를 꺼낸다.
2. 루트 노드와 맨 끝에 있는 값을 교체한다.
3. 맨 마지막 노드를 삭제한다.
4. 변경된 노드와 자식 노드들을 비교하면서 정렬한다.
5. 자식 노드 둘보다 부모 노드가 크거나 가장 마지막 바닥까지 도달하지 않을 때까지 과정을 반복한다.
6. 2에서 제거한 루트 노드 값을 return 한다.

poll(){
    let maxVal = this.heap[1];
    this.heap[1] = this.heap[this.heap.length - 1];
    this.heap.length--;

    this.heapifyDown();

    return maxVal;
}

// 최소 힙에 맞게 제일 작은  노드를 최상단으로 맞춰주기 위해 가장 마지막에 들어온 노드의 인덱스를 변수로 둔다.
heapifyDown(){
    let curIndex = 1;
    // curIndex가 마지막 노드가 아닐 때까지 반복
    while(this.heap[this.getLeftChildIndex(curIndex)] !== undefined){
        let biggerChildIndex = this.getLeftChildIndex(curIndex);

        if(this.heap[this.getRightChildIndex(curIndex)] !== undefined && this.heap[this.getRightChildIndex(curIndex)] > this.heap[this.getLeftChildIndex(curIndex)]
        ){
            biggerChildIndex = this.getRightChildIndex(curIndex);
        }
        // 자식 노드가 있다면 자식 노드 중에서 제일 큰 자식 노드의 값과 현재 노드의 값을 비교
        // 자식 노드 값이 더 크다면 swap하는 식으로 전체 트리를 heap의 구조에 맞게 정렬
        if(this.heap[curIndex] < this.heap[biggerChildIndex]){
            this.swap(curIndex, biggerChildIndex);
            curIndex = biggerChildIndex;
        } else {
            return;
        }

    }
}

전체 코드

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

  getParentIndex(i) {
    return Math.floor(i / 2);
  }

  getLeftChildIndex(i) {
    return i * 2;
  }

  getRightChildIndex(i) {
    return i * 2 + 1;
  }

  swap(idx1, idx2) {
    const temp = this.heap[idx1];
    this.heap[idx1] = this.heap[idx2];
    this.heap[idx2] = temp;
  }

  push(val) {
    this.heap[this.heap.length] = val;
    this.heapifyUp();
  }

  heapifyUp() {
    let curIdx = this.heap.length - 1;
    // min Heap 은 반대로 될 것
    while (this.heap[curIdx] > this.heap[this.getParentIndex(curIdx)]) {
      this.swap(curIdx, this.getParentIndex(curIdx));
      curIdx = this.getParentIndex(curIdx);
    }
  }

  poll() {
    // min Heap 은 반대로 될 것
    let maxVal = this.heap[0];
    if (maxVal === 12 || maxVal === 10 || maxVal === 8) {
      console.log("g", this.heap);
    }
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.length--;
    this.heapifyDown();
    return maxVal;
  }

  heapifyDown() {
    let curIdx = 0;
    while (this.heap[this.getLeftChildIndex(curIdx)] !== undefined) {
      let biggerChild = this.getLeftChildIndex(curIdx);
      if (
        this.heap[this.getLeftChildIndex(curIdx)] <
        this.heap[this.getRightChildIndex(curIdx)]
      ) {
        biggerChild = this.getRightChildIndex(curIdx);
      }
      if (this.heap[curIdx] < this.heap[biggerChild]) {
        this.swap(curIdx, biggerChild);
        curIdx = biggerChild;
      } else {
        return;
      }
    }
  }
}

힙 사용 예제

• 우선순위 큐를 구현하는데 사용한다.
• 게임엔진에서 각 액터의 우선순위를 정한다.
• 서버에서 많은 트래픽을 처리할 때 우선 처리해야 할 트래픽을 정한다.
• 시뮬레이션 시스템
• 네트워크 트래픽 제어
• 운영 체제에서의 작업 스케쥴링 (우선 순위가 높은 일을 바로 조회)
• 수치 해석적인 계산

관련 문제

프로그래머스 - 더 맵게

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

scoville의 길이는 2 이상 1,000,000 이하입니다.
K는 0 이상 1,000,000,000 이하입니다.
scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

문제풀이

MinHeap을 직접 구현하여야 풀이할 수 있는 문제이다.
최소힙은 오른쪽 왼쪽 상관없이 부모노드가 자식노드보다 크기만 하면 된다. (처음에 오른쪽이 왼쪽보다 커야하는 줄 알고 헷갈렸음 )

먼저, 전체 입력값을 Heap에 push해준다. heap에 push할 때에는 값을 배열의 맨 마지막 부분에 넣어주고, 마지막 index의 값을 기준으로 부모 노드와 비교하면서 부모노드보다 더 큰 상황이 올 때까지 부모와 자식을 swap하면서 올라간다. 부모 노드가 현재 비교대상인 자식노드보다 더 크다면 값을 swap하고 비교대상을 그 부모노드의 index로 변경한다. 그렇지 않다면 멈춘다.

Heap의 첫 번째로 작은 값과 두번째로 작은 값 * 2를 구하기 위해, heap에서 pop을 두 번하여, 제일 작은 값과 두번째 작은 값을 구한다. (매 pop마다 minHeap은 정렬된다.) 그 다음 그 값들의 합을 Push하고, heap을 재정렬한다. 이런식으로 반복하다가 heap의 길이가 1, 즉 제일 작은 값만 있고, 두 번째 값이 없는 경우가 되거나, heap의 [0]값이 K보다 커지면 위 동작을 멈춘다. 위 두 경우에서, heap[0]이 K보다 크다면 answer을, 그렇지 않다면 조건을 충족시키지 못한 경우이므로 -1을 리턴한다. (missing point)

위 과정에서 heap에서 pop하는 동작이 있는데, 여기가 아주 골머리~~~

일단 힙에서는 최소힙이든 최대힙이든 루트 노드가 항상 먼저 배출되어야 한다. 배출되고 나서 생기는 빈자리는 가장 마지막 노드, 즉 배열에서 제일 뒤에 있는 값을 가져온다. 그리고 다시 루트노드서 부터 재정렬을 실행해준다.

1. 만약 heap에 어떤 값도 없다면 null을 리턴한다.
2. 만약 Heap의 길이가 1인 경우, 즉, 루트 노드 밖에 없는 경우라면, heap[0]을 pop하여 리턴한다.
3. 1, 2번의 경우 외로 자식 노드들이 있는 경우, 루트 노드를 메서드가 끝날 때 return하기 위해 따로 저장한다.
4. 루트 노드와 맨 마지막 노드를 교환하고, 맨 마지막 노드는 필요가 없어졌기 때문에 heap에서 pop() (배열에서의 pop을 의미)을 한다.
5. 새롭게 바뀐 루트 노드를 자식 노드들과 비교하여 재정렬한다.
6. 3번에서 저장했던 루트 노드를 리턴한다.

재정렬

1. 루트 노드를 자식 노드들과 비교하여 정렬할 것이기 때문에 3가지 정보가 필요하다.

• 현재 노드의 위치 : 0
• 왼쪽 자식 노드의 위치
• 오른쪽 자식 노드의 위치

2. 아래 진행될 정렬을 왼쪽 자식 노드와 오른쪽 자식 노드보다 작을 때까지 계속 반복할 것이다.
3. 주의할 점1. 왼쪽 자식 노드만 있고, 오른쪽 자식 노드는 없는 경우가 있음!
4. 주의할 점2. 왼쪽 자식 노드도 있고, 오른쪽 자식 노드도 있는 경우, 더 작은 자식 노드와 위치를 바꾸어야 한다.
5. 왼쪽 혹은 오른쪽 자식 노드와 위치를 바꾼 경우, current idx를 바꾼 자식 노드의 idx로 변경하고, 해당 위치로부터 다시 정렬한다.

class Heap {
  constructor() {
    this.heap = [];
  }
  // 부모 idx = Math.floor(자식 idx / 2)
  getParentIdx(idx) {
    return Math.floor((idx - 1) / 2);
  }
  // 왼쪽 자식 idx = 부모 idx * 2
  getLeftChildIdx(idx) {
    return idx * 2 + 1;
  }
  // 오른쪽 자식 idx = 부모 idx * 2 + 1
  getRightChildIdx(idx) {
    return idx * 2 + 2;
  }
  swap(idx1, idx2) {
    [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
  }
  push(value) {
    // 일단 마지막 노드에 들어온 값을 push하여 삽입한다. 이때 재귀적이든 반복문을 돌리든 부모노드를 확인하면서 들어온 값이 부모노드보다 작은지 큰지를 구분하여 위치를 교환을 계속 실행해주며 정렬해준다.
    this.heap.push(value);
    let current = this.heap.length - 1; // push 했기 때문에 heap 배열의 맨 뒤에 붙음
    let parent = this.getParentIdx(current);

    while (this.heap[parent] > this.heap[current]) {
      this.swap(parent, current);
      current = parent;
      parent = this.getParentIdx(current);
    }
    return this.heap;
  }
  pop() {
    // heap에 아무것도 없는 경우,
    if (this.heap.length === 0) {
      return null;
    }
    // root만 있는 경우 ,
    if (this.heap.length === 1) {
      return this.heap.pop();
    }
    const min = this.heap[0]; // min에 0번째 값 저장
    this.heap[0] = this.heap.pop(); //  마지막 값이랑 0번째 값이랑 교체

    // 정렬
    let current = 0;
    let leftChild = this.getLeftChildIdx(current);
    let rightChild = this.getRightChildIdx(current);

    while (
      (this.heap[leftChild] && this.heap[leftChild] < this.heap[current]) ||
      (this.heap[rightChild] && this.heap[rightChild] < this.heap[current])
    ) {
      // 오른쪽 왼쪽 다 있고, 왼쪽이 더 큰 경우, -> 오른쪽과 변경
      if (
        this.heap[rightChild] &&
        this.heap[rightChild] < this.heap[leftChild]
      ) {
        this.swap(rightChild, current);
        current = rightChild;
      } else {
        this.swap(leftChild, current);
        current = leftChild;
      }

      leftChild = this.getLeftChildIdx(current);
      rightChild = this.getRightChildIdx(current);
    }
    return min;
  }
}

function solution(input, K) {
  var answer = 0;
  const heap = new Heap();
  for (const item of input) {
    heap.push(item);
  }
  while (heap.heap[0] < K && heap.heap.length > 1) {
    // heap의 root가 k보다 작고, heap에 1개 이상의 데이터가 있다면 계속 할 것
    const first = heap.pop(); // 제일 작은 값과
    const second = heap.pop(); // 두번째로 작은 값을 빼내고,
    heap.push(first + second * 2); // 새로 만든 값을 push
    answer++;
  }
  // 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다. - `놓친 부분``
  if (heap.heap[0] >= K) {
    return answer;
  } else {
    return -1;
  }
}