[JS] 히프(Heap), 최대 히프와 최소 히프, 우선순위 큐

Wol-dan·2021년 9월 13일
자료구조
0

알고리즘&자료구조

목록 보기
2/7
post-thumbnail

힙(Heap)

  • 힙(Heap)은 트리 기반의 자료구조이다. 일반적으로 힙은 완전 이진 트리 구조를 사용한다. 완전 이진 트리의 경우 한 레벨이 모두 채워져야 다음 레벨로 트리가 늘어날 수 있다.

  • 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내기 위해 쓰인다.

  • 트리 내에 동일한 키값이 있을 수 있다.(우선순위 큐를 예로 들면 동일한 우선순위를 가진 데이터가 있을 수 있다는 말)

  • 힙의 종류

    • 최대 힙(Max-Heap): 부모 노드가 항상 자식 노드보다 크거나 같은 힙
    • 최소 힙(Min-Heap): 부모 노드가 항상 자식 노드보다 작거나 같은 힙
    • 두 힙 모두 힙 전체를 통틀어서 각자의 규칙이 꼭 유지되어야 한다.

image

  • 힙의 장점
    • 최소, 최대값을 O(1)의 시간복잡도로 얻어낼 수 있다. (ex. 최소 힙의 경우 최상위 노드만 조회하면 바로 최소값을 얻을 수 있다.)
    • 배열이나 연결리스트의 경우 최소, 최대값을 얻기 위해서 O(N)이 걸린다.(이진 탐색을 적용하면 O(log n)까지도 줄일 수 있긴 하다.)
    • 최소 힙은 우선순위 큐를 구현하는데 최적의 자료구조이다.
    • 다익스트라 알고리즘(최단 거리 구하기 알고리즘)에서 최소 비용을 기반으로 그래프를 탐색할 때 사용된다.

힙 구현하기

힙은 완전 이진 트리이고, 완전 이진 트리의 경우 1차원 배열로 구현하면 편리하다.

<힙을 배열로 구현할 때, 부모 노드와 자식 노드간의 관계(인덱스 규칙)>

자신의 인덱스 = N (이라고 하면)
왼쪽 자식 노드 인덱스 = (N * 2) + 1
오른쪽 자식 노드 인덱스 = (N * 2) + 2
부모 노드 인덱스 = (N - 1) / 2

*루트 노드는 인덱스가 0이다.

image

출처: geeksforgeeks

위 그림에서 최소 힙인 왼쪽의 트리는 우리가 살펴본 인덱스 규칙에 따라 다음과 같은 배열로 나타낼 수 있다.

[10, 15, 30, 40, 50, 100, 40]

히프의 키값들이 담긴 이 배열을 보면 레벨 순서로 히프를 순회했을 때의 순서대로 배열에 담겼음을 알 수 있다. 마지막에 있는 40이 히프의 가장 끝에 있는 값이다.

느슨한 정렬

힙에서는 부모 노드와 자식 노드의 우선순위만 신경쓰기 때문에 형제간의 우선순위는 고려되지 않는다. 이러한 정렬 상태를 느슨한 정렬 상태 = 약한 힙(weak heap)이라고 부른다. 그래서 전체트리를 볼 때 가장 아래 있는 노드가 가장 작거나 큰 값인건 아니다.

형제간의 우선순위가 고려되지 않는 이유는 무엇일까? 힙은 우선순위가 높은 순서대로 뽑는 것이 포인트이므로 형제간 우선순위와 무관하게 삽입할 때 우선순위가 높은 순서대로 나올 수 있도록 힙을 유지하고, 뽑을 때 또한 우선순위가 높은 순서대로 나오게만 하면 되기 때문이다.

삽입과 삭제로 깨진 힙을 재구조화하기 (heapify)

