Double-Ended Priority Queue
(ds/heap/double_ended_priority_queue.hpp)

• View this file on GitHub
• Last update: 2026-07-13 05:54:43+09:00
• Include: #include "ds/heap/double_ended_priority_queue.hpp"

Overview

DoubleEndedPriorityQueue<T, Compare> is a min-max heap stored in one contiguous array. It inserts values and removes either extreme in logarithmic time, while reading both extremes takes constant time.

Unlike an implementation made from two lazily synchronized heaps, this structure stores each element once and never accumulates stale entries. It uses $O(N)$ memory even if insertions and removals are interleaved for a long time.

MinMaxHeap<T, Compare> is an alias for the same type.

Ordering

Compare defines the ordering and defaults to std::less<T>:

• min() returns the first element in the Compare ordering.
• max() returns the last element in the Compare ordering.
• Equal values are stored separately, so the structure behaves as a multiset.

With the default comparator these are the usual numeric minimum and maximum. With std::greater<T>, their roles are reversed.

Interface

template <class T, class Compare = std::less<T>>
class DoubleEndedPriorityQueue {
public:
    DoubleEndedPriorityQueue();
    explicit DoubleEndedPriorityQueue(Compare compare);
    DoubleEndedPriorityQueue(
        std::initializer_list<T> values,
        Compare compare = Compare()
    );

    template <class Iterator>
    DoubleEndedPriorityQueue(
        Iterator first,
        Iterator last,
        Compare compare = Compare()
    );

    std::size_t size() const;
    bool empty() const;
    const T& min() const;
    const T& max() const;

    void clear();

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

    void push(const T& value);
    void push(T&& value);
    void pop_min();
    void pop_max();

    const Compare& comparator() const;
};

template <class T, class Compare = std::less<T>>
using MinMaxHeap = DoubleEndedPriorityQueue<T, Compare>;

Complexity

Method	Description	Complexity
Default/comparator constructor	Creates an empty queue.	$O(1)$
Initializer-list/range constructor	Inserts all $N$ supplied values.	$O(N\log N)$
push(value)	Inserts one value.	$O(\log N)$
emplace(args...)	Constructs and inserts one value.	$O(\log N)$
min()	Returns the minimum without removing it.	$O(1)$
max()	Returns the maximum without removing it.	$O(1)$
pop_min()	Removes one minimum value.	$O(\log N)$
pop_max()	Removes one maximum value.	$O(\log N)$
size()	Returns the number of stored values.	$O(1)$
empty()	Returns whether the queue is empty.	$O(1)$
clear()	Removes every value.	$O(N)$
comparator()	Returns the comparator.	$O(1)$

The data structure uses $O(N)$ memory. min, max, pop_min, and pop_max require a nonempty queue. Queries do not mutate the structure; both removal methods do.

Example

#include "ds/heap/double_ended_priority_queue.hpp"

#include <iostream>

int main() {
    m1une::ds::DoubleEndedPriorityQueue<int> queue = {5, 2, 8, 2};

    std::cout << queue.min() << '\n';  // 2
    queue.pop_min();
    std::cout << queue.max() << '\n';  // 8
    queue.pop_max();

    queue.push(10);
    std::cout << queue.max() << '\n';  // 10
}

Verified with

• verify/ds/heap/double_ended_priority_queue.test.cpp

Code

#ifndef M1UNE_DS_HEAP_DOUBLE_ENDED_PRIORITY_QUEUE_HPP
#define M1UNE_DS_HEAP_DOUBLE_ENDED_PRIORITY_QUEUE_HPP 1

#include <bit>
#include <cassert>
#include <cstddef>
#include <functional>
#include <initializer_list>
#include <utility>
#include <vector>

namespace m1une {
namespace ds {

// Min-max heap supporting access to both extremes of a total ordering.
template <class T, class Compare = std::less<T>>
class DoubleEndedPriorityQueue {
   private:
    std::vector<T> _values;
    [[no_unique_address]] Compare _compare;

    static std::size_t parent(std::size_t index) {
        return (index - 1) / 2;
    }

    static std::size_t grandparent(std::size_t index) {
        return (index - 3) / 4;
    }

    static bool is_min_level(std::size_t index) {
        const int level = int(std::bit_width(index + 1)) - 1;
        return level % 2 == 0;
    }

