如何跟蹤fifo查詢的最大/最小值

Question

我有fifo查詢，我放入和彈出雙精度。 每次更新後，我需要最大和最小值。我不需要查詢中這些值的位置（或索引）。 如何有效地做到這一點？日誌（N）或可能甚至O（1）？

UPD：發現這個Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations

Answer 1

這是一個棘手的問題。考慮以下內容：

假設您在任何給定時間的fifo大小爲N. 假設您只用一對浮點數跟蹤最小值和最大值。 說fifo的大小保持合理恆定。

因此，我們可以假設隊列上的一個「操作」在邏輯上由一個按鈕和一個彈出組成。

假設您比較了兩種處理方法：一種使用堆對，另一種使用天真的比較和搜索。

對於堆方法：

每個操作，你推到列表中，這兩種堆，然後從列表和堆都彈出。堆操作總是O（log（n）），列表操作是O（1），所以N很大時，一個操作的時間複雜度爲O（log（N））平均情況。請注意，無論當前彈出的元素是最小或最大元素，堆操作總是如此複雜。因此，N個操作的時間複雜度爲O（N * log（N））。

對於天真的方法：

每個操作，你推和彈出列表，並彈出的項目比較存儲的最小值和最大值。如果該項目與任一項目相同，則可以在列表中搜索具有相同值的項目（在這種情況下，您提前中斷），或者搜索列表的其餘部分，直到找到下一個最佳元素。然後用次優更新最小/最大值。該方法具有O（1）典型情況和O（N）最壞情況（最小或最大需要更新）。需要注意的是，對於某些範圍的N個數字，您需要更新最小值和最大值的次數將變爲常數，並且您不會達到N的次數。因此，N個操作的時間複雜度爲上）。天真的案例實際上比更先進的解決方案更好。

這就是說，我不認爲堆可以有效地移除元素，所以你會遇到很多麻煩。

因此，考慮下面的僞代碼：

queue fifo; 
float min, max; 

void push(float f) 
{ 
    if (fifo.size == 0) 
    { 
     min = f; 
     max = f; 
    } 
    else if (f > max) max = f; 
    else if (f < min) min = f; 

    fifo.push(f); 
} 

float pop() 
{ 
    if (fifo.size == 0) return (*((float *)NULL)); // explode 
    float f = fifo.pop(); 
    if (fifo.size == 0) 
    { 
     min = NaN; 
     max = NaN; 
     return f; 
    } 
    if (f == max) search_max(fifo); 
    if (f == min) search_min(fifo); 
    return f; 
} 

search_max(queue q) 
{ 
    float f = min; 
    for (element in q) 
    { 
     if (element == max) return; 
     if (element > f) f = element; 
    } 
    max = f; 
} 

search_min(queue q) 
{ 
    float f = max; 
    for (element in q) 
    { 
     if (element == min) return; 
     if (element < f) f = element; 
    } 
    min = f; 
} 

Answer 2

如何使用堆（http://en.wikipedia.org/wiki/Heap_%28data_structure%29）。你可以有兩堆。一個用於提取最小值和一個最大值（因爲單個堆不能同時提取最小值和最大值）。它也不需要任何空間開銷，並且Big O是log n。