cs-js-10-자료구조-힙(Heap)

SeungWoo Yoo ·2023년 2월 7일

DataAlgo

JS-자료구조-알고리즘

목록 보기

10/16

1. 우선순위 큐

FIFO인 큐와 달리 우선 순위가 높은 요소가 먼저 나가는 큐
우선순위 큐는 자료구조가 아닌 개념이다.
e.g. 줄서기 중에 VIP 고객은 먼저 입장

2. 힙(Heap)

힙은 우선순위 큐를 구현하기 위한 가장 적합한 자료구조입니다.
이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제될 때 바로 정렬되는 특징이 있다.
우선순위 큐 != 힙

Data Structure_10_1

1.1 힙의 특징

우선순위가 높은 요소가 먼저 나가는 특징을 가진다.
루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 루트가 가장 작은 값이 되는 최소 힙(Min Heap)이 있다.
즉, 빠른 시간 안에 최대값 또는 최소값을 찾아낼 수 있다.
주로 배열을 이용해 힙 구조를 구현할 수 있는데, 다른 언어의 경우 Heap 구조 자체를 라비르러리로 기본 제공한다.
아쉽게도 JavaScript에선 직접 구현해서 사용해야 한다.
물론 코딩테스트 영역 밖이라면 JS 역시 외부 라이브러리를 통해 heap을 사용할 수 있다.

1.2 Heap 요소 추가

요소가 추가될 떄는 트리의 가장 마지막에 정점에 위치한다. - push()
추가 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다. - swap()
이 과정을 반복하면 결국 가장 우선순위가 높은 정점이 루트가 된다. - heapifyUp()
완전 이진 트리의 높이는 $log\ N$ 이기에 힙의 요소 추가 알고리즘은 $O(log\ n)$ 시간복잡도를 가진다.

Data Structure_10_2

Data Structure_10_3

Data Structure_10_4

1.3 Heap 요소 제거

요소 제거는 루트 정점만 가능하다.
루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치한다.
루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꾼다.
두 자식 정점이 우선순위가 더 낮을 때까지 반복한다.
완전 이진 트리의 높이는 $log\ N$ 이기에 힙의 요소 제거 알고리즘은 $O(log\ n)$ 시간복잡도를 가진다.

Data Structure_10_5

Data Structure_10_6

2. 구현

그렇다면 배열을 이용해 어떻게 힙을 구현할 수 있을까? 알고리즘 문제에서 배열의 첫번째 값은 비워두는 경우가 종종 있다.
이는 배열의 첫번째 요소가 가지는 index는 0이기 때문에 '1번째' 라는 말과 인지부조화가 생기기에 계산의 편의성을 위해 그러한 경향을 띄는 편이다. 물론 이러한 부조화에 익숙하다면 굳이 처음을 비워둘 필요는 없지만, 해당 포스팅에서도 역시 계산의 편의성을 위해 첫 배열의 값은 비워두고 시작한다.

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

배열의 첫 원소는 사용하지 않으므로 부모와 자식 간 다음의 관계가 성립한다.
완전 이진 트리의 일종이기 때문에 Binaray Search tree에서의 부모-자식 간 관계와 유사하다.

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

2.1 힙 요소 추가

삽입 역시 비슷하다. 일단 마지막 노드에 들어온 값을 push하여 삽입한다.
이때 재귀적이든 반복문을 돌리든 부모노드를 확인하면서,
들어온 값이 부모노드보다 작은지 큰지를 구분하여 위치를 교환을 계속 실행해주며 정렬해준다.
최대힙으로 구현할 때의 삽입과정을 살펴보자.

최소힙이라면 반대의 계산결과로 적용해주면 된다!

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

const heap = new MaxHeap();
heap.push(45);
heap.push(36);
heap.push(54);
heap.push(27);
heap.push(63);
console.log(heap.heap); // [ null, 63, 54, 45, 27, 36 ]

2.2 힙 요소 제거

class MaxHeap {
  // ... 
  
  // 힙 요소 제거
  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 MaxHeap();
heap.push(45);
heap.push(36);
heap.push(54);
heap.push(27);
heap.push(63);
console.log(heap.heap); // [ null, 63, 54, 45, 27, 36 ]

const array = [];
array.push(heap.pop()); // 63
array.push(heap.pop()); // 54
array.push(heap.pop()); // 45
array.push(heap.pop()); // 36
array.push(heap.pop()); // 27
console.log(array); // [ 63, 54, 45, 36, 27 ]

3. 힙 실습 : 배상 비용 최소화❌

3.1 문제

https://school.programmers.co.kr/learn/courses/13213/lessons/91086

3.2 풀이

3.2.1 문제 유형 파악하기

문제 설명 중 핵심 부분은 역시 배상 비용을 계산하는 부분입니다.
배상 비용은 각 요소를 제곱하게 되므로 최대한 각 요소를 골고루 처리하는 것이 가장 배상 비용을 최소화할 수 있는 방법입니다.

그러기 위해서는 매 루프마다 가장 큰 작업을 찾아서 처리해야 합니다. 이때 가장 큰 작업을 찾기 위한 방법은 3가지가 있습니다.

매 루프마다 Math.max 함수를 호출한다.
매 루프마다 정렬한다.
Heap을 이용한다.

1번은 매 루프마다 O(n) 시간복잡도가 소요됩니다. 2번은 O(n log n)이 소요됩니다. 반면 Heap을 이용하면 O(log n)만이 소요됩니다.
사실 매번 큰 값 혹은 작은 값을 알아야 한다면 무조건 Heap을 사용하는 것이 좋습니다.
이제 문제 유형을 파악했으니 한 번 풀어보겠습니다.

3.2.2 최대 힙 구현

가장 큰 값을 알기 위해선 최대 힙을 구현해야 합니다.

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];
    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;
  }
}

3.2.3 solution 함수 구현

빠른 성능으로 통과됩니다.

function solution(no, works) {
  // 모든 작업의 합보다 no가 크면 배상 비용을 낼 필요가 없다.
  if (works.reduce((a, b) => a + b) <= no) {
    return 0;
  }

  // max heap 구성
  const heap = new MaxHeap();
  for (const work of works) {
    heap.push(work);
  }

  // no만큼 루프 돌면서 가장 큰 값을 빼서 처리 후 다시 push
  for (let i = 0; i < no; i += 1) {
    heap.push(heap.pop() - 1);
  }

  // 남은 요소에 제곱한 값들의 합을 구한 후 반환
  return heap.heap.reduce((a, b) => a + b * b);
}