<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                [TOC] ## 算法原理 先上一張堆排序動畫演示圖片: [![圖片來自維基百科](http://bubkoo.qiniudn.com/Sorting_heapsort_anim.gif)](https://box.kancloud.cn/2015-07-26_55b456f07354c.gif "圖片來自維基百科") 圖片來自維基百科 **1\. 不得不說說二叉樹** 要了解堆首先得了解一下[二叉樹](http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91),在計算機科學中,二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”(left subtree)和“右子樹”(right subtree)。二叉樹常被用于實現[二叉查找樹](http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9)和[二叉堆](http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E5%A0%86)。 二叉樹的每個結點至多只有二棵子樹(不存在度大于 2 的結點),二叉樹的子樹有左右之分,次序不能顛倒。二叉樹的第 i 層至多有 2i?- 1 個結點;深度為 k 的二叉樹至多有 2k?- 1 個結點;對任何一棵二叉樹 T,如果其終端結點數為 n0,度為 2 的結點數為 n2,則n0?= n2?+ 1。 樹和二叉樹的三個主要差別: * 樹的結點個數至少為 1,而二叉樹的結點個數可以為 0 * 樹中結點的最大度數沒有限制,而二叉樹結點的最大度數為 2 * 樹的結點無左、右之分,而二叉樹的結點有左、右之分 二叉樹又分為完全二叉樹(complete binary tree)和滿二叉樹(full binary tree) 滿二叉樹:一棵深度為 k,且有 2k?- 1 個節點稱之為滿二叉樹 [![深度為 3 的滿二叉樹 full binary tree](http://bubkoo.qiniudn.com/full%C2%A0binary%C2%A0tree.png)](https://box.kancloud.cn/2015-07-26_55b456fd1c9e6.png "深度為 3 的滿二叉樹 full binary tree") 深度為 3 的滿二叉樹 full binary tree 完全二叉樹:深度為 k,有 n 個節點的二叉樹,當且僅當其每一個節點都與深度為 k 的滿二叉樹中序號為 1 至 n 的節點對應時,稱之為完全二叉樹 [![深度為 3 的完全二叉樹 complete binary tree](http://bubkoo.qiniudn.com/complete%C2%A0binary%C2%A0tree.png)](https://box.kancloud.cn/2015-07-26_55b457076f6f5.png "深度為 3 的完全二叉樹 complete binary tree") 深度為 3 的完全二叉樹 complete binary tree **2\. 什么是堆?** 堆(二叉堆)可以視為一棵完全的二叉樹,完全二叉樹的一個“優秀”的性質是,除了最底層之外,每一層都是滿的,這使得堆可以利用數組來表示(普通的一般的二叉樹通常用鏈表作為基本容器表示),每一個結點對應數組中的一個元素。 如下圖,是一個堆和數組的相互關系 [![堆和數組的相互關系](http://bubkoo.qiniudn.com/heap-and-array.png)](https://box.kancloud.cn/2015-07-26_55b4571042a0a.png "堆和數組的相互關系") 堆和數組的相互關系 對于給定的某個結點的下標 i,可以很容易的計算出這個結點的父結點、孩子結點的下標: * Parent(i) = floor(i/2),i 的父節點下標 * Left(i) = 2i,i 的左子節點下標 * Right(i) = 2i + 1,i 的右子節點下標 [![](http://bubkoo.qiniudn.com/heap-and-array-parent-children.png)](https://box.kancloud.cn/2015-07-26_55b45710897d7.png) 二叉堆一般分為兩種:最大堆和最小堆。 最大堆: * 最大堆中的最大元素值出現在根結點(堆頂) * 堆中每個父節點的元素值都大于等于其孩子結點(如果存在) [![最大堆](http://bubkoo.qiniudn.com/max-heap.png)](https://box.kancloud.cn/2015-07-26_55b45710bd585.png "最大堆") 最大堆 最小堆: * 最小堆中的最小元素值出現在根結點(堆頂) * 堆中每個父節點的元素值都小于等于其孩子結點(如果存在) [![最小堆](http://bubkoo.qiniudn.com/min-heap.png)](https://box.kancloud.cn/2015-07-26_55b4571112559.png "最小堆") 最小堆 **3\. 堆排序原理** > 堆排序就是把最大堆堆頂的最大數取出,將剩余的堆繼續調整為最大堆,再次將堆頂的最大數取出,這個過程持續到剩余數只有一個時結束。在堆中定義以下幾種操作: > * 最大堆調整(Max-Heapify):將堆的末端子節點作調整,使得子節點永遠小于父節點 > * 創建最大堆(Build-Max-Heap):將堆所有數據重新排序,使其成為最大堆 > * 堆排序(Heap-Sort):移除位在第一個數據的根節點,并做最大堆調整的遞歸運算 繼續進行下面的討論前,需要注意的一個問題是:數組都是 Zero-Based,這就意味著我們的堆數據結構模型要發生改變 [![Zero-Based](http://bubkoo.qiniudn.com/heap-and-array-zero-based.png)](https://box.kancloud.cn/2015-07-26_55b4571146cea.png "Zero-Based")Zero-Based 相應的,幾個計算公式也要作出相應調整: * Parent(i) = floor((i-1)/2),i 的父節點下標 * Left(i) = 2i + 1,i 的左子節點下標 * Right(i) = 2(i + 1),i 的右子節點下標 最大堆調整(MAX‐HEAPIFY)的作用是保持最大堆的性質,是創建最大堆的核心子程序,作用過程如圖所示: [![Max-Heapify](http://bubkoo.qiniudn.com/MAX%E2%80%90HEAPIFY-Procedure.png)](https://box.kancloud.cn/2015-07-26_55b4571192f0c.png "Max-Heapify") Max-Heapify 由于一次調整后,堆仍然違反堆性質,所以需要遞歸的測試,使得整個堆都滿足堆性質,用 JavaScript 可以表示如下: ~~~ /** * 從 index 開始檢查并保持最大堆性質 * * @array * * @index 檢查的起始下標 * * @heapSize 堆大小 * **/ function maxHeapify(array, index, heapSize) { var iMax = index, iLeft = 2 * index + 1, iRight = 2 * (index + 1); if (iLeft iMax = iLeft; } if (iRight iMax = iRight; } if (iMax != index) { swap(array, iMax, index); maxHeapify(array, iMax, heapSize); // 遞歸調整 } } function swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; } ~~~ 通常來說,遞歸主要用在分治法中,而這里并不需要分治。而且遞歸調用需要壓棧/清棧,和迭代相比,性能上有略微的劣勢。當然,按照20/80法則,這是可以忽略的。但是如果你覺得用遞歸會讓自己心里過不去的話,也可以用迭代,比如下面這樣: ~~~ /** * 從 index 開始檢查并保持最大堆性質 * * @array * * @index 檢查的起始下標 * * @heapSize 堆大小 * **/ function maxHeapify(array, index, heapSize) { var iMax, iLeft, iRight; while (true) { iMax = index; iLeft = 2 * index + 1; iRight = 2 * (index + 1); if (iLeft iMax = iLeft; } if (iRight iMax = iRight; } if (iMax != index) { swap(array, iMax, index); index = iMax; } else { break; } } } function swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; } ~~~ 創建最大堆(Build-Max-Heap)的作用是將一個數組改造成一個最大堆,接受數組和堆大小兩個參數,Build-Max-Heap 將自下而上的調用 Max-Heapify 來改造數組,建立最大堆。因為 Max-Heapify 能夠保證下標 i 的結點之后結點都滿足最大堆的性質,所以自下而上的調用 Max-Heapify 能夠在改造過程中保持這一性質。如果最大堆的數量元素是 n,那么 Build-Max-Heap 從 Parent(n) 開始,往上依次調用 Max-Heapify。流程如下: [![Build-Max-Heap](http://bubkoo.qiniudn.com/building-a-heap.png)](https://box.kancloud.cn/2015-07-26_55b457121b1f3.png "Build-Max-Heap") Build-Max-Heap 用 JavaScript 描述如下: ~~~ function buildMaxHeap(array, heapSize) { var i, iParent = Math.floor((heapSize - 1) / 2); for (i = iParent; i >= 0; i--) { maxHeapify(array, i, heapSize); } } ~~~ 堆排序(Heap-Sort)是堆排序的接口算法,Heap-Sort先調用Build-Max-Heap將數組改造為最大堆,然后將堆頂和堆底元素交換,之后將底部上升,最后重新調用Max-Heapify保持最大堆性質。由于堆頂元素必然是堆中最大的元素,所以一次操作之后,堆中存在的最大元素被分離出堆,重復n-1次之后,數組排列完畢。整個流程如下: [![Heap-Sort](http://bubkoo.qiniudn.com/HeapSort.png)](https://box.kancloud.cn/2015-07-26_55b457127e46f.png "Heap-Sort") Heap-Sort 用 JavaScript 描述如下: ~~~ function heapSort(array, heapSize) { buildMaxHeap(array, heapSize); for (int i = heapSize - 1; i > 0; i--) { swap(array, 0, i); maxHeapify(array, 0, i); } } ~~~ ## JavaScript 語言實現 最后,把上面的整理為完整的 javascript 代碼如下: ~~~ function heapSort(array) { function swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; } function maxHeapify(array, index, heapSize) { var iMax, iLeft, iRight; while (true) { iMax = index; iLeft = 2 * index + 1; iRight = 2 * (index + 1); if (iLeft < heapSize && array[index] < array[iLeft]) { iMax = iLeft; } if (iRight < heapSize && array[iMax] < array[iRight]) { iMax = iRight; } if (iMax != index) { swap(array, iMax, index); index = iMax; } else { break; } } } function buildMaxHeap(array) { var i, iParent = Math.floor(array.length / 2) - 1; for (i = iParent; i >= 0; i--) { maxHeapify(array, i, array.length); } } function sort(array) { buildMaxHeap(array); for (var i = array.length - 1; i > 0; i--) { swap(array, 0, i); maxHeapify(array, 0, i); } return array; } return sort(array); } ~~~ ## 參考文章 * [Wikipedia](http://en.wikipedia.org/wiki/Heapsort) * [維基百科,堆排序](http://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F) * [維基百科,二叉樹](http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91) * [Algorithms Chapter 6 Heapsort](http://ind.ntou.edu.tw/~litsnow/al98/pdf/Algorithm-Ch6-Heapsort.pdf) * [Heap Sort](http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm) * [堆與堆排序](http://blog.kingsamchen.com/archives/547#viewSource) * [堆排序](http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.4.2.1.htm) * [堆排序(Heap Sort)算法學習](http://www.nowamagic.net/algorithm/algorithm_HeapSortStudy.php) * [Sorting Algorithm Animations](http://www.sorting-algorithms.com/)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看