힙(Heap)

0. 요약

최소 힙 구현하기

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

  // 힙에 요소 추가하기
  push(value) {
    this.heap.push(value);
    let cur_index = this.heap.length - 1;
    let parents_index = Math.floor(cur_index / 2);

    while (cur_index !== 1 && this.heap[parents_index] > value) {
      [this.heap[parents_index], this.heap[cur_index]] = [
        this.heap[cur_index],
        this.heap[parents_index],
      ];
      cur_index = parents_index;
      parents_index = Math.floor(cur_index / 2);
    }
  }

  // 힙에 요소 제거하기
  pop() {
    const value = this.heap[1];

    if (this.heap.length <= 2) this.heap = [null];
    else this.heap[1] = this.heap.pop();

    let cur_index = 1;
    let left_index = cur_index * 2;
    let right_index = cur_index * 2 + 1;

    if (!this.heap[left_index]) return value;
    if (!this.heap[right_index]) {
      if (this.heap[left_index] < this.heap[cur_index]) {
        [this.heap[left_index], this.heap[cur_index]] = [
          this.heap[cur_index],
          this.heap[left_index],
        ];
      }
      return value;
    }

    while (
      this.heap[left_index] < this.heap[cur_index] ||
      this.heap[right_index] < this.heap[cur_index]
    ) {
      let min_index =
        this.heap[left_index] > this.heap[right_index]
          ? right_index
          : left_index;

      [this.heap[min_index], this.heap[cur_index]] = [
        this.heap[cur_index],
        this.heap[min_index],
      ];

      cur_index = min_index;
      left_index = cur_index * 2;
      right_index = cur_index * 2 + 1;
    }
    return value;
  }
}

1. 개요

완전 이진 트리의 일종인 힙에 대해 정리한다.

참고할 만한 코딩 테스트 문제

이중우선순위큐

2. 우선순위 큐란?

힙에 대해 살펴보기 전 우선순위 큐에 대해 먼저 살펴보자. 우선순위 큐을 먼저 살펴보는 이유는 힙이 우선순위 큐를 구현하기 위해 고안된 완전 이진 트리 형태의 자료구조이기 때문이다.

큐(Queue): 먼저 들어오는 데이터가 먼저 나가는 FIFO 형식의 자료구조
우선순위 큐(Priority Queue): 먼저 들어온 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나감

주의 해야할 점은 우선순위 큐는 자료구조가 아닌 개념이라는 것이다. 또한 우선순위 큐가 힙이라는 것도 아니다. 즉, 우선순위 큐라는 개념을 적용하기 위해 힙 자료구조를 사용한다는 것으로 이해하도록 하자.

우선순위 큐는 배열, 연결 리스트, 힙으로 구현이 가능하다. 이 중 힙으로 구현하는 것이 가장 효율적이다.

우선순위 큐의 사용 사례는 아래와 같다.

시물레이션 시스템
네트워크 트래픽 제어
운영 체제에서의 작업 스케쥴링

3. 힙이란?

완전 이진 트리의 일종
여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조
일종의 반정렬 상태(느슨한 정렬 상태)를 유지
- 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
중복된 값을 허용(이진 탐색 트리에서는 중복된 값을 허용하지 않음)

4. 힙의 종류

