在chapter0 中，我們?cè)O(shè)計(jì)了一個(gè)產(chǎn)品，叫私人衣櫥。這個(gè)手機(jī)app幫助我們管理衣物，方便我們查找衣物的位置，也可以展示我們的衣服。
現(xiàn)在這個(gè)app要添加新功能：
- 找出過去一年中，自己最不常用的10件物品，看是否需要轉(zhuǎn)賣或者扔掉。
怎么實(shí)現(xiàn)這個(gè)功能呢？方法有很多，我們先來介紹第一種方法：
“堆”
這個(gè)堆不是土堆、人堆，而是數(shù)據(jù)的堆。
特征
計(jì)算機(jī)語言里的描述：堆是指一個(gè)特定的基于樹結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)。
我們先不管這個(gè)抽象的描述，我們只需要記住堆的特征：
一.任何一個(gè)節(jié)點(diǎn)不大于父親節(jié)點(diǎn)（大根堆）
比如下面這幅圖，2的父節(jié)點(diǎn)是17，17的父節(jié)點(diǎn)是19，是不是子節(jié)點(diǎn)小于父節(jié)點(diǎn)。不過19不是2的父節(jié)點(diǎn)，因?yàn)橹虚g跨了一層。其他以此類推。100叫根節(jié)點(diǎn)，因?yàn)樗呀?jīng)到頂了，沒有父節(jié)點(diǎn)。
二.它必須是一棵完全二叉樹：就是除了最后一層節(jié)點(diǎn)外，其他層節(jié)點(diǎn)數(shù)必須是兩個(gè)，最后一層的所有節(jié)點(diǎn)集中在最左側(cè)。
如下圖：
它是一個(gè)正確的例子：55必須有兩個(gè)子節(jié)點(diǎn)：22；25。22和25 不一定是有兩個(gè)子節(jié)點(diǎn)，因?yàn)樗麄円呀?jīng)最后一層。
又如下圖：
它是一個(gè)錯(cuò)誤的例子，為什么？最后一層的所有節(jié)點(diǎn)沒有集中在最左側(cè)。因?yàn)樽庸?jié)點(diǎn)必須從上往下，從左往右添加。
了解完堆的概念，那么堆有哪些分類呢？
首先是：大根堆，即根節(jié)點(diǎn)的值最大，逐層遞減，最下面一層的數(shù)據(jù)最小。
再次是小根堆：正好和大根堆相反。
介紹完堆，我們回到上面的問題，假設(shè)我們有一系列的衣物，他們的使用頻率分別是：35 33 42 10 14 19 27 44 26 31，我們將組數(shù)據(jù)構(gòu)建成一個(gè)大根堆，從下往上層級(jí)的節(jié)點(diǎn)必然是小的值。
最終的結(jié)果是這樣的：
具體構(gòu)建大根堆的步驟：
Step 1 ? 在堆的底部創(chuàng)建一個(gè)新節(jié)點(diǎn)
Step 2 ? 將值放在該節(jié)點(diǎn)
Step 3 ? 比較新關(guān)鍵的節(jié)點(diǎn)值與它的父節(jié)點(diǎn)值大小
Step 4 ? 如何父節(jié)點(diǎn)值小于新節(jié)點(diǎn)值，那么交換他們
Step 5 ? 重復(fù)第三步和第四部
好了，現(xiàn)在堆創(chuàng)建好，我們需要將頻率最低的幾個(gè)數(shù)據(jù)取出，堆是一種特殊的樹（一種數(shù)據(jù)結(jié)構(gòu)，后面再介紹），遍歷數(shù)據(jù)有兩種方式：廣度遍歷和深度遍歷，方式如名字：
廣度遍歷方向：
遍歷出來的數(shù)據(jù)是：
44 42 35 33 31 19 27 10 26 14
深度遍歷方向：
遍歷出來的數(shù)據(jù)是：
44 42 33 10 26 31 14 35 19 27
利用廣度遍歷，已經(jīng)基本是從大到小了，后面的幾個(gè)就已經(jīng)基本滿足我們的要求了。而且我們還可以知道，根節(jié)點(diǎn)就是我們使用頻率最高的衣物。
但是我們也發(fā)現(xiàn)，廣度遍歷出來的數(shù)據(jù)，并不絕對(duì)是最后一個(gè)數(shù)據(jù)就是頻率最低，這個(gè)怎么解決呢？
解決辦法是：
排序
將使用頻率：35 33 42 10 14 19 27 44 26 31，這組數(shù)據(jù)進(jìn)行從高到底排序。也就實(shí)現(xiàn)我們的功能。
那排序的算法怎么設(shè)計(jì)呢？
選擇排序（常規(guī)思維想到的第一個(gè)方法）
思想：首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
算法描述
n個(gè)記錄的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。具體算法描述如下：
- 初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空；
- 第i趟排序(i=1,2,3…n-1)開始時(shí)，當(dāng)前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當(dāng)前無序區(qū)中-選出關(guān)鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個(gè)記錄R交換，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)；
- n-1趟結(jié)束，數(shù)組有序化了。
冒泡排序
冒泡排序是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
算法描述
- 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)；
- 對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)；
- 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；
- 重復(fù)步驟1~3，直到排序完成。
歸并排序（Merge Sort）
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。
算法描述
- 把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列；
- 對(duì)這兩個(gè)子序列分別采用歸并排序；
-
將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。
歸并排序.gif
基數(shù)排序（Radix Sort）
基數(shù)排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的，先按低優(yōu)先級(jí)排序，再按高優(yōu)先級(jí)排序。最后的次序就是高優(yōu)先級(jí)高的在前，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前。
算法描述
- 取得數(shù)組中的最大數(shù)，并取得位數(shù)；
- arr為原始數(shù)組，從最低位開始取每個(gè)位組成radix數(shù)組；
-
對(duì)radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）；
基數(shù)排序.gif
排序的算法還有很多，就不一一介紹了。
總結(jié)
選擇排序：不停找最小值（效率也是最低的）
冒泡排序：相鄰比較，不停交換，冒泡
歸并排序：分組，不同組之間比較
基數(shù)排序：非比較類算法，先低優(yōu)先級(jí)再高優(yōu)先級(jí)排序
上面的堆也是也可以達(dá)到排序的目的。
通過排序，我們就可以得到降序的一個(gè)數(shù)組：
10 14 19 26 27 31 33 35 42 44
還怕找不到你最不常用的衣物嗎？好了，最不常用的衣物已經(jīng)找到了，快去處理掉把。
其他知識(shí)
堆的刪除
從葉子開始添加，刪除的時(shí)候從根節(jié)點(diǎn)開始刪除。
具體的步驟是：
Step 1 ? 刪除根節(jié)點(diǎn).
Step 2 ? 移動(dòng)最近一層的最近一個(gè)元素到根節(jié)點(diǎn)位置
Step 3 ? 比較它與子節(jié)點(diǎn)值的大小
Step 4 ? 加入父節(jié)點(diǎn)值小于子節(jié)點(diǎn)值，則相互交換
Step 5 ? 重復(fù)第三步和第四步
