使用 Swift 實作基於堆積的優先權佇列 大幅改善演算法的時間複雜度


本篇原文(標題:Implementing a Heap Based Priority Queue Using Swift)刊登於作者 Medium,由 Jimmy M Andersson 所著,並授權翻譯及轉載。

電腦科學中存在著許多問題,而其中,使用優先權佇列 (Priority Queue) 作為底層資料結構,就可以大幅改善演算法 (algorithm) 的時間複雜度。其中一個例子就是 Dijkstra 的最短路徑演算法,該演算法就使用優先權佇列在圖形中搜尋兩個頂點之間的最短路徑。

但不幸的是,Swift 標準函式庫並沒有包含優先權佇列的實作,因此我們將深入了解如何自己實現基於堆積 (heap) 的優先權佇列吧!

為了讓你可以跟著教學操作,你可以從 Github 下載原始程式碼!

甚麼是優先權佇列 (Priority Queue) ?

優先權佇列是一種資料結構,讓物件可以有效率地透過相對優先權來排序,你可以把一堆物件丟到佇列之中,然後佇列會依照物件的重要性一個個排好。

假設你為電腦創建了一堆任務,準備在將來某個特定的時間點執行。如果你將這些任務加到一個優先權佇列之中,你的電腦就會依照優先順序將任務從佇列中取出,以在截止時間前執行。

為了實現我們自己的佇列,我們將會使用堆積的結構!

甚麼是堆積 (Heap) ?

堆積的結構就像是一棵樹,而每個節點 (node) 最多只能擁有兩個子節點。而且堆積有個限制,就是新的節點必須加到結構頂層,並且盡可能在最左邊的位置,可以看看下方的示意圖:

同時,堆積也根據每個節點的大小來維持相對的屬性,最小堆積(Min heap,我們將會用到的那種堆積)會維持每個節點都會小於兩個子節點的相對關係,而最大堆積 (Max heap) 則相反。

為了維持這種特性,我們需要執行一些操作來獲得節點的正確順序。當我們插入一個新節點,我們會將它放到結構頂層從左邊數來第一個空的位置。如果加入新節點之後,違反了最小堆積的特性,我們就會開始將節點與其父節點交換,直到重新符合最小堆積的特性,下圖就展示了將數字 2 插入一個已有的最小堆積會是甚麼情況:

algorithm-2

當從佇列中取出(或稱為移除)一個物件時,我們會限制自己只可從佇列的某一端來做這個動作。我們會以一種只能刪除根元素的方式來實現這一點,刪除該元素後,它將被我們樹頂層最右邊的元素取代。由於新元素幾乎肯定會因為太大而無法保留在根中,我們會將它向下移動,與最小的子元素交換,直到我們恢復最小堆積的特性。

關於實作的細節

我們將會使用陣列 (array),以快速又節省空間地實現樹結構。我將不會在這裡探討太多關於數學的細節,若你有興趣的話,可以參考維基百科的說明,網頁詳細解釋了實作的流程和機制。

準備好了嗎?那我們就開始吧!

設計協定 (Protocol)

一如以往,我們需要先定義物件該向外部使用者展現甚麼樣的功能,要達到這個目的,我們要宣告類別之後會遵循的一個協定。對於我們的佇列,我會宣告下列的 Queue 協定:

這個協定明確的指出我們將要實現的佇列中,外部使用者所預期會有甚麼功能。協定同時也顯示了其中一個方法會拋出錯誤,並且有標註出這個錯誤是屬於 QueueError 型別,所以我們也需要實現它!

這個錯誤的定義很簡潔,當使用者嘗試從空的佇列中移除一個項目時,我們就會拋出這個錯誤。

現在準備工作都完成了,讓我們回到佇列本身吧!

實作優先權佇列

我們首先要宣告 PriorityQueue 類別,並實作初始化器 (initializer)、後端儲存 (backing storage)、以及一些實用的方法。程式碼看起來會是這樣子的:

你可能會注意到,在這裡我們還沒有將 Queue 協定加進來。通常在規劃程式碼的時候,我們會希望每個部份能夠保持獨立,保持綜觀的架構,以便瞭解所要找尋的部分在哪裡。當一個類別越來越大,其中一個解決方法就是透過擴展的方式來實現類別。如此一來,每個擴展都能夠專注在一個任務上(像是遵循一個協定、處理後端儲存與初始化、或是宣告巢狀類別 (nested class)),這樣你就能夠輕易找到想要的部份。讓我們現在就來試試吧!首先,實作一個私有的 Int 擴展,為我們執行一些預先定義好的索引值計算 (index calculation):

由於前面加上了 private 存取控制關鍵字,這個擴展只能夠在我們的 PriorityQueue 檔案內部做使用。這個擴展主要的功能就是收集一些計算,以用於在特定節點獲取其子節點、父節點。這樣一來,我們就不必在實作中做一堆數學運算,而是可以透過呼叫 .leftChild 屬性來回傳左子節點的對應索引值,如此類推。

讓我們繼續加入遵循 Queue 協定的部分吧!這看起來會是這樣:

這個部份的程式碼比較多,所以你可能要多看幾次。最上面的,就是我們一開始定義的所有協定方法,而下方就是一些私有幫助方法,而它們只能在這個特定的類別中使用。我在註解中說明了每個方法,讓你閱讀時更了解它們的作用。另外,你也可以看看我們如何使用 Int 擴展,這是一個相當簡潔的功能。

總結

好了,以上這些就是 PriorityQueue 所需要的全部功能。我們可以額外再讓類別遵循 CustomStringConvertible 協定,這樣一來佇列就可以傳入 print 函式,並回傳一些可閱讀的資訊:

完成了!這次的教學就到這裡,現在你已經瞭解如何實作基於堆積結構的優先權佇列!如果有任何問題或意見,歡迎在下面留言。

如果想看更多關於 iOS 開發的文章,可以看看我的其他文章:

本篇原文(標題:Implementing a Heap Based Priority Queue Using Swift)刊登於作者 Medium,由 Jimmy M Andersson 所著,並授權翻譯及轉載。
作者簡介:Jimmy M Andersson 是一名軟件開發人員,在活躍於汽車行業的 NIRA Dynamics 中負責數據採集。他開發了監控和日誌記錄 App,來演示及可視化公司的產品組合和其功能。他目前正在進修資訊科技碩士學位,目標是以數據科學專業畢業。他每週都會在 Medium 發表軟件開發文章。你也可以在 Twitter Email 聯絡他。
譯者簡介:HengJay,iOS 初學者,閒暇之餘習慣透過線上 MOOC 資源學習新的技術,喜歡 Swift 平易近人的語法也喜歡狗狗,目前參與生醫領域相關應用的 App 開發,希望分享文章的同時也能持續精進自己的基礎。

LinkedIn: https://www.linkedin.com/in/hengjiewang/
Facebook: https://www.facebook.com/hengjie.wang

原文Implementing a Heap Based Priority Queue Using Swift


此文章為客座或轉載文章,由作者授權刊登,AppCoda編輯團隊編輯。有關文章詳情,請參考文首或文末的簡介。

blog comments powered by Disqus
訂閲電子報

訂閲電子報

AppCoda致力於發佈優質iOS程式教學,你不必每天上站,輸入你的電子郵件地址訂閱網站的最新教學文章。每當有新文章發佈,我們會使用電子郵件通知你。

已收你的指示。請你檢查你的電郵,我們已寄出一封認證信,點擊信中鏈結才算完成訂閱。

Shares
Share This