一千萬個為什麽

搜索
當前位置: 首頁 > 可拆分堆棧

可拆分堆棧

有哪些數據結構可以維護一系列受以下兩個操作影響的項目?

  • Push(x):將x添加到序列的末尾,並返回序列中其位置的標識符
  • 提取(S):給定一組無序標識符,從序列中刪除這些位置中的項目,並按順序返回已刪除項目的列表

如果您願意,可以將其視為堆棧或具有拆分操作的隊列,將其拆分為兩個堆棧:提取操作可​​用於實現pop或dequeue操作,並且提取的項目序列也可以放在再次回到不同的堆棧或隊列。

我已經知道的:可以將序列維護為雙向鏈表,其中每個標識符只是指向鏈表節點的指針,每個節點還存儲一個位置編號,允許快速比較兩個不相關元素的位置順序。隨著數據結構的進展,更新位置編號並不困難,因此它們都是最大值$ O(n)$的正整數,其中$ n $是列表中當前的項目數。使用此數據結構,提取操作中唯一困難的部分是按提取的項目的位置編號對其進行排序。例如,使用來自FOCS 2002的Han和Thorup的整數排序算法,$ k $項目的提取需要$ O(k \ sqrt {\ log \ log k})$預期隨機時間,並且推送操作需要恒定時間。

我不知道的是:是否可以在$ O(k)$時間內處理提取並推進恒定時間?有關於這個問題的文獻嗎?它和整數排序一樣難嗎?

動機:這是在Coffman-Graham調度算法中訂購項目所需的基本步驟,該算法在圖形繪制中也有應用。 Coffman-Graham的難點在於詞典拓撲排序。這可以通過為每個不同的indegree維護由剩余頂點引起的子圖中具有該indegree的頂點序列來完成。然後,重復從零indegree頂點序列中刪除第一個頂點$ v $並將其添加到拓撲順序;從他們之前所屬的度數中提取$ v $的鄰居,並將它們推送到下一個較小程度的序列中。因此,在此數據結構中提取操作的$ O(k)$時間將導致Coffman-Graham算法的線性時間實現。

自從最初問這個以來我發現了 Sethi從1976年開始的一篇論文,它允許Coffman-Graham算法在線性時間內實現,並將其包含在我的維基百科關於Coffman-Graham算法的文章中,因此原始動機較少有意義的。不過,我仍然很好奇答案是什麽。

最佳答案

我認為這至少和在$ n $中使用大小多項式的“隨機建議”排序一組整數$ S \ subseteq [n] $一樣困難。通過隨機的建議我的意思是,對於任何$ n $,在大小為poly($ n $)的字符串上有一個固定的分配$ {\ cal D} _n $(取決於僅$ n $上的)和我們的算法(由RAM機器建模)可以隨機訪問$ {\ cal D} _n $中的單個樣本。 $ {\ cal D} _n $是按順序推送$ [n] $之後的(隨機化)數據結構,以及將整數映射到預期$ O(1)$時間內的標識符的哈希表。

鑒於設置,對於整數排序問題的實例$ S \ subseteq [n] $,我們可以發出extract($ S $)(實際上我們需要$ S $的標識符,但是這個映射可以在$ O中完成( 1)使用作為建議一部分的哈希表的每個項目的$ time,並且輸入將在執行提取所花費的時間內進行排序。

因此,消息是,除非某些僅依賴於整數上限的“免費”輔助信息可以使整數排序更容易,否則提取與整數排序一樣難。

這是否意味著沒有奇怪模型的兩個問題之間的關系?這種隨機建議的概念是否已知?這有點像MA協議,但Merlin的信息不允許依賴於輸入,我們關心Arthur的運行時間。

轉載註明原文: 可拆分堆棧