힙에서 삽입, 삭제가 일어나게 되면 경우에 따라 힙의 조건이 깨질 수 있다. 이런 경우 힙의(최대힙, 최소힙 각각의) 조건이 만족할 수 있도록 노드들의 위치를 바꿔가며 힙을 재구조화(heapify)해주는 과정이 필요하다. 삽입과 삭제의 경우 이런 heapify 과정을 거치기 때문에 O(log n)의 시간 복잡도를 가지게 된다.

삽입 구현 과정

새로운 노드는 가장 끝에 추가되고 이후 부모 노드와 비교하면서 재구조화(heapify) 과정을 수행한다. 삽입 과정은 아래에서 위로 재구조화 과정이 이루어지게 된다.

image

삭제 구현 과정

삭제는 루트 노드를 삭제하는데 이후 가장 마지막 노드를 루트 노드 자리에 대체한 뒤 재구조화 과정을 수행한다. (우선순위 큐에서도 가장 우선순위가 높은 루트 노드를 주로 삭제한다.) 삭제 과정은 위에서 아래로 재구조화 과정이 이루어지게 된다.

image

최소 힙(Min Heap) 구현하기

최소 힙의 규칙

  • 부모 노드는 항상 자식 노드보다 작거나 같다.
  • 완전 이진 트리(한 레벨이 모두 채워져야 다음 레벨로 트리가 늘어날 수 있다.)
class Heap {
  constructor() {
    this.heap = [];
  }

  // 값을 서로 바꾸는 메서드
  swap(indexA, indexB) {
    const temp = this.heap[indexA];
    this.heap[indexA] = this.heap[indexB];
    this.heap[indexB] = temp;
  }

  // 부모의 인덱스를 구하는 메서드
  parentIndex(index) {
    return Math.floor((index - 1) / 2);
  }
  // 왼쪽 자식의 인덱스를 구하는 메서드
  leftChildIndex(index) {
    return index * 2 + 1;
  }
  // 오른쪽 자식의 인덱스를 구하는 메서드
  rightChildIndex(index) {
    return index * 2 + 2;
  }
  // 부모 노드를 구하는 메서드
  parent(index) {
    return this.heap[this.parentIndex(index)];
  }
  // 왼쪽 자식 노드를 구하는 메서드
  leftChild(index) {
    return this.heap[this.leftChildIndex(index)];
  }
  // 오른쪽 자식 노드를 구하는 메서드
  rightChild(index) {
    return this.heap[this.rightChildIndex(index)];
  }
}

class MinHeap extends Heap {
  // 노드 추가
  add(node) {
    this.heap.push(node); // 노드를 히프의 가장 끝에 추가
    this.heapifyUp(); // 히프 가장 끝에 추가한 값을 올려가며 히프 재구조화
  }

  // 노드 삭제
  remove() {
    const rootItem = this.heap[0]; // 루트 노드값(삭제하려는 값)을 저장
    this.heap[0] = this.heap[this.heap.length - 1]; // 히프의 가장 끝에 값을 루트 노드로 올림
    this.heap.pop(); // 루트 노드로 올린 값은 히프에서 삭제
    this.heapifyDown(); // 루트 노드로 올린 값을 내려가며 히프 재구조화
    return rootItem;
  }

  heapifyUp() {
    // 부모노드와 비교해서 맨끝 노드가 작다면 교환. 아니면 정지
    let curIndex = this.heap.length - 1; // 계속 바뀌는 값

    // 부모 노드가 있고, 부모 노드보다 현재 노드가 값이 작을 때 반복
    while (
      this.parent(curIndex) !== undefined &&
      this.heap[curIndex] < this.parent(curIndex)
    ) {
      this.swap(curIndex, this.parentIndex(curIndex)); // 두 노드를 서로 바꿔줌(swap)
      curIndex = this.parentIndex(curIndex); // curIndex값 변경
    }
  }

