C++ Heap (Priority Queue) 구현하기

in Dev. Log on Algorithm, Data Structure

Don’t reinvent the wheel; use libraries.

From <The C++ Programming Language> by Bjarne Stroustrup

들어가기에 앞서

앞으로 게시될 일련의 게시물들은 STL을 쓰지 못하는 특정 상황을 위해 STL과 비슷하게 동작하는 container, data structure, algorithm 등을 구현한 것 들입니다.
STL 상의 모든 함수들을 구현하지는 못하였지만(특히 iterator 관련…) 사용하는데 큰 지장은 없을 것 입니다.

STL을 사용할 수 있는 상황이라면 꼭 STL을 사용하도록 합시다. 나보다 똑똑한 사람들이 나보다 더 많은 시간을 들여서 작성하고 최적화한 코드입니다.

구현된 STL-like 자료 구조들은 Github Repo에서도 확인 하실 수 있습니다.

혹시나 있을 버그는 댓글 혹은 이메일로 제보해 주시면 수정하도록 하겠습니다.

Documents

FunctionDescription
Heap(bool is_max_heap = true)Create empty heap object.(Default:Max-heap) Set parameter to false for creating Min-heap
Heap(T inp[], size_t length, bool is_max_heap = true)Create new heap object based on inp[] array of size length.
heapify(T inp[], size_t length, bool is_max_heap = true)Sort given array. O(N)
push(T item)Push given item into heap.
pop()Remove first item from the heap. Use top() to get item.
top()Get first item of heap.
reserve(size_t cap)Requests that the capacity be at least enough to contain n elements.
clear()Removes all elements from the heap.
(capacity is set to DEFAULT_CAP & Max-heap/Min-heap property is preserved.)
clear(bool is_max_heap)Removes all elements from the heap.
(capacity is set to DEFAULT_CAP & You may change Max-heap/Min-heap property)
size()Returns the number of elements in the heap.
capacity()Returns the size of the storage space currently allocated for the heap.
empty()Returns true if heap is empty (i.e. its size is 0).

잡담

Max-heap / Min-heap으로 사용 가능한 컨테이너입니다.
heapify()가 siftDown()을 사용하도록 구현되어 있습니다.
(Time Complexity = O(N) / siftUp()으로 구현시 O(NlogN))

구현

#include <stdexcept>

template <typename T>
class Heap {
private:
  static constexpr size_t DEFAULT_CAP = 32;
  T* arr;
  size_t m_size;
  size_t m_capacity;
  bool is_max_heap;

public:
  Heap(bool is_max_heap = true) : arr{new T[DEFAULT_CAP]}, m_size{0}, m_capacity{DEFAULT_CAP}, is_max_heap{is_max_heap} {}
  Heap(T inp[], size_t length, bool is_max_heap = true) : arr{nullptr}, m_size{length}, m_capacity{DEFAULT_CAP}, is_max_heap{is_max_heap} {
    heapify(inp, length);
  }
  ~Heap() { delete[] arr; }

  void heapify(T inp[], size_t length, bool is_max_heap = true) {
    this->is_max_heap = is_max_heap;
    if (length > m_capacity) {
      while (length > m_capacity)
        m_capacity *= 2;
      delete[] arr;
      arr = new T[m_capacity];
    }

    for (size_t i = 0; i < length; i++)
      arr[i] = inp[i];

    m_size = length;
    size_t cur = getParent(m_size - 1);

    while (cur > 0)
      siftDown(cur--);
    siftDown(cur);
  }

  void push(T item) {
    if (m_size == m_capacity) {
      m_capacity *= 2;
      T *tmp = new T[m_capacity];
      for (size_t i = 0; i < m_size; i++)
        tmp[i] = arr[i];
      delete[] arr;
      arr = tmp;
    }
    arr[m_size] = item;
    siftUp(m_size++);
  }

  void pop() {
    if (m_size == 0)
      throw std::out_of_range("Empty heap");
    arr[0] = arr[--m_size];
    siftDown(0);
  }

  T top() const {
    if (m_size == 0)
      throw std::out_of_range("Empty heap");
    return arr[0];
  }

  void reserve(size_t cap) {
    if (m_capacity >= cap)
      return;
    T *tmp = new T[cap];
    for (size_t i = 0; i < m_size; i++)
      tmp[i] = arr[i];
    delete[] arr;
    arr = tmp;
    m_capacity = cap;
  }

  void clear(bool is_max_heap) {
    if (m_capacity != DEFAULT_CAP) {
      delete[] arr;
      arr = new T[DEFAULT_CAP];
      m_capacity = DEFAULT_CAP;
    }
    m_size = 0;
    this->is_max_heap = is_max_heap;
  }
  void clear() { clear(is_max_heap); }

  size_t size() const { return m_size; }
  size_t capacity() const { return m_capacity; }
  bool empty() const { return m_size == 0; }

private:
  size_t getParent(size_t idx) const { return (idx - 1) >> 1; }
  size_t getLeftChild(size_t idx) const { return (idx << 1) + 1; }
  size_t getRightChild(size_t idx) const { return (idx << 1) + 2; }

  bool needToSwap(T& a, T& b) const {
    if (is_max_heap)
      return a < b;
    else
      return b < a;
  }

  void swap(T& a, T& b) {
    T tmp = a;
    a = b;
    b = tmp;
  }

  void siftUp(size_t cur) {
    while (true) {
      if (cur == 0)
        break;
      size_t parent = getParent(cur);
      if (needToSwap(arr[parent], arr[cur]))
        swap(arr[cur], arr[parent]);
      else
        break;
      cur = parent;
    }
  }

  void siftDown(size_t cur) {
    while (getLeftChild(cur) < m_size) {
      size_t left = getLeftChild(cur), right = getRightChild(cur);
      size_t to_swap = cur;

      if (needToSwap(arr[to_swap], arr[left]))
        to_swap = left;
      if (right < m_size && needToSwap(arr[to_swap], arr[right]))
        to_swap = right;

      if (to_swap != cur) {
        swap(arr[to_swap], arr[cur]);
        cur = to_swap;
      } else {
          return;
      }
    }
  }
};