Skip to content

heap

以Python實作資料結構 – Data Structure Implements in Python

  • Python

以Python實作資料結構

tags: data-structure, python

TOC

簡介

什麼是資料結構?為什麼要使用資料結構?

是電腦中儲存、組織資料的方式,可以讓我們有效地儲存資料,並讓所有運算能最有效率地完成

演算法的運行時間是根據資料結構決定的,所以使用適當的資料結構來降低演算法的時間複雜度,如:

  • 最短路徑演算法若無適當的資料結構,運行時間是O(N^2),使用(heap/priority queue)可以大幅降低運行時間至O(N*logN)

抽象資料型態 Abstract Data Types

簡單而言,ADT是針對資料結構的「規範」或「描述」,像是物件導向語言裡面的interface,但不會實作細節

舉例堆疊的ADT描述:

  • push(): 插入元素 item 至堆疊頂端
  • pop(): 移除並回傳堆疊頂端的元素
  • peek(): 看堆疊頂端的資料而不取出
  • size(): 看堆疊的長度

ADT跟資料結構的關係

每個ADT在底層都有相對應的資料結構去實作ADT裡定義過的行為(method)

ADT Data Structures
Stack array, linked list
Queue array, linked list
Priority Queue heap
Dictionary/Hashmap array

時間複雜度 Big O notation

描述演算法的效率(複雜度),舉例來說,A宅想要分享他的D槽給B宅,有以下幾種做法:

  1. 台北騎車到屏東B宅家
  2. 用網路傳輸,不考慮被FBI攔截的情況
1GB 1TB 500TB
騎車運送硬碟 600 min 600 min 600 min
網路傳輸 3 min 3072 min 1536000 min

從上表來看,騎車這個選項雖然聽起來很蠢,但不管硬碟有多大,都能確保10個小時內可以送達—— O(1);至於網路傳輸隨著檔案越大,所需的時間也越長 —— O(N);從這裡就可以看出常數時間(constant time)和線性時間(linear time)的差別對效率的影響有多大了

在表現複雜度函數的時候,有幾個通用的規則:

  • 多個步驟用加法: O(a+b)

  • 省略常數: ~~O(3n)~~ O(n)

  • 不同的input用不同的變數表示: ~~O(N^2)~~ O(a*b)

  • 省略影響不大的變數: ~~O(n+n^2)~~ O(n^2)

陣列 Array

物件或值的集合,每個物件或值可以被陣列的索引(index, key)識別

  • 索引從0開始
  • 因為有索引,我們可以對陣列做隨機存取(Random Access)

優點:

  • 隨機存取不用搜尋就能訪問陣列當中所有值,執行速度快O(1)
  • 不會因為鏈結斷裂而遺失資料
  • 循序存取快

缺點:

  • 重建或插入陣列須要逐一複製裏頭的值,時間複雜度是O(N)
  • 編譯的時候必須事先知道陣列的大小,這讓陣列這個資料結構不夠動態(dynamic)
  • 通常陣列只能存同一種型別
  • 不支援連結串列的共享

Implements

行為 big O
search 搜尋 O(1)
insert 插入第一項 O(N)
append 插入最後一項 O(1)
remove 移除第一項 O(N)
removeLast 移除最後一項 O(1)

以Python實作

random indexing: O(1)

linear search: O(n)

連結串列 Linked List & 雙向連結串列 Double Linked List

  • 節點包含datareferenced object
  • 連結的方式是節點(node)記住其他節點的參考(reference)
  • 最後一個節點的參考是NULL

優點

  • 各節點型態、記憶體大小不用相同
  • 動態佔用的記憶體,不須事先宣告大小
  • 插入、刪除快O(1)

缺點

  • 不支援隨機存取,只能循序存取(sequencial access),時間複雜度為O(N)
  • 須額外空間儲存其他節點的參考
  • 可靠性較差,連結斷裂容易遺失資料
  • 難以向前(backward)訪問,可以用雙向連結串列來處理,不過會多佔用記憶體空間

Implements

行為 big O
search 搜尋 O(N)
insert 插入第一項 O(1)
append 插入最後一項 O(N)
remove 移除第一項 O(1)
removeLast 移除最後一項 O(N)

