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

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_type length, bool is_max_heap = true)Create new heap object based on inp[] array of size length.
heapify(T inp[], size_type 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_type cap)equests 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))

구현

template <typename T>
class Heap {
private:
  using size_type = size_t;
  T* arr;
  size_type _size;
  size_type _capacity;
  bool is_max_heap;
  static constexpr size_type DEFAULT_CAP = 32;

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

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

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

    _size = length;
    size_type cur = getParent(_size - 1);

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

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

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

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

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

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

  inline size_type size() const { return _size; }
  inline size_type capacity() const { return _capacity; }
  inline bool empty() const { return _size == 0; }

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

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

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

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

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

      if (needToSwap(arr[to_swap], arr[left]))
        to_swap = left;
      if (right < _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;
      }
    }
  }
};

© 2020. All rights reserved.