Abstract
優先等級佇列(priority queue)是一種具有大小順序的資料結構。它包括了下列運算尋找最小值 (FindMin)、刪除最小值 (DeleteMin)、加入新值(Insert)；同樣地，我們也可以定義一個優先等級佇列具有尋找最大值 (FindMax)、刪除最大值(DeleteMax) 的運算。很多種方法已經被提出來實際運作優先等級佇列。最為大家所熟悉的為“堆疊”(heap)。一種新的資料結構，“雙向優先等級佇列”(Double-ended priority queue) 是同時具有找最大、最小值，刪除最大、最小值的運算。目前被提出來實際運作此雙向優先等級佇列的方法包括了Min-Max heap和deap。Deap是一個二元樹binary tree)並且具有下列性質：(1) 根節點不存任何資料；(2) 左子樹具有由小到大順序，右子樹具有由大小到順序；(3) 左子樹的大小比右子樹的大小大 1或是兩者相等；(4) 所有樹葉節點的值均比其對應樹葉節點小。假如一個deap所有的機節節點均在同一層，我們稱其為完全的 (perfect)；否則我們稱其為不完全的 (non-perfect)。在本篇論文中，我們所要討論的是有關deap這種資料結構的合併問題。我們將輸入的兩個deap分為完全與不完全來探討；如此就有四種情況。我們分下列四種情況來探討deap的合併方法：(1) 兩個完全並且大小相等的deap的合併方法：(2) 兩個完全並且大小不相等的deap的合併方法。(3) 一個完全和一個不完全的deap的合併方法。(4) 兩個不完全的deap的合併方法。我們以第一種情況為基礎，完成此情況的合併方法再適當的應用到其它三種情況。如此便可有效的完成deap的合併工作。