  heapifyDown() {
    // 루트로 올린 노드의 왼쪽 자식과 오른쪽 자식을 비교해서 더 작은 값을 가진 자식과 위치를 교환
    let curIndex = 0; // 계속 바뀌는 값

    // 자식 노드가 있고 && 현재 노드가 왼쪽 자식이나 오른쪽 자식보다 클 때 계속 반복한다.(크면 내려야 하니까)
    // 자식 노드가 있는지 없는지는 왼쪽 노드가 undefined인지 아닌지 확인하면 알 수 있다.(완전 이진 트리이기 때문에 오른쪽 노드가 있는데 왼쪽노드는 비어있는 상황은 있을 수 없음.)
    while (
      this.leftChild(curIndex) !== undefined &&
      (this.leftChild(curIndex) < this.heap[curIndex] ||
        this.rightChild(curIndex) < this.heap[curIndex])
    ) {
      // 왼쪽 자식과 오른쪽 자식중 값이 더 작은 노드를 찾기
      const smallerIndex =
        this.leftChild(curIndex) < this.rightChild(curIndex)
          ? this.leftChildIndex(curIndex)
          : this.rightChildIndex(curIndex);
      // 찾은 그 노드와 현재 노드를 서로 바꾸기
      this.swap(curIndex, smallerIndex);
      // curIndex 값을 갱신하기
      curIndex = smallerIndex;
    }
  }

  // 최소값을 리턴하는 메서드
  getMin() {
    return this.heap[0];
  }
}

const minHeap = new MinHeap();
minHeap.add(10);
minHeap.add(15);
minHeap.add(30);
minHeap.add(40);
minHeap.add(50);
minHeap.add(100);
minHeap.add(40);
// 현재 힙의 상태: [10, 15, 30, 40, 50, 100, 40]

console.log(minHeap.getMin()); // 10
console.log(minHeap.heap); // [10, 15, 30, 40, 50, 100, 40]

minHeap.add(2);
console.log(minHeap.getMin()); // 2
console.log(minHeap.heap); // [2, 10, 30, 15, 50, 100, 40, 40]

minHeap.remove(); // 루트 노드가 삭제됨
console.log(minHeap.getMin()); // 10
console.log(minHeap.heap); // [10, 15, 30, 40, 50, 100, 40]

힙의 시간복잡도

  • 최소값, 최대값 구하기(peek): O(1)
  • 삽입: O(log n)
  • 삭제: O(log n)

힙에서 삽입, 삭제를 할 때는 힙을 재구조화하는 heapify 과정을 거친다. 최악의 경우 이 과정은 삽입, 삭제 전 힙의 높이만큼 걸린다.

힙은 완전 이진 트리이다. 완전 이진 트리의 노드가 모두 존재한다고 가정했을 때 높이를 h, 첫번째 레벨을 0, 노드의 개수를 n이라고 한다면 다음과 같이 힙의 높이 h를 구해 시간 복잡도를 구할 수 있다.

image

우선순위 큐(Priority Queue)

큐에 우선순위 개념을 도입한 자료구조. 데이터들이 우선순위를 가지고 있고, 삽입은 일반적인 큐와 같으나 삭제는 우선 순위가 가장 높은 것이 먼저 삭제되는 자료구조이다.

  • 시간 복잡도
    • 삽입: O(1)
    • 삭제: O(N) -> 모든 노드를 방문해 우선 순위가 높은 것을 기억해놓고 삭제해야하기 때문이다.

그런데 우선순위 큐를 히프로 구현하면 삽입, 삭제를 O(log N)에 해결할 수 있다.

최소, 최대 힙과 우선순위 큐

  • 숫자가 클수록 우선순위가 높은 문제 -> 최대 힙 사용
  • 숫자가 작을 수록 우선순위가 높은 문제 -> 최소 힙 사용