    void bubble_up_min(std::size_t index) {
        while (index >= 3) {
            const std::size_t ancestor = grandparent(index);
            if (!_compare(_values[index], _values[ancestor])) break;
            std::swap(_values[index], _values[ancestor]);
            index = ancestor;
        }
    }

    void bubble_up_max(std::size_t index) {
        while (index >= 3) {
            const std::size_t ancestor = grandparent(index);
            if (!_compare(_values[ancestor], _values[index])) break;
            std::swap(_values[index], _values[ancestor]);
            index = ancestor;
        }
    }

    std::size_t minimum_descendant(std::size_t index) const {
        std::size_t result = _values.size();
        const std::size_t first_child = index * 2 + 1;
        const std::size_t first_grandchild = index * 4 + 3;
        for (std::size_t candidate = first_child;
             candidate < _values.size() && candidate < first_child + 2;
             candidate++) {
            if (result == _values.size() ||
                _compare(_values[candidate], _values[result])) {
                result = candidate;
            }
        }
        for (std::size_t candidate = first_grandchild;
             candidate < _values.size() && candidate < first_grandchild + 4;
             candidate++) {
            if (result == _values.size() ||
                _compare(_values[candidate], _values[result])) {
                result = candidate;
            }
        }
        return result;
    }

    std::size_t maximum_descendant(std::size_t index) const {
        std::size_t result = _values.size();
        const std::size_t first_child = index * 2 + 1;
        const std::size_t first_grandchild = index * 4 + 3;
        for (std::size_t candidate = first_child;
             candidate < _values.size() && candidate < first_child + 2;
             candidate++) {
            if (result == _values.size() ||
                _compare(_values[result], _values[candidate])) {
                result = candidate;
            }
        }
        for (std::size_t candidate = first_grandchild;
             candidate < _values.size() && candidate < first_grandchild + 4;
             candidate++) {
            if (result == _values.size() ||
                _compare(_values[result], _values[candidate])) {
                result = candidate;
            }
        }
        return result;
    }

    void trickle_down_min(std::size_t index) {
        while (true) {
            const std::size_t descendant = minimum_descendant(index);
            if (descendant == _values.size()) return;
            if (parent(descendant) == index) {
                if (_compare(_values[descendant], _values[index])) {
                    std::swap(_values[descendant], _values[index]);
                }
                return;
            }
            if (!_compare(_values[descendant], _values[index])) return;
            std::swap(_values[descendant], _values[index]);
            const std::size_t descendant_parent = parent(descendant);
            if (_compare(_values[descendant_parent], _values[descendant])) {
                std::swap(_values[descendant_parent], _values[descendant]);
            }
            index = descendant;
        }
    }

    void trickle_down_max(std::size_t index) {
        while (true) {
            const std::size_t descendant = maximum_descendant(index);
            if (descendant == _values.size()) return;
            if (parent(descendant) == index) {
                if (_compare(_values[index], _values[descendant])) {
                    std::swap(_values[descendant], _values[index]);
                }
                return;
            }
            if (!_compare(_values[index], _values[descendant])) return;
            std::swap(_values[descendant], _values[index]);
            const std::size_t descendant_parent = parent(descendant);
            if (_compare(_values[descendant], _values[descendant_parent])) {
                std::swap(_values[descendant_parent], _values[descendant]);
            }
            index = descendant;
        }
    }

    void restore_after_push(std::size_t index) {
        if (index == 0) return;
        const std::size_t ancestor = parent(index);
        if (is_min_level(index)) {
            if (_compare(_values[ancestor], _values[index])) {
                std::swap(_values[ancestor], _values[index]);
                bubble_up_max(ancestor);
            } else {
                bubble_up_min(index);
            }
        } else {
            if (_compare(_values[index], _values[ancestor])) {
                std::swap(_values[ancestor], _values[index]);
                bubble_up_min(ancestor);
            } else {
                bubble_up_max(index);
            }
        }
    }

    std::size_t maximum_index() const {
        assert(!_values.empty());
        if (_values.size() == 1) return 0;
        if (_values.size() == 2 || !_compare(_values[1], _values[2])) return 1;
        return 2;
    }

   public:
    DoubleEndedPriorityQueue() = default;

    explicit DoubleEndedPriorityQueue(Compare compare)
        : _compare(std::move(compare)) {}