註:連結串列沒有index,處理插入或移除第N項會需要先循序找到插入/移除位置,因此會需要O(N)的時間

以Python實作

以下的代碼是我實作的範例,有錯誤煩請指正。

主要概念是實作__getitem__來循序存取(indexing),另外Double Linked List支援反向存取,故訪問lst[0]lst[-1]皆可以達成O(1)的時間複雜度

執行結果請參考travishen/gist/linked-list.md

Linked List現實中的應用

  1. 低級別的內存管理(Low Level Memory Management),以C語言為例:
  • malloc()free(): 見Heap Management
  • chart * chart_ptr = (chart*)malloc(30);: 取得30byte的heap memory
  1. 許多Windows的應用程式:工具列視窗切換、PhotoViewer
  2. 區塊鏈技術

image
[圖片來源]

堆疊 Stack

  • 推疊是一種抽象資料型態,特性是先進後出(LIFO, last in first out)
  • 在高階程式語言,容易用array、linked list來實作
  • 大部分的程式語言都是Stack-Oriented,因為仰賴堆疊來處理method call(呼叫堆疊, Call Stack)。

Implements

行為 big O
push 將資料放入堆疊的頂端 O(1)
pop 回傳堆疊頂端資料 O(1)
peek 看堆疊頂端的資料而不取出 O(1)

應用

  • call stack + stack memory
  • 深度優先搜尋演算法(Depth-First-Search)
  • 尤拉迴路(Eulerian Circuit)
  • 瀏覽器回上一頁
  • PhotoShop上一步(undo)

註:任何遞迴(recursion)形式的演算法,都可以用Stack改寫,例如DFS。不過就算我們使用遞迴寫法,程式最終被parsing還是Stack

Stack memory vs Heap memory

stack memory heap memory
有限的記憶體配置空間 記憶體配置空間較大
存活時間規律可預測的 存活時間不規律不可預測的
CPU自動管理空間(GC) 使用者自主管理空間
區域變數宣告的空間不能更動 物件的值可以變動,如realloc()

以Python實作

Using Lists as Stacks

佇列 Queue

  • 佇列是一種抽象資料型態,特性是先進先出(FIFO, first in first out)
  • 在高階程式語言,容易用array、linked list來實作

應用

  • 多個程序的資源共享,例如CPU排程
  • 非同步任務佇列,例如I/O Buffer
  • 廣度優先搜尋演算法(Depth-First-Search)

以Python實作

參考

二元搜尋樹 Binary Search Tree

主要的優點就是時間複雜度能優化至O(logN)

  • 每個節點最多有兩個子節點
  • 子節點有左右之分
  • 左子樹的節點小於根節點、右子樹的節點大於根節點
  • 節點值不重複
Average case Worst case
insert O(logN) O(N)
delete O(logN) O(N)
search O(logN) O(N)

以Python實作insert, remove, search,執行結果請參考gist

BST現實中的應用

  • OS file system
  • 機器學習:決策樹

平衡二元搜尋樹 Balancing Binary Search Tree, AVL Tree

  • 能保證O(logN)的時間複雜度
  • 每次insert, delete都要檢查平衡,非平衡需要額外做rotation
  • 判斷是否平衡:
    • 左子樹高度 - 右子樹高度 > 1: rotate to right
    • 左子樹高度 - 右子樹高度 < -1: rotate to left
    • image
Average case Worst case
insert O(logN) O(logN)
delete O(logN) O(logN)
search O(logN) O(logN)

不適合用在排序,時間複雜度為O(N*logN)

  • 插入n個:O(N*logN)
  • in-order迭代:O(N)

繼承上面BST繼續往下實作,有bug請協助指正,執行結果請參考gist

  • 任一節點設定完left或right,更新該節點height
  • 每個insert的call stack檢查檢查節點是否平衡,不平衡則rotate

紅黑樹 Red-Black Tree

  • 相較於AVL樹,紅黑樹犧牲了部分平衡性換取插入/刪除操作時更少的翻轉操作,整體效能較佳(插入、刪除快)
  • 不像AVL樹的節點屬性用height來判斷是否須翻轉,而是用紅色/黑色來判斷
    • 根節點、末端節點(NULL)是黑色
    • 紅色節點的父節點和子節點是黑色
    • 每條路徑上黑色節點的數量相同
    • 每個新節點預設是紅色,若違反以上規則:
    • 翻轉,或
    • 更新節點顏色

