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

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

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

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

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

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

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

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

为了向左推进，我们制作了一个大小为 1 的树，然后将其合并，直到恢复不变量。所需的时间是 O(1)，按与二进制数加 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("%dn", *value);
      } else {
        puts("null");
      }
      break;
    }
    case 3: {
      if (auto value = queue.ExtractMax()) {
        printf("%dn", *value);
      } else {
        puts("null");
      }
      break;
    }
    }
  }
}

• @EmmaNic. B beats D and is achievable at least two ways using data structures and techniques that appear in CLRS. You could keep a doubly linked list and a heap with pointers between corresponding nodes in each and then cascade the deletion (list determines which element is the tail, cascading delete from heap; heap determines which element is the min, cascading delete from list). You could also augment a regular balanced binary tree (*not* a search tree). Honestly I think this question is way too hard for an interview, and if it were forced on me, I wouldn't downgrade anyone for picking B.