Heap

Heap 은 완전 이진 트리 기반의 자료구조이다.
(즉, 가장 아래 층을 제외한 모든 레벨이 완전히 채워져야 한다.)

규칙에 따라 Max Heap 과 Min Heap 으로 나뉜다.

  • Max Heap 은 부모 노드가 항상 자식 노드보다 크거나 같은 이진 트리.

  • Min Heap 은 부모 노드가 항상 자식 노드보다 작거나 같은 이진 트리.

시간 복잡도

  • peek O(1) : 최상단 노드 return
  • poll O(logn) : 최상단 노드 제거 후 return
  • insert O(logn) : 새로운 노드 추가

배열 사용하기

배열을 사용해 이진 트리를 다루려면 아래 개념을 알고 있어야 한다.

getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1;
getRightChildIndex = (parentIndex) => parentIndex * 2 + 2;
getParentIndex = (childIndex) => Math.floor((childIndex - 1) / 2);

헷갈리면 그림을 그리며 계산해보는 것이 좋다.

코드로 구현하기

우선 Heap 을 구현해보자.
(Min 또는 Max 에 따라 구현체가 달라지는 heapifyUp, heapifyDown 은 abstract method 로 선언한다.)

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

  // 이진 트리구조를 배열로 다루기 위해 index 계산 method 정의
  getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1;
  getRightChildIndex = (parentIndex) => parentIndex * 2 + 2;
  getParentIndex = (childIndex) => Math.floor((childIndex - 1) / 2);

  // 최상위 노드 return
  peek = () => this.heap[0];

  // 최상위 노드 꺼내고 return
  poll = () => {
    const count = this.heap.length;
    const root = this.heap[0];

    if (count <= 0) return undefined;
    if (count === 1) this.heap = [];
    else {
      this.heap[0] = this.heap.pop()
      this.heapifyDown();
    }

    return root;
  }

  insert = (key, value) => {
    const node = { key, value };
    this.heap.push(node);
    this.heapifyUp();
  }

  // abstract
  heapifyUp = () => {
    throw new Error('Abstract Method !');
  }

  // abstract
  heapifyDown = () => {
    throw new Error('Abstract Method !');
  }
}

Max Heap

위의 Heap 을 상속하는 MaxHeap 구현하기

class MaxHeap extends Heap {
  constructor() {
    super();
  }

  // 가장 마지막 노드 (leaf) -> parent 와 비교하며 위로 올림
  heapifyUp = () => {
    let index = this.heap.length - 1;
    const lastInsertedNode = this.heap[index];

    while (index > 0) {
      const parentIndex = this.getParentIndex(index);

      if (this.heap[parentIndex].key < lastInsertedNode.key) {
        // swap
        this.heap[index] = this.heap[parentIndex];
        this.heap[parentIndex] = lastInsertedNode;
        index = parentIndex;
      } else break;
    }
  }

  // root 를 child 와 비교하며 아래로 내림
  heapifyDown = () => {
    let index = 0;
    const root = this.heap[index]
    const count = this.heap.length;

    // 계속해서 left child 가 있을 때 까지 검사
    while (this.getLeftChildIndex(index) < count) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);

      // 왼쪽, 오른쪽 중 더 큰 노드를 찾는다.
      // // 오른쪽 child 있을 때는 left - right 비교
      // // 없을 대는 leftChild 가 더 큰 값을 갖는다.
      const biggerChildIndex =
        rightChildIndex < count
        && this.heap[rightChildIndex].key > this.heap[leftChildIndex].key
          ? rightChildIndex
          : leftChildIndex;

      // 자식 노드의 키 값이 루트노드보다 크면 위로 끌어올린다.
      if (this.heap[biggerChildIndex].key >= root.key) {
        this.heap[index] = this.heap[biggerChildIndex];
        index = biggerChildIndex;
      } else break;
    }

    this.heap[index] = root;
  }
}

Min Heap


class MinHeap extends Heap {
  constructor() {
    super();
  }

  // 가장 마지막 노드 (leaf) -> parent 와 비교하며 위로 올림
  heapifyUp = () => {
    let index = this.heap.length - 1;
    const lastInsertedNode = this.heap[index];

    while (index > 0) {
      const parentIndex = this.getParentIndex(index);

      if (this.heap[parentIndex].key > lastInsertedNode.key) {
        // swap
        this.heap[index] = this.heap[parentIndex];
        this.heap[parentIndex] = lastInsertedNode;

        index = parentIndex;
      } else break;
    }
  }

  // root 를 child 와 비교하며 아래로 내림
  heapifyDown = () => {
    let index = 0;
    const root = this.heap[index]
    const count = this.heap.length;

    // 계속해서 left child 가 있을 때 까지 검사
    while (this.getLeftChildIndex(index) < count) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);

      // 왼쪽, 오른쪽 중 더 작은 노드를 찾는다.
      // // 오른쪽 child 있을 때는 left - right 비교
      // // 없을 대는 leftChild 가 더 작은 값을 갖는다.
      const smallerChildIndex =
        rightChildIndex < count
        && this.heap[rightChildIndex].key < this.heap[leftChildIndex].key
          ? rightChildIndex
          : leftChildIndex;

      // 자식 노드의 키 값이 루트노드보다 작으면 위로 끌어올린다.
      if (this.heap[smallerChildIndex].key <= root.key) {
        this.heap[index] = this.heap[smallerChildIndex];
        index = smallerChildIndex;
      } else break;
    }

    this.heap[index] = root;
  }
}

Priority Queue

마지막으로 Min Heap 을 상속하는 우선순위 큐를 구현해보자.

class PriorityQueue extends MinHeap {
  constructor() {
    super();
    this.queue = this.heap;
  }

  enqueue = (priority, value) => this.insert(priority, value);
  dequeue = () => this.poll();
  isEmpty = () => this.heap.length <= 0;
}


const q = new PriorityQueue();

q.enqueue(100, 100);
q.enqueue(50, 50);
q.enqueue(10, 10);
q.enqueue(80, 80);
q.enqueue(60, 60);
q.enqueue(30, 30);
q.enqueue(70, 70);

q.queue 를 출력하면 아래와 같다.

queue

얼핏 보면 우선 순위가 맞지 않는 것 같지만, 아래 처럼 도식화 해보면 제대로 동작한 것을 알 수 있다.

(부모 노드가 항상 작은 값을 가진다.)

                  3 (100)
                /
         1 (60) 
       /        \
      /           4 (80)
0 (10) 
      \           5 (50)
       \        /
         2 (30) 
                \
                  6 (70)

그리고 이들을 dequeue 해보면 값이 우선순위대로 출력되는 것을 확인할 수 있다.

queue