我遇到過這樣的問題：用 push(x)、pop() 和pop_max()方法實作一個佇列。
pop_max() 函式應該按照 FIFO 規則彈出最大的元素。
例如：在 pop_max() 之前：front-> 2,3,4,5,1,5
在 pop_max() 之后：front-> 2,3,4,1,5
下面是我的一些嘗試。
使用基本佇列實作它，使用支持佇列通過 O(n) 掃描找到最大元素。
pop()/push() 是 O(1)，pop_max() 應該是 O(n)。
用一個雙鏈表和一個單調堆疊來實作它。
pop()/pop_max() 是 O(1)，push() 應該是 O(n)。
有人知道以最小的時間復雜度做到這一點的方法是什么？我讀過這個實作一個佇列，其中 push_rear()、pop_front() 和 get_min() 都是常量時間操作，它提供的方法似乎不適合這種場景。
uj5u.com熱心網友回復：
首先讓我們爭論一個目標運行時間。我們可以使用這種抽象資料型別對 n 個元素串列進行排序，其中 n 個推送，然后是 n 個 pop-max。假設通用的可比較元素，由于最快的比較排序是 Θ(n log n)，最壞情況的 push/pop-max 對必須是 Ω(log n)。
在下面的 C 中實作了為所有三個操作獲得 O(log n) 最壞情況的一種方法。通過攤銷記賬，我們可以使推送 O(log n) 和 pops 和 pop-maxes 免費。
這確實留下了一個問題，即我們是否可以獲得最壞情況下的 O(1) 次推送、O(1) 次彈出和 O(log n) 次彈出最大值。我相信答案是肯定的，但我想到的解決方案相當復雜，包括在佇列的各個段上定期維護 O(log n) 錦標賽樹，其大小呈幾何級數減小。
#include <list>
#include <map>
template <typename T> class QueueWithPopMax {
public:
void Push(T element) {
typename std::list<ListElement>::iterator back =
list_.insert(list_.end(), ListElement{});
back->iterator = multimap_.insert({element, back});
}
T Pop() {
T element = list_.front().iterator->first;
multimap_.erase(list_.front().iterator);
list_.pop_front();
return element;
}
T PopMax() {
T element = multimap_.begin()->first;
list_.erase(multimap_.begin()->second);
multimap_.erase(multimap_.begin());
return element;
}
private:
struct ListElement {
typename std::multimap<T, typename std::list<ListElement>::iterator,
std::greater<T>>::iterator iterator;
};
std::multimap<T, typename std::list<ListElement>::iterator, std::greater<T>>
multimap_;
std::list<ListElement> list_;
};
#include <iostream>
int main() {
QueueWithPopMax<int> queue;
queue.Push(2);
queue.Push(3);
queue.Push(4);
queue.Push(5);
queue.Push(1);
queue.Push(5);
std::cout << queue.PopMax() << "\n";
std::cout << queue.Pop() << "\n";
std::cout << queue.Pop() << "\n";
std::cout << queue.Pop() << "\n";
std::cout << queue.Pop() << "\n";
std::cout << queue.Pop() << "\n";
}
uj5u.com熱心網友回復：
根據要求，這里有一個有點詳細的答案，說明為什么我相信有一個解決方案，最壞情況是 O(1) 推送和彈出以及 O(log n) 彈出最大值。這太復雜了，你不需要在面試中理解它。真的。我寫這個答案主要是為了娛樂 [algorithm] 標簽常客。
變數
n 是結構中當前的元素數，p 是結構生命周期中的推送次數。顯然 n ≤ p，并且通常情況下，log p 不是 O(log n)。
比賽樹
主要構建塊是錦標賽樹。錦標賽樹是一棵完整的二叉樹（每個節點有零個或兩個子節點），帶有標記的節點，這樣每個帶有標記為 x 和 y 的子節點的每個節點都被標記為 max(x, y)。從語意上講，該資料結構的內容是具有零個子節點（葉子）的節點的標簽。如果您感到困惑，請查看單淘汰賽的完整組別。
錦標賽樹的有用之處在于我們可以按照我們想要的任何方式對葉子進行排序。對于這個問題，我們需要佇列順序。根元素給出了整體的最大標簽。要找到帶有該標簽的最左邊的葉子，如果它的標簽與當前節點相同，則重復下降到左子節點，否則為右節點。要軟洗掉葉子，請將其值設定為 -∞ 并將其祖先從父級更新為根。
攤銷 O(1) 次推送和最壞情況 O(log p) pop-max
在實踐中有更好的方法來實作這一點，但我們在這里的目標是展示想法。
我們保留一個 O(log p) 錦標賽樹的鏈表。連接起來，它們的葉子代表佇列。對于某個整數 k ≥ 0，每棵樹都是一個完整的二叉樹，有 2 k 個葉子（軟洗掉元素包括在計數中）。
推送操作類似于向二進制表示的數字加一。我們將新元素單獨放入錦標賽樹中，并將該樹附加到串列中。雖然串列中的最后兩棵樹具有相同的大小，但通過將倒數第二個作為新樹的左子樹和最后一個右子樹，將它們組合成一棵樹。
pop-max 操作掃描樹根以找到整體最大值，然后軟洗掉最左邊的出現。
最壞情況 O(1) 推送
我們可以更懶惰地合并樹。我們沒有立即完成合并回圈，而是保留一個延續佇列。每個延續都可以表示為指向串列中一棵樹的可變指標。為了步進，我們將樹的大小與其左鄰居的大小進行比較；如果它們相同，則合并樹并更新指向合并樹的指標。否則，繼續進行。
push 操作附加一個單例樹，將指向該樹的延續附加到佇列的后面，然后繼續前面的作業幾步。在任何給定時間，都會有 O(log p) 次合并要繼續，因此 pop-max 仍然運行得足夠快。（這是根據攤銷分析得出的。）
定期流行音樂
我們可以通過向尚未洗掉的錦標賽樹葉添加雙向鏈表結構，在最壞情況時間 O(log p) 中實作彈出操作。比賽使用軟洗掉；此串列使用硬洗掉。
顯然，我們希望 pops 在恒定時間內運行。我們可以通過在軟洗掉之前拆分最左邊的錦標賽樹直到它有一個元素來獲得恒定的 分攤時間（使用某種障礙來確保之前的合并延續保留這個前綴）。
最壞情況下的恒定時間應該可以通過更多的調度來實作，就像我們為推送所做的那樣。
最壞情況 O(log n) pop-maxes
Never mind hand-waving, at this point it’s basically my whole arms. Our strategy is to limit the effective value of p to O(n) by periodically rebuilding the whole structure in the background. This means issuing pop operations to the rebuild and remembering how far we are in the rebuild so that we can issue pop-maxes if needed. Assuming that we do multiple pushes on the rebuild with every operation, we’ll finish before pops and pop-maxes can decrease the element count by more than a constant fraction.
Open questions
I’m sure that there’s a cleaner way to accomplish all this. What is it?
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/325969.html