algorithm - 支持提取最小值的队列的最佳时间复杂度是多少？

Question

我遇到了以下非常困难的面试问题：

考虑具有三个操作的队列数据结构：

- Add into the front of list (be careful front of list)

- Delete from Tail of the list (end of the list)

- Extract Min (remove)

这种数据结构的最佳实现具有摊销时间：

A) O(1) 的三个操作

B) O(log n) 的三个操作

C) 在 O(1) 中添加和删除，在 O(log n) 中提取最小

D) 在 O(log n) 中添加和删除，在 O(n) 中提取最小

面试后我看到（C）是正确的答案。为什么会这样？

第一个挑战是比较选项：哪个选项比其他选项更好，我们如何理解最终正确的选项？

标签： algorithmdata-structures

Answer 1

在给定的运行时间中，A 比 C 快 比 B 比 D 快。

A 在基于比较的数据结构中是不可能的（此处未说明的规范），因为它会违反已知的比较排序的 Ω(n log n) 时间下限，因为它允许插入 n 个元素然后提取的线性时间排序算法最少 n 次。

C 可以使用增强的手指树来完成。手指树支持分摊常数时间内的类似队列的推送和弹出，并且可以使用其子树中的最小值来扩充每个节点。为了提取最小值，我们使用增强来找到树中的最小值，其深度为 O(log n)。然后我们通过发出两个拆分和一个附加来提取这个最小值，所有这些都在摊销时间 O(log n) 内运行。

另一种可能性是将序列表示为一个展开树，其节点由 subtree min 增加。Push 和 pop 是由动态手指定理摊销的 O(1)。

斐波那契堆在没有进一步检查的情况下不会完成相同的时间限制，因为无论删除的元素是否是最小值，删除成本 Θ(log n) 都会摊销。

由于 C 是可行的，因此无需考虑 B 或 D。

---

鉴于数据结构的限制，我们实际上不需要手指树的全部功能。下面的 C++ 通过维护一个获胜者树列表来工作，其中每棵树的大小都是 2 的幂（忽略删除，我们可以将其实现为软删除，而不会破坏摊销的运行时间）。树的大小先增大后减小，有 O(log n) 个。这给了手指树的味道，实现的麻烦要少得多。

为了向左推，我们制作一棵大小为 1 的树，然后将其合并，直到恢复不变量。所需时间为 O(1)，按与将二进制数加一相同的逻辑摊销。

要在右侧弹出，我们拆分最右边的获胜者树，直到找到一个元素。这可能需要一段时间，但我们可以将其全部计入相应的推送操作。

要提取最大值（为方便起见，从 min 更改，因为 nullopt 是负无穷大，而不是正无穷大），找到包含最大值的获胜者树（O(log n)，因为有 O(log n) 树），然后软删除最大值从那棵获胜者树（O（log n），因为那是那棵树的高度）。

#include <stdio.h>
#include <stdlib.h>

#include <list>
#include <optional>

class Node {
public:
  using List = std::list<Node *>;
  virtual ~Node() = default;
  virtual int Rank() const = 0;
  virtual std::optional<int> Max() const = 0;
  virtual void RemoveMax() = 0;
  virtual std::optional<int> PopRight(List &nodes, List::iterator position) = 0;
};

class Leaf : public Node {
public:
  explicit Leaf(int value) : value_(value) {}
  int Rank() const override { return 0; }
  std::optional<int> Max() const override { return value_; }
  void RemoveMax() override { value_ = std::nullopt; }
  std::optional<int> PopRight(List &nodes, List::iterator position) override {
    nodes.erase(position);
    return value_;
  }

private:
  std::optional<int> value_;
};

class Branch : public Node {
public:
  Branch(Node *left, Node *right)
      : left_(left), right_(right),
        rank_(std::max(left->Rank(), right->Rank()) + 1) {
    UpdateMax();
  }

  int Rank() const override { return rank_; }

  std::optional<int> Max() const override { return max_; }

  void RemoveMax() override {
    if (left_->Max() == max_) {
      left_->RemoveMax();
    } else {
      right_->RemoveMax();
    }
    UpdateMax();
  }

  std::optional<int> PopRight(List &nodes, List::iterator position) override {
    nodes.insert(position, left_);
    auto right_position = nodes.insert(position, right_);
    nodes.erase(position);
    return right_->PopRight(nodes, right_position);
  }

private:
  void UpdateMax() { max_ = std::max(left_->Max(), right_->Max()); }

  Node *left_;
  Node *right_;
  int rank_;
  std::optional<int> max_;
};

class Queue {
public:
  void PushLeft(int value) {
    Node *first = new Leaf(value);
    while (!nodes_.empty() && first->Rank() == nodes_.front()->Rank()) {
      first = new Branch(first, nodes_.front());
      nodes_.pop_front();
    }
    nodes_.insert(nodes_.begin(), first);
  }

  std::optional<int> PopRight() {
    while (!nodes_.empty()) {
      auto last = --nodes_.end();
      if (auto value = (*last)->PopRight(nodes_, last)) {
        return value;
      }
    }
    return std::nullopt;
  }

  std::optional<int> ExtractMax() {
    std::optional<int> max = std::nullopt;
    for (Node *node : nodes_) {
      max = std::max(max, node->Max());
    }
    for (Node *node : nodes_) {
      if (node->Max() == max) {
        node->RemoveMax();
        break;
      }
    }
    return max;
  }

private:
  std::list<Node *> nodes_;
};

int main() {
  Queue queue;
  int choice;
  while (scanf("%d", &choice) == 1) {
    switch (choice) {
    case 1: {
      int value;
      if (scanf("%d", &value) != 1) {
        return EXIT_FAILURE;
      }
      queue.PushLeft(value);
      break;
    }
    case 2: {
      if (auto value = queue.PopRight()) {
        printf("%d\n", *value);
      } else {
        puts("null");
      }
      break;
    }
    case 3: {
      if (auto value = queue.ExtractMax()) {
        printf("%d\n", *value);
      } else {
        puts("null");
      }
      break;
    }
    }
  }
}