1–5 佇列 Queue
就像排隊一樣,新到的人(新增數據,enqueue)會排在隊伍的尾端,但處理(例如刪除數據,dequeue),則會從隊伍的頭開始。
有點類似堆疊,但我們可以從字面上的意思推敲出來,佇列的“新增數據”跟“刪除數據”是分別從一列數據的兩端來進行的。
就像排隊一樣,新到的人(新增數據,enqueue)會排在隊伍的尾端,但處理(例如刪除數據,dequeue)則會從隊伍的頭,也就是最早被加進這個佇列的資料開始進行。
與堆疊相反,佇列的這個概念稱為“先進先出” First In First Out。
這樣的資料結構可以被應用在廣度優先搜尋(4–2),之後會說明。
1–6 雜湊表 Hash Table
Hash Table可以用來儲存成對的數據,每一組數據是一個key and value pair。
例如:我們想要儲存每個人的電話號碼,key為人名,value為電話號碼。
為了瞭解hash table的優勢,我們先來看看同樣的成對數據,如果存在陣列中,會是什麼樣子。
假設我們想要知道資料中的Lisa Smith的電話號碼,在陣列中,因為我們不知道Lisa Smith在array中的index,所以得從array[0]開始,依序一個個搜索 ,直到找到key為Lisa Smith為止,才能得知相對應的電話號碼。這樣的搜尋方式稱為線性搜尋(3–1),資料量龐大時,是非常沒有效率的。
而hash table可以解決這個問題。
首先,我們得先決定,所有的資料要被大致分為幾組。
這裡的例子分為16組。也就是說,我們先準備一個長度為16的陣列用來儲存數據。
要存入一筆新的數據時,key得先通一個hash function,這個函式會回傳一個hash值,將hash值除以組數後得到的餘數,就是這個數據現在的index。
公式如下:hash = hashfunc(key)index = hash % array_size
如下圖,John Smith的hash值除以16後的餘數是2,所以他的資料被存在index 02的箱子裡。反覆執行同樣的步驟,一一存入每筆資料。
可以想像的是,求得相同餘數的資料,可能不只一筆,這個現象稱為Collision。當發生Collision時,我們可以用列表list的形式,將同個餘數的數據們連結起來。如下圖,Sandra Dee的餘數和John Smith相同,但箱子裡已經有John Smith了,所以我們用list把Sandra Dee接在John Smith後面。(解決collision的方法還有很多,這邊僅舉出Chaining的例子。)
回到一開始的問題,當我們想得知Lisa Smith的電話時,我們一樣透過hash function得知Lisa Smith的hash值,接著求出index,便可以直接在array[index]中找到他的電話了。那如果我們想找的是Sandra Dee的電話呢? 依照前述的步驟,我們會先找到John Smith,接著再從John Smith開始進行線性搜尋(3–1),直到找到key為Lisa Smith的資料為止。
在一開始我們說,我們要先決定好,所有的資料要被分為幾組,這個決定是非常重要的。
組數太少時,collision的機會就會增加,導致常常需要做線性搜尋(3–1),便無法有效發揮hash table的優勢。但組數太多時,會產生許多沒有儲存到資料的空位,造成記憶體空間浪費。
Hash Table適合用在程式語言的關聯陣列 (Associated Array),意指有key value pair的陣列。
ps. 相對於另一種陣列是索引式陣列,用index存取array element。
1–7 堆積 Heap
堆積是一種樹狀結構,數據被存在各個節點(node)上,用於實踐 “優先佇列 Priority Queue”。
而優先佇列是什麼?可以自由新增數據,讀取數據時從最小值開始選取,就可以稱作優先佇列。
堆積有幾個原則必須遵守:
1. 每個node最多可以有兩個child node。2. Chile node的數一定要比father node大,因此最小的數會在樹狀結構的最上方,稱為root。3. 為了遵守第二點的結構原則,新增數據時,會從最左下方的node開始填入,若最下方一層被填滿時,就產生新的一層,從最左邊開始新增數據。4. 讀取數據時從最小值開始(優先佇列),也就是樹狀結構的root。5. 取出數據後,必須將最尾端的數據提到最上面,接著再進行重整heap結構。
以下圖為例,我們依序填入1, 3, 6, 5, 9, 8 這些數據:
如果要在上圖的結構中新增一個數據4,依照前述的原則,因為最底下一層還有空位,所以4會先被填入這個位置。但填入後發現,他比他的father node 6還要小,不符合”子比父大”的原則,所以他必須跟father node 6交換位置。在堆疊中進行新增或刪除數據時,必須反覆進行“子比父大”原則的檢查,對調位置直到整個heap都符合原則為止。
因為需要反覆比較上下移動,heap的新增和刪除數據所需要的時間,都與heap的高度成正比。假設數據有n個, 則heap高度為log2(n),執行時間為O(log n)。
在需要反覆取出最小值時,heap很方便,例如戴克斯特拉演算法(4–5),之後會說明。
1–8 二元搜尋樹 Binary Search Tree
Binary Search Tree同樣也是樹狀結構,也將數據存在node裏。他有幾個特性:
1. 所有數都會大於連結在其左邊節點上的數 (右比左大)2. 所有數都會小於連結在其右邊節點上的數
舉例來說,在10左邊的數,藍色圈起來的部分(8, 3, 1, 6, 4, 7)全都比他小,在他右邊的數 (14, 13)則比他大。
從這個特性可以得知:
1. 最小值會在從頂點開始,沿線一路往左的最尾端2. 最大值會在從頂點開始,沿線一路往右的最尾端
新增數據時,我們先想像這個數據在樹的最頂端,為了符合前述的特性,我們必須反覆地將這個數跟現有的數比大小。
如此一來才能決定這個數在結構中,應該往左擺還是往右擺 (較小往左,較大則往右),遇到該方向已經沒有節點時,就新增一個節點存放這個新增的數據。
如果我們要在上圖的結構中新增一個數據11,流程如下:
- 一開始,我們比較11與頂點8, 11<8,所以11往右移動
- 接著跟10比大小,11>10,所以再往右移動
- 跟14比大小,11<14,往左移動
- 跟13比大小,11<13,但目前13的左下方沒有node, 所以新增一個node存放11
新增數據11後的結構會長這樣:
刪除節點時,會分為幾種情況:
- 該節點沒有子節點,例如圖中的4,直接刪除即可。
- 該節點有一個子節點,例如圖中的13,刪除13後,把子節點11移到原本13的位置即可。
- 該節點有兩個子節點,例如圖中的3,刪除3後,可以在3左邊的tree中找最大的node(在這邊是1),把1移到原本3的位置。或者是,在3右邊的tree中找最小的node(在這邊是4),把4移到原本3的位置也可以。
note:如果被移動的節點本身也有子結點,就反覆進行同樣的步驟,可參考遞迴演算法河內塔。
要搜尋一個節點時,類似新增數據的邏輯,從頂端開始,比較大小,根據比大小結果決定接下來要往左邊還是右邊繼續找。
我們可以把二元搜尋樹想成,是用樹狀結構來表現二元搜尋(3–2)。比較的次數就等同於樹的高度,但這也取決於這棵樹長得平衡不平衡,當樹比較平衡的時候,執行時間會是O(log n),但如果這棵樹長得一點都不像樹,反而是往一邊靠攏成一直線的樣子,那執行時間會提高成O(n)。