Hu-Tucker Algorithm
(dp/hu_tucker.hpp)

• View this file on GitHub
• Last update: 2024-01-08 01:32:22+09:00
• Include: #include "dp/hu_tucker.hpp"

Description

Hu-Tucker のアルゴリズムは，最適二分探索木問題を高速に解くアルゴリズムである．

正当性の証明は難しいらしい．

Operations

• T hu_tucker(vector<T> w)
  • 各頂点の重み $w_i$ が与えられたとき，最適二分探索木の重みを求める．
  • 時間計算量: $O(n\log n)$

Reference

• C - 最適二分探索木

Depends on

• Leftist Heap (data-structure/leftist_heap.hpp)

Verified with

• test/aoj/2415.test.cpp

Code

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

#include "../data-structure/leftist_heap.hpp"

template <typename T>
T hu_tucker(std::vector<T> w) {
    const int n = w.size();
    const T INF = std::numeric_limits<T>::max() / 2;
    std::vector<LeftistHeap<T>> heaps(n - 1);  // interior nodes in each group
    std::vector<int> left(n), right(n);
    std::vector<T> cs(n - 1);
    using P = std::pair<T, int>;
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
    for (int i = 0; i < n - 1; ++i) {
        left[i] = i - 1;
        right[i] = i + 1;
        cs[i] = w[i] + w[i + 1];
        pq.emplace(cs[i], i);
    }
    T ret = 0;
    for (int k = 0; k < n - 1; ++k) {
        T c;
        int i;
        // find the optimal nodes to merge
        do {
            std::tie(c, i) = pq.top();
            pq.pop();
        } while (right[i] == -1 || cs[i] != c);

        bool merge_l = false, merge_r = false;
        if (w[i] + w[right[i]] == c) {  // lr
            merge_l = merge_r = true;
        } else {
            T top = heaps[i].top().second;
            heaps[i].pop();
            if (w[i] + top == c) {  // lm
                merge_l = true;
            } else if (top + w[right[i]] == c) {  // mr
                merge_r = true;
            } else {  // mm
                heaps[i].pop();
            }
        }
        ret += c;
        heaps[i].push(-1, c);
        if (merge_l) {
            w[i] = INF;
        }
        if (merge_r) {
            w[right[i]] = INF;
        }

        // merge left
        if (merge_l && i > 0) {
            int j = left[i];
            heaps[j] =
                LeftistHeap<T>::meld(std::move(heaps[j]), std::move(heaps[i]));
            right[j] = right[i];
            right[i] = -1;
            left[right[j]] = j;
            i = j;
        }
        // merge right
        if (merge_r && right[i] < n - 1) {
            int j = right[i];
            heaps[i] =
                LeftistHeap<T>::meld(std::move(heaps[i]), std::move(heaps[j]));
            right[i] = right[j];
            right[j] = -1;
            left[right[i]] = i;
        }

        cs[i] = w[i] + w[right[i]];  // lr
        if (!heaps[i].empty()) {
            T top = heaps[i].top().second;
            heaps[i].pop();
            cs[i] =
                std::min(cs[i], std::min(w[i], w[right[i]]) + top);  // lm or mr
            if (!heaps[i].empty()) {
                cs[i] = std::min(cs[i], top + heaps[i].top().second);  // mm
            }
            heaps[i].push(-1, top);
        }
        pq.emplace(cs[i], i);
    }
    return ret;
}

#line 2 "dp/hu_tucker.hpp"
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

#line 2 "data-structure/leftist_heap.hpp"
#include <algorithm>
#include <memory>
#line 5 "data-structure/leftist_heap.hpp"

template <typename T>
class LeftistHeap {
   public:
    LeftistHeap() = default;

    static LeftistHeap meld(LeftistHeap a, LeftistHeap b) {
        return LeftistHeap(meld(std::move(a.root), std::move(b.root)));
    }

    std::pair<int, T> top() const {
        push(root);
        return {root->id, root->val};
    }

