D 分ヒープ

#pragma once
#include <functional>
#include <utility>
#include <vector>

/// @brief D 分ヒープ
/// @details 順序基準の `Key` と付随データ `Value` を保持し、`Comp` で `Key` を比較する。
///          `Comp = std::greater<>` で `Key` 最小をルートにする最小ヒープになる
///          （`binary_heap` / `fibonacci_heap` と同じ規約）。
///          連続領域（`std::vector`）に `{key, value}` を並べる flat 実装。
///          decrease-key は持たない。
/// @tparam Key 順序基準。`Comp` で比較される側。
/// @tparam Value 付随データ。順序には関与しない。
/// @tparam Comp `Key` の比較子。
/// @tparam D 分岐数（既定 4）。二分ヒープより木が浅く（log_D N）、`pop` の
///           sift-down で子をまとめて見るため比較回数が増えるトレードオフがある。
/// @note 当環境のベンチでは Dijkstra 用途で `std::priority_queue` と概ね互角だった
///       （明確な速度優位は確認できなかった）。`binary_heap` と並ぶ汎用ヒープとして提供する。
template <class Key, class Value, class Comp = std::less<>, int D = 4>
struct dary_heap {
    static_assert(D >= 2, "D must be >= 2");

  private:
    struct _node {
        Key key;
        Value value;
    };

  public:
    /// @brief 空のD分ヒープを構築する
    /// @complexity $O(1)$
    dary_heap() : data(), comp() {}

    /// @brief 空か返す
    /// @complexity $O(1)$
    constexpr bool empty() const { return data.empty(); }

    /// @brief 要素数を返す
    /// @complexity $O(1)$
    constexpr int size() const { return (int)data.size(); }

    /// @brief 最上位のkeyとvalueを返す
    /// @complexity $O(1)$
    std::pair<Key, Value> top() const { return {data[0].key, data[0].value}; }

    /// @brief 要素を追加する
    /// @complexity $O(\log_D n)$
    void push(Key key, Value value) {
        data.push_back({std::move(key), std::move(value)});
        int index = (int)data.size() - 1;
        // sift-up: 親より「上に来るべき」なら入れ替える。
        while (index > 0) {
            int parent = (index - 1) / D;
            if (!comp(data[parent].key, data[index].key)) break;
            std::swap(data[parent], data[index]);
            index = parent;
        }
    }
    /// @brief 要素を追加する
    /// @complexity $O(\log_D n)$
    void emplace(Key key, Value value) { push(std::move(key), std::move(value)); }

    /// @brief 最上位の要素を削除する
    /// @complexity $O(D\log_D n)$
    void pop() {
        data[0] = std::move(data.back());
        data.pop_back();
        int index = 0, n = (int)data.size();
        // sift-down: 子のうち「最も上に来るべき」ものと入れ替える。
        while (true) {
            int first = D * index + 1;
            if (first >= n) break;
            int best = first;
            for (int k = first + 1; k < first + D && k < n; ++k) {
                if (comp(data[best].key, data[k].key)) best = k;
            }
            if (!comp(data[index].key, data[best].key)) break;
            std::swap(data[index], data[best]);
            index = best;
        }
    }

  private:
    // 連続領域に {key, value} を並べる flat 実装。比較は key で行う。
    std::vector<_node> data;
    Comp comp;
};

/// @brief 4 分ヒープ（`dary_heap` の D=4 固定エイリアス）
/// @details `template <class...> class` 形式（型パラメータのみ）にすることで、
///          `shortest_path<quaternary_heap>` のように template-template 引数として渡せる。
/// @complexity 型別名であり実行時計算量はない
template <class Key, class Value, class Comp = std::less<>>
using quaternary_heap = dary_heap<Key, Value, Comp, 4>;

bundled

#line 2 "lib/heap/dary_heap.hpp"
#include <functional>
#include <utility>
#include <vector>

/// @brief D 分ヒープ
/// @details 順序基準の `Key` と付随データ `Value` を保持し、`Comp` で `Key` を比較する。
///          `Comp = std::greater<>` で `Key` 最小をルートにする最小ヒープになる
///          （`binary_heap` / `fibonacci_heap` と同じ規約）。
///          連続領域（`std::vector`）に `{key, value}` を並べる flat 実装。
///          decrease-key は持たない。
/// @tparam Key 順序基準。`Comp` で比較される側。
/// @tparam Value 付随データ。順序には関与しない。
/// @tparam Comp `Key` の比較子。
/// @tparam D 分岐数（既定 4）。二分ヒープより木が浅く（log_D N）、`pop` の
///           sift-down で子をまとめて見るため比較回数が増えるトレードオフがある。
/// @note 当環境のベンチでは Dijkstra 用途で `std::priority_queue` と概ね互角だった
///       （明確な速度優位は確認できなかった）。`binary_heap` と並ぶ汎用ヒープとして提供する。
template <class Key, class Value, class Comp = std::less<>, int D = 4>
struct dary_heap {
    static_assert(D >= 2, "D must be >= 2");

  private:
    struct _node {
        Key key;
        Value value;
    };

  public:
    /// @brief 空のD分ヒープを構築する
    /// @complexity $O(1)$
    dary_heap() : data(), comp() {}

    /// @brief 空か返す
    /// @complexity $O(1)$
    constexpr bool empty() const { return data.empty(); }

    /// @brief 要素数を返す
    /// @complexity $O(1)$
    constexpr int size() const { return (int)data.size(); }

    /// @brief 最上位のkeyとvalueを返す
    /// @complexity $O(1)$
    std::pair<Key, Value> top() const { return {data[0].key, data[0].value}; }

    /// @brief 要素を追加する
    /// @complexity $O(\log_D n)$
    void push(Key key, Value value) {
        data.push_back({std::move(key), std::move(value)});
        int index = (int)data.size() - 1;
        // sift-up: 親より「上に来るべき」なら入れ替える。
        while (index > 0) {
            int parent = (index - 1) / D;
            if (!comp(data[parent].key, data[index].key)) break;
            std::swap(data[parent], data[index]);
            index = parent;
        }
    }
    /// @brief 要素を追加する
    /// @complexity $O(\log_D n)$
    void emplace(Key key, Value value) { push(std::move(key), std::move(value)); }

    /// @brief 最上位の要素を削除する
    /// @complexity $O(D\log_D n)$
    void pop() {
        data[0] = std::move(data.back());
        data.pop_back();
        int index = 0, n = (int)data.size();
        // sift-down: 子のうち「最も上に来るべき」ものと入れ替える。
        while (true) {
            int first = D * index + 1;
            if (first >= n) break;
            int best = first;
            for (int k = first + 1; k < first + D && k < n; ++k) {
                if (comp(data[best].key, data[k].key)) best = k;
            }
            if (!comp(data[index].key, data[best].key)) break;
            std::swap(data[index], data[best]);
            index = best;
        }
    }

  private:
    // 連続領域に {key, value} を並べる flat 実装。比較は key で行う。
    std::vector<_node> data;
    Comp comp;
};

/// @brief 4 分ヒープ（`dary_heap` の D=4 固定エイリアス）
/// @details `template <class...> class` 形式（型パラメータのみ）にすることで、
///          `shortest_path<quaternary_heap>` のように template-template 引数として渡せる。
/// @complexity 型別名であり実行時計算量はない
template <class Key, class Value, class Comp = std::less<>>
using quaternary_heap = dary_heap<Key, Value, Comp, 4>;