Heap managing median (tools/median_heap.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2022-03-19 14:14:06+09:00
• Include: #include "tools/median_heap.hpp"

It is a heap managing median.

License

• CC0

Author

• anqooqie

Constructor

median_heap<T, Compare = std::less<T>> heap(Compare less = Compare());

It creates an empty heap.

Constraints

• None

Time Complexity

• $O(1)$

empty

bool heap.empty();

It returns whether the heap is empty or not.

Constraints

• None

Time Complexity

• $O(1)$

size

std::size_t heap.size();

It returns the number of elements in the heap.

Constraints

• None

Time Complexity

• $O(1)$

lesser

T heap.lesser();

It returns the $\left\lfloor\frac{N + 1}{2}\right\rfloor$-th smallest element in the heap where $N$ is the number of elements in the heap.

Constraints

• The heap is not empty.

Time Complexity

• $O(1)$

greater

T heap.greater();

It returns the $\left(\left\lfloor\frac{N}{2}\right\rfloor + 1\right)$-th smallest element in the heap where $N$ is the number of elements in the heap.

Constraints

• The heap is not empty.

Time Complexity

• $O(1)$

push

void heap.push(T x);

It adds $x$ to the heap.

Constraints

• None

Time Complexity

• $O(\log N)$ where $N$ is the number of elements in the heap

emplace

template <typename... Args>
void heap.emplace(Args&&... args);

It adds T(args...) to the heap.

Constraints

• None

Time Complexity

• $O(\log N)$ where $N$ is the number of elements in the heap

swap

void heap.swap(median_heap<T, Compare>& other);

It swaps heap and other.

Constraints

• None

Time Complexity

• $O(1)$

Verified with

• tests/median_heap.test.cpp

Code

#ifndef TOOLS_MEDIAN_HEAP_HPP
#define TOOLS_MEDIAN_HEAP_HPP

#include <functional>
#include <queue>
#include <vector>
#include <cstddef>
#include <cassert>

namespace tools {

  template <typename T, typename Compare = ::std::less<T>>
  class median_heap {
  private:
    class RevCompare {
    private:
      Compare m_less;
    public:
      explicit RevCompare(const Compare& less) : m_less(less) {
      }
      bool operator()(const T& x, const T& y) const {
        return this->m_less(y, x);
      }
    };

    Compare m_less;
    ::std::priority_queue<T, ::std::vector<T>, Compare> m_pq1;
    ::std::priority_queue<T, ::std::vector<T>, RevCompare> m_pq2;

  public:
    explicit median_heap(const Compare& less) : m_less(less), m_pq1(less), m_pq2(RevCompare(less)) {
    }
    median_heap() : median_heap(Compare()) {
    }
    median_heap(const ::tools::median_heap<T, Compare>&) = default;
    median_heap(::tools::median_heap<T, Compare>&&) = default;
    ~median_heap() = default;
    ::tools::median_heap<T, Compare>& operator=(const ::tools::median_heap<T, Compare>&) = default;
    ::tools::median_heap<T, Compare>& operator=(::tools::median_heap<T, Compare>&&) = default;

    bool empty() const {
      return this->m_pq1.empty() && this->m_pq2.empty();
    }

    ::std::size_t size() const {
      return this->m_pq1.size() + this->m_pq2.size();
    }

    T lesser() const {
      assert(!this->empty());
      return this->m_pq1.top();
    }

    T greater() const {
      assert(!this->empty());
      return this->m_pq1.size() == this->m_pq2.size() ? this->m_pq2.top() : this->m_pq1.top();
    }

    void push(const T& v) {
      if (this->m_pq1.size() == this->m_pq2.size()) {
        if (!this->m_pq2.empty() && this->m_less(this->m_pq2.top(), v)) {
          this->m_pq1.push(this->m_pq2.top());
          this->m_pq2.pop();
          this->m_pq2.push(v);
        } else {
          this->m_pq1.push(v);
        }
      } else {
        if (this->m_less(v, this->m_pq1.top())) {
          this->m_pq2.push(this->m_pq1.top());
          this->m_pq1.pop();
          this->m_pq1.push(v);
        } else {
          this->m_pq2.push(v);
        }
      }
    }

    template <typename... Args>
    void emplace(Args&&... args) {
      this->push(T(::std::forward<Args>(args)...));
    }

    void swap(::tools::median_heap<T, Compare>& other) {
      ::std::swap(this->m_less, other.m_less);
      this->m_pq1.swap(other.m_pq1);
      this->m_pq2.swap(other.m_pq2);
    }
  };
}

#endif

#line 1 "tools/median_heap.hpp"



#include <functional>
#include <queue>
#include <vector>
#include <cstddef>
#include <cassert>

namespace tools {

  template <typename T, typename Compare = ::std::less<T>>
  class median_heap {
  private:
    class RevCompare {
    private:
      Compare m_less;
    public:
      explicit RevCompare(const Compare& less) : m_less(less) {
      }
      bool operator()(const T& x, const T& y) const {
        return this->m_less(y, x);
      }
    };

    Compare m_less;
    ::std::priority_queue<T, ::std::vector<T>, Compare> m_pq1;
    ::std::priority_queue<T, ::std::vector<T>, RevCompare> m_pq2;

  public:
    explicit median_heap(const Compare& less) : m_less(less), m_pq1(less), m_pq2(RevCompare(less)) {
    }
    median_heap() : median_heap(Compare()) {
    }
    median_heap(const ::tools::median_heap<T, Compare>&) = default;
    median_heap(::tools::median_heap<T, Compare>&&) = default;
    ~median_heap() = default;
    ::tools::median_heap<T, Compare>& operator=(const ::tools::median_heap<T, Compare>&) = default;
    ::tools::median_heap<T, Compare>& operator=(::tools::median_heap<T, Compare>&&) = default;

    bool empty() const {
      return this->m_pq1.empty() && this->m_pq2.empty();
    }

    ::std::size_t size() const {
      return this->m_pq1.size() + this->m_pq2.size();
    }

    T lesser() const {
      assert(!this->empty());
      return this->m_pq1.top();
    }

    T greater() const {
      assert(!this->empty());
      return this->m_pq1.size() == this->m_pq2.size() ? this->m_pq2.top() : this->m_pq1.top();
    }

    void push(const T& v) {
      if (this->m_pq1.size() == this->m_pq2.size()) {
        if (!this->m_pq2.empty() && this->m_less(this->m_pq2.top(), v)) {
          this->m_pq1.push(this->m_pq2.top());
          this->m_pq2.pop();
          this->m_pq2.push(v);
        } else {
          this->m_pq1.push(v);
        }
      } else {
        if (this->m_less(v, this->m_pq1.top())) {
          this->m_pq2.push(this->m_pq1.top());
          this->m_pq1.pop();
          this->m_pq1.push(v);
        } else {
          this->m_pq2.push(v);
        }
      }
    }

    template <typename... Args>
    void emplace(Args&&... args) {
      this->push(T(::std::forward<Args>(args)...));
    }

    void swap(::tools::median_heap<T, Compare>& other) {
      ::std::swap(this->m_less, other.m_less);
      this->m_pq1.swap(other.m_pq1);
      this->m_pq2.swap(other.m_pq2);
    }
  };
}

Back to top page