    DoubleEndedPriorityQueue(std::initializer_list<T> values,
                             Compare compare = Compare())
        : DoubleEndedPriorityQueue(std::move(compare)) {
        for (const T& value : values) push(value);
    }

    template <class Iterator>
    DoubleEndedPriorityQueue(Iterator first, Iterator last,
                             Compare compare = Compare())
        : DoubleEndedPriorityQueue(std::move(compare)) {
        while (first != last) {
            push(*first);
            ++first;
        }
    }

    std::size_t size() const {
        return _values.size();
    }

    bool empty() const {
        return _values.empty();
    }

    const T& min() const {
        assert(!empty());
        return _values[0];
    }

    const T& max() const {
        return _values[maximum_index()];
    }

    void clear() {
        _values.clear();
    }

    template <class... Args>
    void emplace(Args&&... args) {
        _values.emplace_back(std::forward<Args>(args)...);
        restore_after_push(_values.size() - 1);
    }

    void push(const T& value) {
        emplace(value);
    }

    void push(T&& value) {
        emplace(std::move(value));
    }

    void pop_min() {
        assert(!empty());
        if (_values.size() == 1) {
            _values.pop_back();
            return;
        }
        _values[0] = std::move(_values.back());
        _values.pop_back();
        trickle_down_min(0);
    }

    void pop_max() {
        assert(!empty());
        const std::size_t index = maximum_index();
        if (index == _values.size() - 1) {
            _values.pop_back();
            return;
        }
        _values[index] = std::move(_values.back());
        _values.pop_back();
        trickle_down_max(index);
    }

    const Compare& comparator() const {
        return _compare;
    }
};

template <class T, class Compare = std::less<T>>
using MinMaxHeap = DoubleEndedPriorityQueue<T, Compare>;

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_DS_HEAP_DOUBLE_ENDED_PRIORITY_QUEUE_HPP

#line 1 "ds/heap/double_ended_priority_queue.hpp"



#include <bit>
#include <cassert>
#include <cstddef>
#include <functional>
#include <initializer_list>
#include <utility>
#include <vector>

namespace m1une {
namespace ds {

// Min-max heap supporting access to both extremes of a total ordering.
template <class T, class Compare = std::less<T>>
class DoubleEndedPriorityQueue {
   private:
    std::vector<T> _values;
    [[no_unique_address]] Compare _compare;

    static std::size_t parent(std::size_t index) {
        return (index - 1) / 2;
    }

    static std::size_t grandparent(std::size_t index) {
        return (index - 3) / 4;
    }

    static bool is_min_level(std::size_t index) {
        const int level = int(std::bit_width(index + 1)) - 1;
        return level % 2 == 0;
    }

    void bubble_up_min(std::size_t index) {
        while (index >= 3) {
            const std::size_t ancestor = grandparent(index);
            if (!_compare(_values[index], _values[ancestor])) break;
            std::swap(_values[index], _values[ancestor]);
            index = ancestor;
        }
    }

    void bubble_up_max(std::size_t index) {
        while (index >= 3) {
            const std::size_t ancestor = grandparent(index);
            if (!_compare(_values[ancestor], _values[index])) break;
            std::swap(_values[index], _values[ancestor]);
            index = ancestor;
        }
    }

    std::size_t minimum_descendant(std::size_t index) const {
        std::size_t result = _values.size();
        const std::size_t first_child = index * 2 + 1;
        const std::size_t first_grandchild = index * 4 + 3;
        for (std::size_t candidate = first_child;
             candidate < _values.size() && candidate < first_child + 2;
             candidate++) {
            if (result == _values.size() ||
                _compare(_values[candidate], _values[result])) {
                result = candidate;
            }
        }
        for (std::size_t candidate = first_grandchild;
             candidate < _values.size() && candidate < first_grandchild + 4;
             candidate++) {
            if (result == _values.size() ||
                _compare(_values[candidate], _values[result])) {
                result = candidate;
            }
        }
        return result;
    }

    std::size_t maximum_descendant(std::size_t index) const {
        std::size_t result = _values.size();
        const std::size_t first_child = index * 2 + 1;
        const std::size_t first_grandchild = index * 4 + 3;
        for (std::size_t candidate = first_child;
             candidate < _values.size() && candidate < first_child + 2;
             candidate++) {
            if (result == _values.size() ||
                _compare(_values[result], _values[candidate])) {
                result = candidate;
            }
        }
        for (std::size_t candidate = first_grandchild;
             candidate < _values.size() && candidate < first_grandchild + 4;
             candidate++) {
            if (result == _values.size() ||
                _compare(_values[result], _values[candidate])) {
                result = candidate;
            }
        }
        return result;
    }

