Python 一網打盡<排序算法>之堆排序算法中的樹

本文從說到，再使用的有序性對無序數(shù)列排序。

1. 樹

是最基本的數(shù)據(jù)結構，可以用映射現(xiàn)實世界中一對多的群體關系。如公司的組織結構、網頁中標簽之間的關系、操作系統(tǒng)中文件與目錄結構……都是用樹結構描述的。

樹是由以及所構成的集合。樹結構更多概念不是本文的內容，本文只關心樹數(shù)據(jù)結構中的幾個特殊變種：

如果樹中的任意結點（除葉結點）最多只有兩個子結點，這樣的樹稱為。

如果 中任意結點的子結點（除葉結點）都有 個，則稱為。

滿二叉樹的特性：

根據(jù)的定義可知，從上向下，每一層上的結點數(shù)以 倍的增量遞增。也可以說，滿二叉樹是一個首項為 ，公比為 的等比數(shù)列。所以：

一個層數(shù)為 的滿二叉樹總結點數(shù)為：2-1 。

滿二叉樹的總結點數(shù)一定是奇數(shù)！

根據(jù)等比公式可知第 層上的結點數(shù)為：2，因此，一個層數(shù)為 的滿二叉樹的葉子結點個數(shù)為（也就是最后一層）: 2。

什么是完全二叉樹？

是的一個特例。

通俗理解：在基礎上，從右向左刪除幾個葉子節(jié)點后，此時滿二叉樹就變成了完全二叉樹。如下圖，在上圖滿二叉樹基礎上從右向左刪除 個葉結點后的結構就是完全二叉樹。

完全二叉樹的專業(yè)概念：

一棵深度為 的有 個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編號，如果編號為 的結點與滿二叉樹中編號為 的結點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。

專業(yè)概念有點像繞口令。

顯然，完全二叉樹的葉子結點只能出現(xiàn)在最下層或次下層，且最下層的葉子結點集中在樹的左部。

注意：滿二叉樹肯定是完全二叉樹，而完全二叉樹不一定是滿二叉樹。

2. 二叉堆

是有序的 ，在的基礎上， 提供了有序性特征：

的根結點上的值是整個堆中的或。

當根結點上的值是整個堆結構中的最小值時，此堆稱為最小堆。

如果根結點上的值是整個堆結構中的最大值時，則稱堆為最大堆。

最小堆中，任意節(jié)點的值大于父結點的值，反之，最大堆中，任意節(jié)點的值小于父結點的值。

綜合所述，二叉堆的父結點與子結點之間滿足下面的關系：

如果知道了一個結點的位置 ，則其左子結點在 處，右子結點在 處。

如果有子結點。

如果知道了一個結點的位置 ，則其父結點在 除 處。

根結點沒有父結點。

如上圖所示：

值為 的結點在 處，則其左結點 的位置應該在 處，而實際情況也是在 4 位置。其右子結點 的位置應該在 的位置，實際位置也是在 位置。

值為 的結點現(xiàn)在 位置，其父結點的根據(jù)公式 除 等于 (取整)，應該在 處，而實際情況也是在 處（位置在 、 值為 的結點是其父結點）。

2.1 二叉堆的抽象數(shù)據(jù)結構

當談論某種數(shù)據(jù)結構的抽象數(shù)據(jù)結構時，最基本的 無非就是增、刪、改、查。

二叉堆的基本抽象數(shù)據(jù)結構：

：創(chuàng)建一個新堆。

：向堆中添加新節(jié)點（數(shù)據(jù)）。

：返回最?。ù螅┒训淖钚。ù螅┰?。

：刪除根節(jié)點。

：判斷堆是否為空。

：查詢堆中所有數(shù)據(jù)。

雖然是樹結構的變種，有樹的層次結構，但因結點與結點之間有很密切的數(shù)學關系，使用 中的列表存儲是非常不錯的選擇。

現(xiàn)如有一個數(shù)列=，現(xiàn)使用二叉堆方式保存。先構造一個列表。

列表中的第 位置初始為 ，從第 個位置也就是索引號為 的地方開始存儲堆的數(shù)據(jù)。如下圖，二叉堆中的數(shù)據(jù)在列表中的存儲位置。

2.2 API 實現(xiàn)

設計一個 類封裝對二叉堆的操作方法，類中方法用來實現(xiàn)最小堆。

類中的屬性詳解：

：使用列表存儲的數(shù)據(jù)，初始時，列表的第 位置初始為默認值 。