    void pop() {
        push(root);
        root = meld(std::move(root->left), std::move(root->right));
    }

    void push(int id, T x) {
        root = meld(std::move(root), std::make_unique<Node>(id, x));
    }

    bool empty() const { return root == nullptr; }

    void add(T x) { root->lazy += x; }

   private:
    struct Node;
    using node_ptr = std::unique_ptr<Node>;

    struct Node {
        node_ptr left, right;
        int s;
        int id;
        T val, lazy;
        Node(int id, T x) : id(id), val(x), lazy(0) {}
    };

    node_ptr root = nullptr;

    explicit LeftistHeap(node_ptr root) : root(std::move(root)) {}

    static node_ptr meld(node_ptr a, node_ptr b) {
        if (!a) return b;
        if (!b) return a;
        push(a);
        push(b);
        if (a->val > b->val) std::swap(a, b);
        a->right = meld(std::move(a->right), std::move(b));
        if (!a->left || a->left->s < a->right->s) std::swap(a->left, a->right);
        a->s = (a->right ? a->right->s : 0) + 1;
        return a;
    }

    static void push(const node_ptr& t) {
        if (t->left) t->left->lazy += t->lazy;
        if (t->right) t->right->lazy += t->lazy;
        t->val += t->lazy;
        t->lazy = 0;
    }
};
#line 9 "dp/hu_tucker.hpp"

template <typename T>
T hu_tucker(std::vector<T> w) {
    const int n = w.size();
    const T INF = std::numeric_limits<T>::max() / 2;
    std::vector<LeftistHeap<T>> heaps(n - 1);  // interior nodes in each group
    std::vector<int> left(n), right(n);
    std::vector<T> cs(n - 1);
    using P = std::pair<T, int>;
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
    for (int i = 0; i < n - 1; ++i) {
        left[i] = i - 1;
        right[i] = i + 1;
        cs[i] = w[i] + w[i + 1];
        pq.emplace(cs[i], i);
    }
    T ret = 0;
    for (int k = 0; k < n - 1; ++k) {
        T c;
        int i;
        // find the optimal nodes to merge
        do {
            std::tie(c, i) = pq.top();
            pq.pop();
        } while (right[i] == -1 || cs[i] != c);

        bool merge_l = false, merge_r = false;
        if (w[i] + w[right[i]] == c) {  // lr
            merge_l = merge_r = true;
        } else {
            T top = heaps[i].top().second;
            heaps[i].pop();
            if (w[i] + top == c) {  // lm
                merge_l = true;
            } else if (top + w[right[i]] == c) {  // mr
                merge_r = true;
            } else {  // mm
                heaps[i].pop();
            }
        }
        ret += c;
        heaps[i].push(-1, c);
        if (merge_l) {
            w[i] = INF;
        }
        if (merge_r) {
            w[right[i]] = INF;
        }

        // merge left
        if (merge_l && i > 0) {
            int j = left[i];
            heaps[j] =
                LeftistHeap<T>::meld(std::move(heaps[j]), std::move(heaps[i]));
            right[j] = right[i];
            right[i] = -1;
            left[right[j]] = j;
            i = j;
        }
        // merge right
        if (merge_r && right[i] < n - 1) {
            int j = right[i];
            heaps[i] =
                LeftistHeap<T>::meld(std::move(heaps[i]), std::move(heaps[j]));
            right[i] = right[j];
            right[j] = -1;
            left[right[i]] = i;
        }

        cs[i] = w[i] + w[right[i]];  // lr
        if (!heaps[i].empty()) {
            T top = heaps[i].top().second;
            heaps[i].pop();
            cs[i] =
                std::min(cs[i], std::min(w[i], w[right[i]]) + top);  // lm or mr
            if (!heaps[i].empty()) {
                cs[i] = std::min(cs[i], top + heaps[i].top().second);  // mm
            }
            heaps[i].push(-1, top);
        }
        pq.emplace(cs[i], i);
    }
    return ret;
}

Back to top page