image

Average case Worst case
insert O(logN) O(logN)
delete O(logN) O(logN)
search O(logN) O(logN)

github上用python實作的範例:Red-Black-Tree

優先權佇列 Priority Queue

  • 相較於Stack或Queue,對資料項目的取出順序是以權重(priority)來決定
  • 常用heap來實作

二元堆積 Binary Heap

  • 是一種二元樹資料結構,通常透過一維陣列(one dimension array)
  • 根據排序行為分成minmax
    • max heap: 父節點的值(value)或權重(key)大於子節點
    • min heap: 父節點的值(value)或權重(key)小於子節點
  • 必須是完全(compelete)二元樹或近似完全二元樹

註:

  • heap資料結構跟heap memory沒有關聯
  • 優勢在於取得最大權重或最小權重項目(root),時間複雜度為O(1)
time complexity
insert O(N) + O(logN) reconsturct times
delete O(N) + O(logN) reconsturct times

應用

  • 堆積排序法(Heap Sort)
  • 普林演算法(Prim’s Algorithm)
  • 戴克斯特拉演算法(Dijkstra’s Algorithm)

堆積排序 Heapsort

  • 是一種比較排序法(Comparision Sort)
  • 主要優勢在於能確保O(NlogN)的時間複雜度
  • 屬於原地演算法(in-place algorithm),缺點是每次排序都須重建heap——增加O(N)時間複雜度
  • 在一維陣列起始位置為0的indexing:

image

用Python實作Max Binary Heap,請參考gist

python build-in heapq

關聯陣列/對映/字典 Associative Array/ Map/ Dictionary

  • 鍵、值的配對(key-value)
  • 相較於樹狀資料結構,劣勢在於排序困難
  • 主要操作:
    • 新增、刪除、修改值
    • 搜尋已知的鍵

image

hash function

  • division method: modulo operator

h(x) = n % m

n: number of keys, m: number of buckets

Collision

當多個key存取同一個bucket(slot),解決collision會導致時間複雜度提高

解法:

  • chaining: 在同一個slot用linked list存放多個關聯
  • open addressing: 分配另一個空的slot
    • linear probing: 線性探測
    • quadratic probing: 二次方探測,如1, 2, 4, 8…
    • rehashing

Dynamic resizing

load factor(佔用率): n / m

  • load factor會影響到存取的效能,因此須要根據使用率動態變更陣列大小;
  • 舉例來說,Java觸發resize的時機點大約是佔用超過75%時、Python則約是66%

應用

  • 資料庫
  • Network Routing
  • Rabin-Karp演算法
  • Hashing廣泛用於資料加密

以Python實作,請參考gist

Average case Worst case
insert O(1) O(N)
delete O(1) O(N)
search O(1) O(N)

三元搜尋樹 Ternary Search Tree, TST

  • 相較其他樹狀資料結構而言,佔用記憶體空間較小
  • 只儲存string,不存NULL或其他物件
  • 父節點可以有3個子節點:left(less)middle(equal)right(greater)
  • 可以同時用來當作hashmap使用,也可以做排序
  • 效能上比hashmap更佳,在解析key時是漸進式的(如cat若root沒有c就不用繼續找了)

image

應用

  • autocompelete
  • 拼字檢查
  • 最近鄰居搜尋(Near-neighbor)
  • WWW package routing
  • 最長前綴匹配(perfix matching)
  • Google Search

以Python實作,請參考gist

互斥集 Disjoint sets / union-find data structure

  • 一堆沒有交集的集合,如10個學生分成4組
  • 主要操作: unionfindmakeSet
  • 通常以linked list或tree來實作
  • 訪問disjoint set中的任何節點都回傳同一個root value

set在union過程中會遇到不平衡的問題,有兩種最佳化方法:

  1. union by rank: 讓小的樹接到較大的樹
  2. path compression: 訪問節點時調整樹的結構,直接與root連結

應用

  • Kruskal: 檢查圖中是否有cycle

以Python實作,輸出請參考gist