Of the given running times, A is faster than C is faster than B is faster than D.
A is impossible in a comparison-based data structure (the unstated norm here) because it would violate the known Ω(n log n)-time lower bound for comparison sorts by allowing a linear-time sorting algorithm that inserts n elements and then extracts the min n times.
C can be accomplished using an augmented finger tree. Finger trees support queue-like push and pop in amortized constant time, and it's possible to augment each node with the minimum in its sub-tree. To extract the min, we use the augmentations to find the minimum value in the tree, which will be at depth O(log n). Then we extract this minimum by issuing two splits and an append, all of which run in amortized time O(log n).
Another possibility is to represent the sequence as a splay tree whose nodes are augmented by subtree min. Push and pop are O(1) amortized by the dynamic finger theorem.
Fibonacci heaps do not accomplish the same time bound without further examination because deletes cost Θ(log n) amortized regardless of whether the deleted element is the min.
Since C is feasible, there is no need to consider B or D.
Given the limitations on the data structure, we actually don't need the full power of finger trees. The C++ below works by maintaining a list of winner trees, where each tree has size a power of two (ignoring deletion, which we can implement as soft delete without blowing up the amortized running time). The sizes of the trees increase and then decrease, and there are O(log n) of them. This gives the flavor of finger trees with a much lesser implementation headache.
To push on the left, we make a size-1 tree and then merge it until the invariant is restored. The time required is O(1) amortized by the same logic as increasing a binary number by one.
To pop on the right, we split the rightmost winner tree until we find a single element. This may take a while, but we can charge it all to the corresponding push operations.
To extract the max (changed from min for convenience because nullopt is minus infinity, not plus infinity), find the winner tree containing the max (O(log n) since there are O(log n) trees) and then soft delete the max from that winner tree (O(log n) because that's the height of that tree).
#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;
}
}
}
}
