heap.h

Go to the documentation of this file.

#pragma once
 
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>
 
#include "clustering/math/detail/heap_ops.h"
 
namespace clustering {

template <class Key, class Val> class BinaryHeap {
public:
  BinaryHeap() = default;

  void push(Key key, Val val) {
    m_heap.emplace_back(std::move(key), std::move(val));
    math::detail::siftUp(m_heap, m_heap.size() - 1, minOnKey);
  }

  [[nodiscard]] const std::pair<Key, Val> &top() const noexcept {
    assert(!m_heap.empty() && "BinaryHeap::top on empty heap");
    return m_heap.front();
  }

  void pop() noexcept {
    assert(!m_heap.empty() && "BinaryHeap::pop on empty heap");
    const std::size_t last = m_heap.size() - 1;
    if (last != 0) {
      m_heap[0] = std::move(m_heap[last]);
    }
    m_heap.pop_back();
    if (!m_heap.empty()) {
      math::detail::siftDown(m_heap, 0, minOnKey);
    }
  }

  [[nodiscard]] std::size_t size() const noexcept { return m_heap.size(); }

  [[nodiscard]] bool empty() const noexcept { return m_heap.empty(); }
 
private:
  static bool minOnKey(const std::pair<Key, Val> &a, const std::pair<Key, Val> &b) noexcept {
    return a.first < b.first;
  }
 
  std::vector<std::pair<Key, Val>> m_heap;
};

template <class Key, class Val, class Idx = std::uint32_t> class IndexedHeap {
public:
  static_assert(std::is_unsigned_v<Idx>, "IndexedHeap Idx must be an unsigned integer type");

  static constexpr std::size_t kNotInHeap = std::numeric_limits<std::size_t>::max();

  struct Entry {
    Idx handle;
    Key key;
    Val val;
  };

  explicit IndexedHeap(std::size_t capacity) : m_posMap(capacity, kNotInHeap) {}

  void push(Idx handle, Key key, Val val) {
    assert(static_cast<std::size_t>(handle) < m_posMap.size() &&
           "IndexedHeap::push handle out of range");
    assert(m_posMap[handle] == kNotInHeap && "IndexedHeap::push handle already in heap");
    const std::size_t pos = m_heap.size();
    m_heap.push_back(Entry{handle, std::move(key), std::move(val)});
    m_posMap[handle] = pos;
    siftUp(pos);
  }

  [[nodiscard]] bool contains(Idx handle) const noexcept {
    assert(static_cast<std::size_t>(handle) < m_posMap.size() &&
           "IndexedHeap::contains handle out of range");
    return m_posMap[handle] != kNotInHeap;
  }

  void decreaseKey(Idx handle, Key newKey) noexcept {
    assert(static_cast<std::size_t>(handle) < m_posMap.size() &&
           "IndexedHeap::decreaseKey handle out of range");
    const std::size_t pos = m_posMap[handle];
    assert(pos != kNotInHeap && "IndexedHeap::decreaseKey handle not in heap");
    assert(!(m_heap[pos].key < newKey) && "IndexedHeap::decreaseKey newKey > current key");
    m_heap[pos].key = std::move(newKey);
    siftUp(pos);
  }

  [[nodiscard]] const Entry &top() const noexcept {
    assert(!m_heap.empty() && "IndexedHeap::top on empty heap");
    return m_heap.front();
  }

  Entry pop() noexcept {
    assert(!m_heap.empty() && "IndexedHeap::pop on empty heap");
    Entry out = std::move(m_heap.front());
    m_posMap[out.handle] = kNotInHeap;
    const std::size_t last = m_heap.size() - 1;
    if (last != 0) {
      m_heap.front() = std::move(m_heap[last]);
      m_posMap[m_heap.front().handle] = 0;
    }
    m_heap.pop_back();
    if (!m_heap.empty()) {
      siftDown(0);
    }
    return out;
  }

  [[nodiscard]] std::size_t size() const noexcept { return m_heap.size(); }

  [[nodiscard]] bool empty() const noexcept { return m_heap.empty(); }

  [[nodiscard]] std::size_t capacity() const noexcept { return m_posMap.size(); }
 
private:
  std::vector<Entry> m_heap;
  std::vector<std::size_t> m_posMap;
 
  void swapEntries(std::size_t i, std::size_t j) noexcept {
    std::swap(m_heap[i], m_heap[j]);
    m_posMap[m_heap[i].handle] = i;
    m_posMap[m_heap[j].handle] = j;
  }
 
  void siftUp(std::size_t pos) noexcept {
    while (pos > 0) {
      const std::size_t parent = (pos - 1) / 2;
      if (m_heap[pos].key < m_heap[parent].key) {
        swapEntries(pos, parent);
        pos = parent;
      } else {
        return;
      }
    }
  }
 
  void siftDown(std::size_t pos) noexcept {
    const std::size_t n = m_heap.size();
    while (true) {
      const std::size_t left = (2 * pos) + 1;
      const std::size_t right = left + 1;
      std::size_t smallest = pos;
      if (left < n && m_heap[left].key < m_heap[smallest].key) {
        smallest = left;
      }
      if (right < n && m_heap[right].key < m_heap[smallest].key) {
        smallest = right;
      }
      if (smallest == pos) {
        return;
      }
      swapEntries(pos, smallest);
      pos = smallest;
    }
  }
};
 
} // namespace clustering