    void trickle_down_min(std::size_t index) {
        while (true) {
            const std::size_t descendant = minimum_descendant(index);
            if (descendant == _values.size()) return;
            if (parent(descendant) == index) {
                if (_compare(_values[descendant], _values[index])) {
                    std::swap(_values[descendant], _values[index]);
                }
                return;
            }
            if (!_compare(_values[descendant], _values[index])) return;
            std::swap(_values[descendant], _values[index]);
            const std::size_t descendant_parent = parent(descendant);
            if (_compare(_values[descendant_parent], _values[descendant])) {
                std::swap(_values[descendant_parent], _values[descendant]);
            }
            index = descendant;
        }
    }

    void trickle_down_max(std::size_t index) {
        while (true) {
            const std::size_t descendant = maximum_descendant(index);
            if (descendant == _values.size()) return;
            if (parent(descendant) == index) {
                if (_compare(_values[index], _values[descendant])) {
                    std::swap(_values[descendant], _values[index]);
                }
                return;
            }
            if (!_compare(_values[index], _values[descendant])) return;
            std::swap(_values[descendant], _values[index]);
            const std::size_t descendant_parent = parent(descendant);
            if (_compare(_values[descendant], _values[descendant_parent])) {
                std::swap(_values[descendant_parent], _values[descendant]);
            }
            index = descendant;
        }
    }

    void restore_after_push(std::size_t index) {
        if (index == 0) return;
        const std::size_t ancestor = parent(index);
        if (is_min_level(index)) {
            if (_compare(_values[ancestor], _values[index])) {
                std::swap(_values[ancestor], _values[index]);
                bubble_up_max(ancestor);
            } else {
                bubble_up_min(index);
            }
        } else {
            if (_compare(_values[index], _values[ancestor])) {
                std::swap(_values[ancestor], _values[index]);
                bubble_up_min(ancestor);
            } else {
                bubble_up_max(index);
            }
        }
    }

    std::size_t maximum_index() const {
        assert(!_values.empty());
        if (_values.size() == 1) return 0;
        if (_values.size() == 2 || !_compare(_values[1], _values[2])) return 1;
        return 2;
    }

   public:
    DoubleEndedPriorityQueue() = default;

    explicit DoubleEndedPriorityQueue(Compare compare)
        : _compare(std::move(compare)) {}

    DoubleEndedPriorityQueue(std::initializer_list<T> values,
                             Compare compare = Compare())
        : DoubleEndedPriorityQueue(std::move(compare)) {
        for (const T& value : values) push(value);
    }

    template <class Iterator>
    DoubleEndedPriorityQueue(Iterator first, Iterator last,
                             Compare compare = Compare())
        : DoubleEndedPriorityQueue(std::move(compare)) {
        while (first != last) {
            push(*first);
            ++first;
        }
    }

    std::size_t size() const {
        return _values.size();
    }

    bool empty() const {
        return _values.empty();
    }

    const T& min() const {
        assert(!empty());
        return _values[0];
    }

    const T& max() const {
        return _values[maximum_index()];
    }

    void clear() {
        _values.clear();
    }

    template <class... Args>
    void emplace(Args&&... args) {
        _values.emplace_back(std::forward<Args>(args)...);
        restore_after_push(_values.size() - 1);
    }

    void push(const T& value) {
        emplace(value);
    }

    void push(T&& value) {
        emplace(std::move(value));
    }

    void pop_min() {
        assert(!empty());
        if (_values.size() == 1) {
            _values.pop_back();
            return;
        }
        _values[0] = std::move(_values.back());
        _values.pop_back();
        trickle_down_min(0);
    }

    void pop_max() {
        assert(!empty());
        const std::size_t index = maximum_index();
        if (index == _values.size() - 1) {
            _values.pop_back();
            return;
        }
        _values[index] = std::move(_values.back());
        _values.pop_back();
        trickle_down_max(index);
    }

    const Compare& comparator() const {
        return _compare;
    }
};

template <class T, class Compare = std::less<T>>
using MinMaxHeap = DoubleEndedPriorityQueue<T, Compare>;

}  // namespace ds
}  // namespace m1une

Back to top page