DSA
含有「DSA」共 17 篇內容
全部內容
發佈日期由新至舊
從Python 內建deque資料結構的角度切入，
同時了解deque 與 FIFO Queue相關的function用法。
collections.deque是一種兩端點皆可進出的雙端佇列
在兩端點高效地在O(1)常數時間內添加和刪除元素。
這使得deque非常適合實現FIFO Queue
深入探討圖(Graph)的基本概念 及 最短路徑Shortest Path的尋找。
我們專注於廣度優先搜尋(BFS)演算法，以等權圖的最短路徑為例，
詳細說明如何利用BFS從起點擴散到終點，並且提供詳細的程式碼範例。
透過實作，讀者能夠更清楚理解圖論及BFS的應用，並體會水波紋擴散模型的重要性。
定義
圖Graph: 由節點和邊所組成的一個網狀資料結構。
圖的表達方式Graph representation:
常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。
本文以adjacenct list作為示範。
節點Vertex: 節點
定義
圖Graph: 由節點和邊所組成的一個網狀資料結構。
圖的表達方式Graph representation:
常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。
本文以adjacenct list作為示範。
Min-Heap 最小堆是一種特殊的樹狀資料結構，
其中每個節點的值都小於或等於其子節點的值。這意味著最小值總是位於根節點。
Min-Heap 常用於實作優先權佇列 (Priority Queue)、Dijkstra 演算法、
排序以及尋找中位數等應用。
Prefix Sum（前綴和）是一種用於計算陣列中任意區間和的高效方法。
前綴和算是一種犧牲空間換取時間效能提升的策略。
這在需要頻繁查詢區間和的情況下特別有用。
一開始，初始化時花費O(n)時間，掃描每個元素累加，建立一個prefix sum table，
接著，提供query介面查詢區間和
二元搜尋樹（Binary Search Tree，簡稱 BST）是一種特殊的二元樹結構，
具有以下特性：
左子樹：左子樹上所有節點的值均小於該節點的值。
右子樹：右子樹上所有節點的值均大於該節點的值。
無重複值：每個節點的值都是唯一的。
這些特性使得二元搜尋樹在搜尋、插入和刪除操作具有較佳的效能。
接著來進入圖論的重點之一，Tree與Binary Tree。
二元樹（Binary Tree）是一種樹狀數據結構，其中每個節點最多有兩個子節點，通常稱為左子節點和右子節點。這些子節點可以是其他節點或空節點（即無子節點）。
二元樹是其他進階樹的基礎，可延伸推廣到Binary Search Tree
看樣子真的要找時間來學
今天，我們將用Python list來實現Disjoint Set (併查集，另外也有人稱之為Union-Find)。
Disjoint Set適合用於處理一些子集合的合併和根節點的查找操作。
這種資料結構在圖論中非常有用，特別是在解決連通性相關問題的應用。
在之前的教學中，已經學會了用雙向鏈結串列來實作Stack 堆疊。
今天，要用另一種底層資列結構，python list，來實作Stack 堆疊。
讀者可以從中發現，因為python list的功能和function實作已經很豐富，
所以使用起來，相當直覺，也簡單許多。
🤪🤪🤪