堆排序(Heap-Sort)

這裡記錄,堆排序算法,咱的理解。

堆=完全n叉樹,根據自身具體情況控制,一般是完全二叉樹。

Max-Heap,具備每一個根節點都大於等於其子節點的堆,稱之爲最大堆。

Min-Heap,正好與上相反。

堆排序的實現,主要依賴與堆數據結構的實現。

Heap-Sort需要實現幾個基本過程:

  1. MAX-HEAPIFY過程,保持最大堆性質,其運行時間爲O(lgn)
  2. BUILD-MAX-HEAP過程,可在無序數組基礎之上構造最大堆,線性時間運行
  3. HEAPSORT過程,對數組進行原地排序,運行時間O(nlgn)
  4. MAX-HEAP-INSERT,HEAP-EXTRACT-MAX,HEAP-INCREASE-KEY和HEAP-MAXIMUM過程的運行時間爲O(lgn),這些過程可以使得堆結構作為優先隊列使用!(重要)

也就是說維持一個穩定性質的最大/最小堆是實現堆排序的先決條件,只要可以完成這一點,就可以比較輕鬆的折騰出排序功能。另外由於最大/最小堆的這種性質,可以利用其作為操作系統作業調度隊列的一個實現。

Anyway,有個打算,為了學習&記錄,以後把咱對這些算法的基本C or CPP實現都寫出來放到Github上。:)

发表评论

电子邮件地址不会被公开。 必填项已用*标注