최소힙으로 우선순위 큐를 구현하면 다음과 같다.(숫자가 작을수록 우선순위가 높은 경우) 위에서 구현한 최소힙 코드와 거의 비슷하고, 배열에 데이터를 저장할 때 우선순위도 같이 저장한다는 것만 다르다. 우선순위 큐가 최소힙 class를 상속하도록 구현했다.

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

  // 값을 서로 바꾸는 메서드
  swap(indexA, indexB) {
    const temp = this.heap[indexA];
    this.heap[indexA] = this.heap[indexB];
    this.heap[indexB] = temp;
  }

  // 부모의 인덱스를 구하는 메서드
  parentIndex(index) {
    return Math.floor((index - 1) / 2);
  }
  // 왼쪽 자식의 인덱스를 구하는 메서드
  leftChildIndex(index) {
    return index * 2 + 1;
  }
  // 오른쪽 자식의 인덱스를 구하는 메서드
  rightChildIndex(index) {
    return index * 2 + 2;
  }
  // 부모 노드를 구하는 메서드
  parent(index) {
    return this.heap[this.parentIndex(index)];
  }
  // 왼쪽 자식 노드를 구하는 메서드
  leftChild(index) {
    return this.heap[this.leftChildIndex(index)];
  }
  // 오른쪽 자식 노드를 구하는 메서드
  rightChild(index) {
    return this.heap[this.rightChildIndex(index)];
  }
}

class MinHeap extends Heap {
  // 노드 추가
  add(key, value) {
    this.heap.push({ key, value }); // ✏️ 노드를 추가할 때 key에 priority를, value에 데이터를 저장하도록 한다.
    this.heapifyUp();
  }

  // 노드 삭제
  remove() {
    const rootItem = this.heap[0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    this.heapifyDown();
    return rootItem;
  }

  heapifyUp() {
    let curIndex = this.heap.length - 1;

    while (
      this.parent(curIndex) !== undefined &&
      this.heap[curIndex].key < this.parent(curIndex).key
    ) {
      this.swap(curIndex, this.parentIndex(curIndex));
      curIndex = this.parentIndex(curIndex);
    }
  }

  heapifyDown() {
    let curIndex = 0; // 계속 바뀌는 값

    while (
      this.leftChild(curIndex) !== undefined &&
      (this.leftChild(curIndex).key < this.heap[curIndex].key ||
        this.rightChild(curIndex).key < this.heap[curIndex].key)
    ) {
      const smallerIndex =
        this.leftChild(curIndex).key < this.rightChild(curIndex).key
          ? this.leftChildIndex(curIndex)
          : this.rightChildIndex(curIndex);
      this.swap(curIndex, smallerIndex);
      curIndex = smallerIndex;
    }
  }

  // 최소값을 리턴하는 메서드
  getMin() {
    return this.heap[0];
  }
}

class PriorityQueue extends MinHeap {
  enqueue(priority, value) {
    this.add(priority, value);
  }
  dequeue() {
    this.remove();
  }
  isEmpty() {
    return this.heap.length <= 0;
  }
}

const priQueue = new PriorityQueue();
priQueue.enqueue(10, 1);
priQueue.enqueue(15, 2);
priQueue.enqueue(30, 3);
priQueue.enqueue(40, 4);
priQueue.enqueue(50, 5);
priQueue.enqueue(100, 6);
priQueue.enqueue(40, 7);
console.log(priQueue.heap); //(1)
priQueue.dequeue();
console.log(priQueue.heap); //(2)
console.log(priQueue.isEmpty()); //(3)

실행 결과

// (1)
[
  { key: 10, value: 1 },
  { key: 15, value: 2 },
  { key: 30, value: 3 },
  { key: 40, value: 4 },
  { key: 50, value: 5 },
  { key: 100, value: 6 },
  { key: 40, value: 7 }
]

//(2)
[
  { key: 15, value: 2 },
  { key: 40, value: 7 },
  { key: 30, value: 3 },
  { key: 40, value: 4 },
  { key: 50, value: 5 },
  { key: 100, value: 6 }
]

//(3)
false

Ref

profile
Wol-dan
정리하고 모으고 커뮤니케이션하는 걸 좋아하는 새싹 웹 개발자🌱
이전 포스트

[JS] 트리(Tree), 이진 트리, 이진 탐색 트리

다음 포스트

📚 알고리즘&자료구조 Intro

0개의 댓글