高级数据结构讲解与案例分析
然而，僅僅掌握好它們不足以應付大廠的算法面試的。為了達到對時間和空間復雜度的理想要求，本節課探究高級數據結構，它們的實現要比那些常用的數據結構要復雜得多。其中重點介紹：
-
優先隊列
-
圖
-
前綴樹
-
線段樹
-
樹狀數組
?
掌握好高級數據結構的性質以及所適用的場合，在分析問題的時候回歸本質，很多題目都能迎刃而解。
?
優先隊列（Priority Queue）
?
特點
能保證每次取出的元素都是隊列中優先級別最高的。優先級別可以是自定義的，例如，數據的數值越大，優先級越高；或者數據的數值越小，優先級越高。優先級別甚至可以通過各種復雜的計算得到。
?
應用場景
從一堆雜亂無章的數據當中按照一定的順序（或者優先級）逐步地篩選出部分乃至全部的數據。
?
舉例：任意一個數組，找出前?k?大的數。
?
解法 1：先對這個數組進行排序，然后依次輸出前?k?大的數，復雜度將會是?O(nlogn)，其中，n?是數組的元素個數。這是一種直接的辦法。
?
解法 2：使用優先隊列，復雜度優化成?O(k + nlogk)。
當數據量很大（即?n?很大），而?k?相對較小的時候，顯然，利用優先隊列能有效地降低算法復雜度。因為要找出前?k?大的數，并不需要對所有的數進行排序。
?
實現
優先隊列的本質是一個二叉堆結構。堆在英文里叫?Binary Heap，它是利用一個數組結構來實現的完全二叉樹。換句話說，優先隊列的本質是一個數組，數組里的每個元素既有可能是其他元素的父節點，也有可能是其他元素的子節點，而且，每個父節點只能有兩個子節點，很像一棵二叉樹的結構。
?
牢記下面優先隊列有三個重要的性質。
1. 數組里的第一個元素?array[0]?擁有最高的優先級別。
2. 給定一個下標 i，那么對于元素 array[i] 而言：
-
它的父節點所對應的元素下標是 (i-1)/2
-
它的左孩子所對應的元素下標是 2×i + 1
-
它的右孩子所對應的元素下標是 2×i + 2
3. 數組里每個元素的優先級別都要高于它兩個孩子的優先級別。
?
優先隊列最基本的操作有兩個。
1. 向上篩選（sift?up / bubble up）
-
當有新的數據加入到優先隊列中，新的數據首先被放置在二叉堆的底部。
-
不斷進行向上篩選的操作，即如果發現該數據的優先級別比父節點的優先級別還要高，那么就和父節點的元素相互交換，再接著往上進行比較，直到無法再繼續交換為止。
? ? ? ?? ? ? ?
時間復雜度：由于二叉堆是一棵完全二叉樹，并假設堆的大小為?k，因此整個過程其實就是沿著樹的高度往上爬，所以只需要?O(logk)?的時間。
???????????
2. 向下篩選（sift down / bubble down）
-
當堆頂的元素被取出時，要更新堆頂的元素來作為下一次按照優先級順序被取出的對象，需要將堆底部的元素放置到堆頂，然后不斷地對它執行向下篩選的操作。
-
將該元素和它的兩個孩子節點對比優先級，如果優先級最高的是其中一個孩子，就將該元素和那個孩子進行交換，然后反復進行下去，直到無法繼續交換為止。
? ? ? ?? ? ? ?
時間復雜度：整個過程就是沿著樹的高度往下爬，所以時間復雜度也是?O(logk)。
?
因此，無論是添加新的數據還是取出堆頂的元素，都需要?O(logk)?的時間。
?
初始化
優先隊列的初始化是一個最重要的時間復雜度，是分析運用優先隊列性能時必不可少的，也是經常容易弄錯的地方。
?
舉例：有?n?個數據，需要創建一個大小為?n?的堆。
?
誤區：每當把一個數據加入到堆里，都要對其執行向上篩選的操作，這樣一來就是?O(nlogn)。
?
解法：在創建這個堆的過程中，二叉樹的大小是從?1?逐漸增長到?n?的，所以整個算法的復雜度經過推導，最終的結果是 O(n)。
?
? ? ? ??? ? ?
?
注意：算法面試中是不要求推導的，你只需要記住，初始化一個大小為?n?的堆，所需要的時間是?O(n)?即可。
?
例題分析
LeetCode 第?347?題：給定一個非空的整數數組，返回其中出現頻率前?k?高的元素。
?
說明：
-
你可以假設給定的?k?總是合理的，且 1 ≤ k ≤ 數組中不相同的元素的個數。
-
你的算法的時間復雜度必須優于?O(nlogn) ，n?是數組的大小
示例：car，car，book，desk，desk，desk
?
解題思路
這道題的輸入是一個字符串數組，數組里的元素可能會重復一次甚至多次，要求按順序輸出前?k?個出現次數最多的字符串。
?
解這類求"前 k 個"的題目，關鍵是看如何定義優先級以及優先隊列中元素的數據結構。
-
題目中有”前?k?個“這樣的字眼，應該很自然地聯想到優先隊列。
-
優先級別可以由字符串出現的次數來決定，出現的次數越多，優先級別越高，反之越低。
-
統計詞頻的最佳數據結構就是哈希表（Hash?Map），利用一個哈希表，就能快速地知道每個單詞出現的次數。
-
將單詞和其出現的次數作為一個新的對象來構建一個優先隊列，那么這個問題就很輕而易舉地解決了。
?
建議：這道題是利用優先隊列處理問題的典型，建議好好練習。
?
??????????????????????????????????Desk (3)
????????????????????????????????????/ ? ?\
?????????????????????????????car(2) ? book(1)?? ? ? ???
????????????????????????????????
?
圖（Graph）
?
基本知識點
圖可以說是所有數據結構里面知識點最豐富的一個，最基本的知識點如下。
-
階（Order）、度：出度（Out-Degree）、入度（In-Degree）
-
樹（Tree）、森林（Forest）、環（Loop）
-
有向圖（Directed Graph）、無向圖（Undirected Graph）、完全有向圖、完全無向圖
-
連通圖（Connected Graph）、連通分量（Connected Component）
-
存儲和表達方式：鄰接矩陣（Adjacency Matrix）、鄰接鏈表（Adjacency List）
?
圍繞圖的算法也是五花八門。
-
圖的遍歷：深度優先、廣度優先
-
環的檢測：有向圖、無向圖
-
拓撲排序
-
最短路徑算法：Dijkstra、Bellman-Ford、Floyd Warshall
-
連通性相關算法：Kosaraju、Tarjan、求解孤島的數量、判斷是否為樹
-
圖的著色、旅行商問題等
?
以上的知識點只是圖論里的冰山一角，對于算法面試而言，完全不需要對每個知識點都一一掌握，而應該有的放矢地進行準備。
?
必會知識點
根據長期的經驗總結，以下的知識點是必須充分掌握并反復練習的。
-
圖的存儲和表達方式：鄰接矩陣（Adjacency Matrix）、鄰接鏈表（Adjacency List）
-
圖的遍歷：深度優先、廣度優先
-
二部圖的檢測（Bipartite）、樹的檢測、環的檢測：有向圖、無向圖
-
拓撲排序
-
聯合-查找算法（Union-Find）
-
最短路徑：Dijkstra、Bellman-Ford
?
其中，環的檢測、二部圖的檢測、樹的檢測以及拓撲排序都是基于圖的遍歷，尤其是深度優先方式的遍歷。而遍歷可以在鄰接矩陣或者鄰接鏈表上進行，所以掌握好圖的遍歷是重中之重！因為它是所有其他圖論算法的基礎。
?
至于最短路徑算法，能區分它們的不同特點，知道在什么情況下用哪種算法就很好了。對于有充足時間準備的面試者，能熟練掌握它們的寫法當然是最好的。
?
建議：LeetCode 里邊有許多關于圖論的算法題，而且都是非常經典的題目，可以通過練習解題來熟練掌握必備知識。
?
?
例題分析
LeetCode 第?785?題：給定一個無向圖 graph，當這個圖為二部圖時返回 true。
?
提示：如果能將一個圖的節點集合分割成兩個獨立的子集 A 和 B，并使圖中的每一條邊的兩個節點一個來自 A 集合，一個來自 B 集合，就將這個圖稱為二部圖。
?
解題思路
判斷一個給定的任意圖是否為二部圖，就必須要對該圖進行一次遍歷：
-
深度優先
-
廣度優先
（關于深度優先和廣度優先算法，將在第?06?節課進行詳細討論）。
?
二部圖，圖的所有頂點可以分成兩個子集 U 和 V，子集里的頂點互不直接相連，圖里面所有的邊，一頭連著子集 U 里的頂點，一頭連著子集 V 里的頂點。
-
給圖里的頂點涂上顏色，子集?U?里的頂點都涂上紅色，子集?V?里的頂點都涂上藍色。
-
開始遍歷這個圖的所有頂點，想象一下手里握有紅色和藍色的畫筆，每次交替地給遍歷當中遇到的頂點涂上顏色。
-
如果這個頂點還沒有顏色，那就給它涂上顏色，然后換成另外一支畫筆。
-
下一個頂點，如果發現這個頂點已經涂上了顏色，而且顏色跟我手里畫筆的顏色不同，那么表示這個頂點它既能在子集?U?里，也能在子集?V?里。
-
所以，它不是一個二部圖。
?
前綴樹（Trie）
?
應用場景
前綴樹被廣泛地運用在字典查找當中，也被稱為字典樹。
?
舉例：給定一系列字符串，這些字符串構成了一種字典，要求你在這個字典當中找出所有以“ABC”開頭的字符串。
?
解法 1：暴力搜索
直接遍歷一遍字典，然后逐個判斷每個字符串是否由“ABC”開頭。假設字典很大，有?N?個單詞，要對比的不是“ABC”，而是任意的，那不妨假設所要對比的開頭平均長度為?M，那么時間復雜度是?O(M×N)。
?
解法 2：前綴樹
如果用前綴樹頭幫助對字典的存儲進行優化，那么可以把搜索的時間復雜度下降為?O(M)，其中?M?表示字典里最長的那個單詞的字符個數，在很多情況下，字典里的單詞個數?N?是遠遠大于?M?的。因此，前綴樹在這種場合中是非常高效的。
?
經典應用
-
網站上的搜索框會羅列出以搜索文字作為開頭的相關搜索信息，這里運用了前綴樹進行后端的快速檢索。
-
漢字拼音輸入法的聯想輸出功能也運用了前綴樹。
?
舉例：假如有一個字典，字典里面有如下詞："A"，"to"，"tea"，"ted"，"ten"，"i"，"in"，"inn"，每個單詞還能有自己的一些權重值，那么用前綴樹來構建這個字典將會是如下的樣子：
?
? ? ? ??? ? ?
?
性質
1.?每個節點至少包含兩個基本屬性。
-
children：數組或者集合，羅列出每個分支當中包含的所有字符
-
isEnd：布爾值，表示該節點是否為某字符串的結尾
?
2. 前綴樹的根節點是空的
所謂空，即只利用到這個節點的?children?屬性，即只關心在這個字典里，有哪些打頭的字符。
?
3. 除了根節點，其他所有節點都有可能是單詞的結尾，葉子節點一定都是單詞的結尾。
?
實現
前綴樹最基本的操作就是兩個：創建和搜索。
?
1. 創建
-
遍歷一遍輸入的字符串，對每個字符串的字符進行遍歷
-
從前綴樹的根節點開始，將每個字符加入到節點的?children?字符集當中。
-
如果字符集已經包含了這個字符，則跳過。
-
如果當前字符是字符串的最后一個，則把當前節點的?isEnd?標記為真。
由上，創建的方法很直觀。
?
前綴樹真正強大的地方在于，每個節點還能用來保存額外的信息，比如可以用來記錄擁有相同前綴的所有字符串。因此，當用戶輸入某個前綴時，就能在?O(1)?的時間內給出對應的推薦字符串。
?
2. 搜索
與創建方法類似，從前綴樹的根節點出發，逐個匹配輸入的前綴字符，如果遇到了就繼續往下一層搜索，如果沒遇到，就立即返回。
?
?
例題分析
LeetCode 第?212?題：給定一個二維網格?board?和一個字典中的單詞列表 words，找出所有同時在二維網格和字典中出現的單詞。
? ? ? ?
單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母在一個單詞中不允許被重復使用。
?
說明：你可以假設所有輸入都由小寫字母?a-z?組成。
?
?
解題思路
這是一道出現較為頻繁的難題，題目給出了一個二維的字符矩陣，然后還給出了一個字典，現在要求在這個字符矩陣中找到出現在字典里的單詞。
?
由于字符矩陣的每個點都能作為一個字符串的開頭，所以必須得嘗試從矩陣中的所有字符出發，上下左右一步步地走，然后去和字典進行匹配，如果發現那些經過的字符能組成字典里的單詞，就把它記錄下來。
?
可以借用深度優先的算法來實現（關于深度優先算法，將在第 06 節課深入探討），如果你對它不熟悉，可以把它想象成走迷宮。
字典匹配的解法 1：每次都循環遍歷字典，看看是否存在字典里面，如果把輸入的字典變為哈希集合的話，似乎只需要?O(1)?的時間就能完成匹配。
?
但是，這樣并不能進行前綴的對比，即，必須每次都要進行一次全面的深度優先搜索，或者搜索的長度為字典里最長的字符串長度，這樣還是不夠高效。
?
字典匹配的解法 2：對比字符串的前綴，借助前綴樹來重新構建字典。
?
假如在矩陣里遇到了一個字符”V”，而字典里根本就沒有以“V”開頭的字符串，則不需要將深度優先搜索進行下去，可以大大地提高搜索效率。
?
構建好了前綴樹之后，每次從矩陣里的某個字符出發進行搜索的時候，同步地對前綴樹進行對比，如果發現字符一直能被找到，就繼續進行下去，一步一步地匹配，直到在前綴樹里發現一個完整的字符串，把它輸出即可。
?
線段樹（Segment Tree）
舉例：假設有一個數組?array[0 … n-1]， 里面有?n?個元素，現在要經常對這個數組做兩件事。
-
更新數組元素的數值
-
求數組任意一段區間里元素的總和（或者平均值）
?
?
?
解法 1：遍歷一遍數組。
-
時間復雜度?O(n)。
?
解法 2：線段樹。
-
線段樹，就是一種按照二叉樹的形式存儲數據的結構，每個節點保存的都是數組里某一段的總和。
-
適用于數據很多，而且需要頻繁更新并求和的操作。
-
時間復雜度 O(logn)。
?
實現
舉例：數組是?[1, 3, 5, 7, 9,?11]，那么它的線段樹如下。
?
? ? ? ?
根節點保存的是從下標?0?到下標?5?的所有元素的總和，即?36。左右兩個子節點分別保存左右兩半元素的總和。按照這樣的邏輯不斷地切分下去，最終的葉子節點保存的就是每個元素的數值。
?
解法：
1. 更新數組里某個元素的數值
從線段樹的根節點出發，更新節點的數值，它保存的是數組元素的總和。修改的元素有可能會落在線段樹里一些區間里，至少葉子節點是肯定需要更新的，所以，要做的是從根節點往下，判斷元素的下標是否在左邊還是右邊，然后更新分支里的節點大小。因此，復雜度就是遍歷樹的高度，即?O(logn)。
?
2. 對數組某個區間段里的元素進行求和
方法和更新操作類似，首先從根節點出發，判斷所求的區間是否落在節點所代表的區間中。如果所要求的區間完全包含了節點所代表的區間，那么就得加上該節點的數值，意味著該節點所記錄的區間總和只是所要求解總和的一部分。接下來，不斷地往下尋找其他的子區間，最終得出所要求的總和。
?
建議：線段樹的實現書寫起來有些繁瑣，需要不斷地練習。
?
例題分析
?
LeetCode 第?315?題：給定一個整數數組 nums，按要求返回一個新數組 counts，使得數組 counts 有該性質——counts[i] 的值是 nums[i] 右側小于?nums[i] 的元素的數量。
?
示例
輸入：[5, 2, 6, 1]
輸出：[2, 1, 1, 0]?
?
解釋
5 的右側有 2 個更小的元素（2 和 1）
2 的右側僅有 1 個更小的元素（1）
6 的右側有 1 個更小的元素（1）
1 的右側有 0 個更小的元素
?
解題思路
給定一個數組?nums，里面都是一些整數，現在要求打印輸出一個新的數組?counts，counts?數組的每個元素?counts[i]?表示?nums?中第?i?個元素右邊有多少個數小于?nums[i]。
?
例如，輸入數組是?[5, 2,?6, 1]，應該輸出的結果是?[2, 1, 1, 0]。
?
因為，對于?5，右邊有兩個數比它小，分別是?2?和?1，所以輸出的結果中，第一個元素是?2；對于?2，右邊只有?1?比它小，所以第二個元素是?1，類推。
?
如果使用線段樹解法，需要理清線段樹的每個節點應該需要包含什么樣的信息。
?
線段樹每個節點記錄的區間是數組下標所形成的區間，然而對于這道題，因為要統計的是比某個數還要小的數的總和，如果把分段的區間設計成按照數值的大小來劃分，并記錄下在這個區間中的數的總和，就能快速地知道比當前數還要小的數有多少個。
? ? ? ?? ? ? ?
1. 首先，讓從線段樹的根節點開始，根節點記錄的是數組里最小值到最大值之間的所有元素的總和，然后分割根節點成左區間和右區間，不斷地分割下去。
2. 初始化，每個節點記錄的在此區間內的元素數量是?0，接下來從數組的最后一位開始往前遍歷，每次遍歷，判斷這個數落在哪個區間，那么那個區間的數量加一。
3. 遇到?1，把它加入到線段樹里，此時線段樹里各個節點所統計的數量會發生變化。
4. 當前所遇到的最小值就是?1。
5.?把?6?加入到線段樹里。
6. 求比?6?小的數有多少個，即查詢線段樹，從?1?到?5?之間有多少個數。
7. 從根節點開始查詢。由于所要查詢的區間是?1?到?5，無法包含根節點的區間?1?到?6，所以繼續往下查詢。
8. 左邊，區間?1?到?3?被完全包含在?1?到?5?之間，把該節點所統計好的數返回。
9. 右邊，區間?1?到?5?跟區間?4?到?6?有交叉，繼續往下看，區間?4?到?5?完全被包含在?1?到?5?之間，所以可以馬上返回，并把統計的數量相加。
10. 最后得出，在當前位置，在?6?的右邊比?6?小的數只有一個。
?
通過這樣的方法，每次把當前的數用線段樹進行個數統計，然后再計算出比它小的數即可。算法復雜度是?O(nlogn)。
?
樹狀數組（Fenwick Tree / Binary Indexed Tree）
?
實現
舉例：假設有一個數組?array[0 … n-1]， 里面有?n?個元素，現在要經常對這個數組做兩件事。
-
更新數組元素的數值
-
求數組前?k?個元素的總和（或者平均值）
?
解法 1：線段樹。
-
線段樹能在?O(logn)?的時間里更新和求解前?k?個元素的總和。
?
解法 2：樹狀數組。
-
該問題只要求求解前 k 個元素的總和，并不要求任意一個區間。
-
樹狀數組可以在?O(logn)?的時間里完成上述的操作。
-
相對于線段樹的實現，樹狀數組顯得更簡單。
?
特點
樹狀數組的數據結構有以下幾個重要的基本特征。
-
它是利用數組來表示多叉樹的結構，在這一點上和優先隊列有些類似，只不過，優先隊列是用數組來表示完全二叉樹，而樹狀數組是多叉樹。
-
樹狀數組的第一個元素是空節點。
-
如果節點?tree[y]?是?tree[x]?的父節點，那么需要滿足條件：y =?x?- (x & (-x))。
?
建議：由于樹狀數組所解決的問題跟線段樹有些類似，所以不花篇幅進行問題的討論。LeetCode?上有很多經典的題目可以用樹狀數組來解決，比如?LeetCode?第?308?題，求一個動態變化的二維矩陣里，任意子矩陣里的數的總和。
?
總結
這節課講解了一些高級的數據結構。
?
1. 優先隊列
經常出現在考題里的，它的實現過程比較繁瑣，但是很多編程語言里都有它的實現，所以在解決面試中的問題時，實行“拿來主義”即可。
鼓勵你自己練習實現一個優先隊列，在實現它的過程中更好地去了解它的結構和特點。
?
2. 圖
被廣泛運用的數據結構，很多涉及大數據的問題都得運用到圖論的知識。
比如在社交網絡里，每個人可以用圖的頂點表示，人與人直接的關系可以用圖的邊表示；再比如，在地圖上，要求解從起始點到目的地，如何行駛會更快捷，需要運用圖論里的最短路徑算法。
?
3. 前綴樹
出現在許多面試的難題當中。
因為很多時候你得自己實現一棵前綴樹，所以你要能熟練地書寫它的實現以及運用它。
?
4. 線段樹和樹狀數組
應用場合比較明確。
例如，問題變為在一幅圖片當中修改像素的顏色，然后求解任意矩形區間的灰度平均值，那么可以考慮采用二維的線段樹了。
?
建議：LeetCode 平臺上，針對上面的這些高級數據結構都有豐富的題目，希望你能用功學習。
總結
以上是生活随笔為你收集整理的高级数据结构讲解与案例分析的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： php配置mongodb扩展、安装mon
- 下一篇： 如何写出安全的API接口（参数加密+超时