為什么要設置列表的第 位置的默認值為 ？

這個 也不是隨意指定的，有其特殊數(shù)據(jù)含義：用來描述根結點的父結點或者說根結點沒有父結點。

：用來存儲二叉堆中數(shù)據(jù)的實際個數(shù)。

類中的方法介紹：

：檢查是不是空堆。

：創(chuàng)建根結點。保證根節(jié)點始終存儲在列表索引為 的位置。

：如果是最大堆，則返回二叉堆的最大值，如果是最小堆，則返回二叉堆的最小值。

使用列表保存二叉堆數(shù)據(jù)時，根結點始終保存在索引號為 的位置。

前面是幾個基本方法，現(xiàn)在實現(xiàn)添加新結點，編碼之前，先要知道如何在二叉堆中添加新結點：

添加新結點采用上沉算法。如下演示流程描述了上沉的實現(xiàn)過程。

把添加到已有的的最后面。如下圖，添加值為 的新結點，存儲至索引號為 的位置。

查找的，并與的值比較大小，如果比父結點的值小，則和交換位置。如下圖，值為 的結點小于值為 的父結點，兩者交換位置。

交換后再查詢是否存在父結點，如果有，同樣比較大小、交換，直到到達根結點或比父結點大為止。值為 的結點小于值為 的父結點，繼續(xù)交換。交換后，新結點已經達到了根結點位置，整個添加過程可結束。觀察后會發(fā)現(xiàn)，遵循此流程添加后，沒有破壞二叉堆的有序性。

方法的實現(xiàn)：

測試向二叉堆中添加數(shù)據(jù)。

創(chuàng)建一個空堆。

創(chuàng)建值為 的根結點。

檢查根結點是否創(chuàng)建成功。

添加值為 和值為 的 個新結點，檢查添加新結點后整個二叉堆的有序性是否正確。

添加值為 的新結點，并檢查二叉堆的有序性。

繼續(xù)添加值為 、、 的 個新結點，并檢查二叉堆的狀況。

介紹完添加方法后，再來了解一下，如何刪除二叉堆中的結點。

的刪除操作從根結點開始，如下圖刪除根結點后，空出來的根結點位置，需要在整個二叉堆中重新找一個結點充當新的根結點。

二叉堆中使用下沉算法選擇新的根結點：

找到二叉堆中的最后一個結點，移到到根結點位置。如下圖，把二叉堆中最后那個值為 的結點移到根結點位置。

最小堆中，如果的值比左或右子結點的值大，則和子結點交換位置。如下圖，在二叉堆中把 和 的位置進行交換。

注意：總是和最小的子結點交換。

交換后，如果還是不滿足最小二叉堆父結點小于子結點的規(guī)則，則繼續(xù)比較、交換直到下沉到二叉堆有序為止。如下，繼續(xù)交換 和 的值。如此反復經過多次交換直到整個堆結構符合二叉堆的特性。

方法的具體實現(xiàn)：

方法依賴 和 方法：

方法用查找比父結點小的結點。

方法用來查找是否存在子結點。

測試在二叉堆中刪除結點：

可以看到最后二叉堆的結構和有序性都得到了完整的保持。

3. 堆排序

堆排序指借助堆的有序性對數(shù)據(jù)進行排序。

需要排序的數(shù)據(jù)以堆的方式保存

然后再從堆中以根結點方式取出來，無序數(shù)據(jù)就會變成有序數(shù)據(jù) 。

如有數(shù)列=[4,1,8,12,5,10,7,21,3]，現(xiàn)通過堆的數(shù)據(jù)結構進行排序。

本例中的代碼還有優(yōu)化空間，本文試圖講清楚堆的使用，優(yōu)化的地方交給有興趣者。

4. 后記

在樹結構上加上一些新特性要求，樹會產生很多新的變種，如二叉樹，限制子結點的個數(shù)，如滿二叉樹，限制葉結點的個數(shù)，如完全二叉樹就是在滿二叉樹的“滿”字上做點文章，讓這個""滿"變成"不那么滿"。

在完全二叉樹上添加有序性，則會衍生出二叉堆數(shù)據(jù)結構。利用二叉堆的有序性，能輕松完成對數(shù)據(jù)的排序。

二叉堆中有 2 個核心方法，插入和刪除，這兩個方法也可以使用遞歸方式編寫。

關鍵詞： Python 一網打盡排序算法之堆排序算法中的樹