|
隨著電腦硬體技術的突飛猛進及高速計算的需求，一部擁有多個微處理機
的電腦或是分散式系統已從理論中的環境漸漸變為實際可行，而平行演算
法的重要性正因為它是在此種環境下發展軟體的基礎。本篇論文將在
PRAM (Parallel Random Access Machine) Model 下探討有關堆積(Heap)
結構上的一些運算。堆積(Heap)結構在演算法中佔有極為重要的角色，在
此結構中，無論是加入資料或是從結構內的資料中找尋極值的問題，基本
上它都提供了非常有效率的方法。因此，無論在圖形演算法，排序或搜尋
的問題上常常利用此一結構而達到高效率的演算法。故其重要性是不可忽
略的。在本篇論文中，我們將會探討數個運算的演算法並證明其執行時間
的理論下界(Lower bound)。假設在一個堆積 (Heap)中有n 個元素，對傳
統從堆積(Heap)中加入或刪除一個元素的運算而言，我們在 CREW 和
EREW PRAM上提出了執行時間分別為θ(1)和θ(loglogn)的演算法。除了
傳統的運算外，我們也討論如何從堆積(Heap)中同時加入 r個元素與刪除
其值落在某一個範圍 (l,u)內的元素。在堆積(Heap)中加入 r個元素的運
算中，我們提出了在 CREW PRAM 上執行時間為θ(logr) 的演算法並且其
成本(Cost)為 O(rlogr+logn)。針對刪除某個特殊範圍，也就是其值小
於 u，內的元素的運算，我們提出的演算法可以在θ(logr+loglogn)的時
間內完成，並且其成本(Cost)為 q(n)，其中r是將被刪除的元素並且 r
小於 n/logr。除此之外，我們在 CREW PRAM下證明了若針對一般範圍中
刪除元素的運算其執行時間的下界(Lower bound)是 Ω(logn)，這時間相
當於重建一個堆積 (Heap) 所花的時間。因此，我們只好在 CRCW PRAM
上討論此一運算了。在此環境下，我們提出一個時間為 O(logr+loglogn)
而其成本(Cost)為 θ(n)的演算法，其中 r 是將被刪除的元素並且 r 小
於 n/logr。
|