최대 힙(max heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
최소 힙(min heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

5. 힙 구현하기

힙을 구현 하기 전 몇 가지 사항을 짚고 넘어가자.

힙을 저장하는 표준적인 자료구조로 배열을 이용한다.
구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
부모 노드와 자식 노드의 관계
- 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
- 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
- 부모의 인덱스 = Math.floor(자식의 인덱스 / 2)
  부모 노드와 자식 노드의 관계

위의 내용을 바탕으로 최소 힙을 구현한다.

5-1. 힙의 기본 구조

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

this.heap을 배열로 이용하여 선언을 하고 첫 번째 요소는 null로 저장한다.

5-2. 힙에 요소 추가하기

class Heap {
  // ...
  push(value) {
    this.heap.push(value);
    let cur_index = this.heap.length - 1;
    let parents_index = Math.floor(cur_index / 2);

    while (cur_index !== 1 && this.heap[parents_index] > value) {
      [this.heap[parents_index], this.heap[cur_index]] = [
        this.heap[cur_index],
        this.heap[parents_index],
      ];
      cur_index = parents_index;
      parents_index = Math.floor(cur_index / 2);
    }
  }
}

최소 힙은 부모 노드가 제일 작아야 한다. 현재 노드와 부모 노드의 값을 비교하여 부모 노드의 값이 크다면 그 둘을 서로 바꾸어 준다.

만약 현재 노드의 인덱스가 1이거나 현재 노드가 부모 노드 보다 값이 작다면 반복문 더 이상 실행되지 않는다.

5-3. 힙에 요소 제거하기

class Heap {
  // ...
  pop() {
    // 1.
    const value = this.heap[1];

    // 2.
    if (this.heap.length <= 2) this.heap = [null];
    else this.heap[1] = this.heap.pop();

    let cur_index = 1;
    let left_index = cur_index * 2;
    let right_index = cur_index * 2 + 1;

    // 3. 루트만 있는 상황
    if (!this.heap[left_index]) return value;
    // 4. 왼쪽 자식 하나만 있는 상황
    if (!this.heap[right_index]) {
      if (this.heap[left_index] < this.heap[cur_index]) {
        [this.heap[left_index], this.heap[cur_index]] = [
          this.heap[cur_index],
          this.heap[left_index],
        ];
      }
      return value;
    }

    // 5. 왼쪽 자식과 오른쪽 자식이 모두 있는 경우
    while (
      // 6.
      this.heap[left_index] < this.heap[cur_index] ||
      this.heap[right_index] < this.heap[cur_index]
    ) {
      // 7.
      let min_index =
        this.heap[left_index] > this.heap[right_index]
          ? right_index
          : left_index;
      // 8.
      [this.heap[min_index], this.heap[cur_index]] = [
        this.heap[cur_index],
        this.heap[min_index],
      ];
      // 9.
      cur_index = min_index;
      left_index = cur_index * 2;
      right_index = cur_index * 2 + 1;
    }
    return value;
  }
}

가장 작은 요소는 항상 this.heap[1]에 위치한다. 이를 value에 할당한다.
가정 먼저해야 할 과정은 배열의 this.heap의 마지막 요소를 root위치에 배치하는 것이다.
루트만 있는 상황
- 요소의 이동 없이 바로 value를 반환한다.
왼쪽 자식 하나만 있는 상황
- 왼쪽 자식의 값과 현재 인덱스의 값을 비교하여 왼쪽 자식의 값이 더 작으면 두 개의 값을 서로 바꾼다.
왼쪽 자식과 오른쪽 자식이 모두 있는 경우
- 아래의 반복문을 실행한다.
왼쪽 자식과 오른쪽 자식의 값 중 하나라도 현재 인덱스의 값 보다 작으면 반복문을 계속 실행된다. 즉, 부모의 값이 자식들의 값 보다 작아져야 반복문은 종료된다.
왼쪽 자식과 오른쪽 자식의 값을 비교하여 더 작은 값을 가지는 인덱스를 min_index에 할당한다. 이때 오른쪽 자식의 값이 없다면 비교 값은 항상 false가 되므로 이점을 유의해야 한다.
부모의 값과 자식의 값(더 작은)을 비교하여 부모의 값 보다 자식의 값이 더 작으면 두 개의 값을 서로 바꾼다.
다음 비교를 위해 각각의 값들을 바꾼다.

6. Conclusion

이번 힙의 요소를 제거하는 과정을 정리하면서 해당 알고리즘을 사용해 트리의 요소를 삭제하는 것도 가능하지 않을까라는 생각을 하였다. 지금까지 봤던 자료구조 중 가장 메서드가 길었던 것 같다. 특히 요소의 삭제가 길었는데 신기한 것은 배열, 연결 리스트를 사용하여 우선 순위 큐를 구현하는 것보다 힙으로 구현하는 것이 시간 복잡도 측면에서 효율적인 면을 보인다는 것이다. 코드의 양은 중요하지 않고 얼마나 효율적으로 요소를 추가, 삭제하는 데에 있다는 것을 깨닫게 되었다. 과연 이런 힙 자료구조가 코딩 테스트 문제에서 어떻게 적용이 되었는지 궁금하다.

참고

[자료구조] 힙(heap)이란 [자료구조] 우선순위 큐와 힙 (Priority Queue & Heap) [자료구조] JS로 구현하는 HEAP

📅 2022-09-12

Previous트리(Tree)Next트라이(Trie)

Last updated 3 years ago