還想看更多文章的朋友可以訪問我的個(gè)人博客
一些基礎(chǔ)知識
學(xué)習(xí)堆排序，總要了解堆的數(shù)據(jù)結(jié)構(gòu)吧，了解堆又需要了解二叉樹的基本知識，了解二叉樹要先知道樹是個(gè)什么東西吧…… 呃，還是太年輕。這里簡單談?wù)劙伞?/p>
二叉樹
-
提一下樹——樹是一對多的數(shù)據(jù)結(jié)構(gòu)，從一個(gè)根結(jié)點(diǎn)開始，生長出它的子結(jié)點(diǎn)，而每一個(gè)子結(jié)點(diǎn)又生長出各自的子結(jié)點(diǎn)，成為子樹。如果某個(gè)結(jié)點(diǎn)不再生長出子結(jié)點(diǎn)了，它就成為葉子。
一個(gè)普通的樹結(jié)構(gòu) -
二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹（）的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree），且次序不能顛倒。
二叉樹 -
完全二叉樹除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者是在右邊缺少連續(xù)若干節(jié)點(diǎn)。
完全二叉樹
-
滿二叉樹的所有分支結(jié)點(diǎn)都既有左子樹又有右子樹，并且所有葉子都在同一層。每一層上的節(jié)點(diǎn)數(shù)都是最大節(jié)點(diǎn)數(shù) 。
滿二叉樹
堆排序
-
數(shù)組與堆結(jié)構(gòu) （如何用數(shù)組實(shí)現(xiàn)）：
image對于任一節(jié)點(diǎn)（若其在數(shù)組中對應(yīng)元素下標(biāo)為 i）而言，都有
- 子節(jié)點(diǎn)：左孩子是2*i+1，右孩子是2*i+2
- 父節(jié)點(diǎn)：(i - 1) / 2
-
生成大根堆：
堆可以分為大根堆和小根堆。在大根堆中，所有子樹中子節(jié)點(diǎn)的值都小于等于父節(jié)點(diǎn)；而小根堆的組織方式恰好相反：所有子樹中子節(jié)點(diǎn)的值都大于等于父節(jié)點(diǎn)。在堆排序中，使用的是大根堆；而小根堆常被用作構(gòu)建優(yōu)先隊(duì)列。
調(diào)整大根堆的過程，遍歷數(shù)組元素，將當(dāng)前節(jié)點(diǎn)與其父節(jié)點(diǎn)進(jìn)行比較：
- 若當(dāng)前節(jié)點(diǎn)小于等于父節(jié)點(diǎn)，則比較下一位置。
- 若當(dāng)前節(jié)點(diǎn)大于父節(jié)點(diǎn)，則將當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)交換，然后比較交換后的父節(jié)點(diǎn)（交換前的“當(dāng)前”節(jié)點(diǎn)）與其父節(jié)點(diǎn)進(jìn)行比較(交換）過程。這個(gè)過程很明顯可以是個(gè)遞歸過程。
下面是該過程的實(shí)現(xiàn)：
/** * 遞歸調(diào)整大根堆 * @param arr array * @param index current node index * @param comparable 比較原則 */ private void heapInsert(T[] arr, int index, Comparator<T> comparable) { int parent = (index - 1) >>> 1; if (comparable.compare(arr[index], arr[parent]) <= 0) { return; } swap(arr, index, parent); heapInsert(arr, parent, comparable); } /** * 非遞歸調(diào)整大根堆 */ private void heapInsertByLoop(T[] arr, int index, MangoComparable<T> comparable) { int parent = (index - 1) / 2; while (comparable.compare(arr[index], arr[parent]) > 0) { swap(arr, index, parent); index = parent; parent = (index - 1) / 2; } } 容易想到的是，調(diào)整完畢后的樹仍然是無序的。但是可以理解的是根節(jié)點(diǎn)一定是整個(gè)樹（數(shù)組）的最大值，那么我們完全可以利用上述過程查找最大值，然后將與樹的最后一個(gè)節(jié)點(diǎn)交換。再對除最后一個(gè)節(jié)點(diǎn)的前n-1個(gè)樹節(jié)點(diǎn)（將樹的規(guī)?？s小1，size--）進(jìn)行大根堆調(diào)整，再交換。循環(huán)執(zhí)行此過程，即可使得元素升序排列。
值得注意的是，大根堆生成過程中的調(diào)整策略，是將當(dāng)前元素與父節(jié)點(diǎn)比較（由底向上），利用該策略同樣可以完成上述排序過程，流程如下：(構(gòu)建大根堆 -> 交換)
具體實(shí)現(xiàn)如下：
@Override
public void sort(T[] array, Comparator<T> comparable) {
if (array == null || array.length < 2) {
return;
}
for (int i = 0; i < array.length; i++) {
heapInsert(array, i, comparable);
}
int heapSize = array.length;
swap(array, 0, --heapSize);
while (heapSize > 0) {
for (int i = 0; i < heapSize; i++) {
heapInsert(array, i, comparable);
}
swap(array, 0, --heapSize);
}
}
而在排序過程中，我們當(dāng)然也可以便利地比較左右子樹與父節(jié)點(diǎn)即，當(dāng)前節(jié)點(diǎn)（由頂向下，畢竟此時(shí)我們已經(jīng)生成了堆結(jié)構(gòu)了）。找到當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)中較大的子節(jié)點(diǎn)，與當(dāng)前節(jié)點(diǎn)比較：
- 若當(dāng)前節(jié)點(diǎn)大于等于較大的子節(jié)點(diǎn)，則判斷下一個(gè)節(jié)點(diǎn)。
- 若當(dāng)前節(jié)點(diǎn)小于較大的子節(jié)點(diǎn)，則將當(dāng)前節(jié)點(diǎn)與較大的節(jié)點(diǎn)交換（我們的目標(biāo)是讓最大值向上浮）。然后比較交換后的所產(chǎn)生的父節(jié)點(diǎn)（交換前的較大的子節(jié)點(diǎn)）與其子節(jié)點(diǎn)進(jìn)行比較(交換）。
具體流程如下：
具體實(shí)現(xiàn)如下：
@Override
public void sort(T[] array, Comparator<T> comparable) {
// ...
while (heapSize > 0) {
heapify(array, 0, heapSize, comparable);
}
}
/**
* 遞歸版
*/
private void heapify(T[] arr, int index, int size, Comparator<T> comparable) {
int left = 2*index + 1;
if (left < size) {
int largestChild = left + 1 < size
&& comparable.compare(arr[left+1], arr[left]) > 0 ? left+1 : left;
if (comparable.compare(arr[largestChild], arr[index]) < 0) {
return;
}
swap(arr, largestChild, index);
heapify(arr, largestChild, size, comparable);
}
}
/**
* 非遞歸版
*/
private void heapifyByLoop(T[] arr, int index, int size, Comparator<T> comparable) {
int left = 2*index + 1;
while (left < size) {
int largestChild = left + 1 < size
&& comparable.compare(arr[left+1], arr[left]) > 0 ? left+1 : left;
if (comparable.compare(arr[largestChild], arr[index]) < 0) {
return;
}
swap(arr, largestChild, index);
index = largestChild;
left = 2*index + 1;
}
}
-
時(shí)間復(fù)雜度分析：我們知道二叉樹結(jié)構(gòu)的基礎(chǔ)操作時(shí)間復(fù)雜度為
O(logN)，其中N是樹的節(jié)點(diǎn)數(shù)。大根堆的生成過程相當(dāng)于不斷向樹中增加節(jié)點(diǎn)的過程，即數(shù)組中下標(biāo)為0的元素，插入高度為0的二叉樹； 數(shù)組中下標(biāo)為1的元素，插入高度為1的二叉樹； 數(shù)組中下標(biāo)為2的元素，插入高度為2的二叉樹； …… 數(shù)組中下標(biāo)為n-1的元素，插入高度為n-1的二叉樹；所以，該操作時(shí)間復(fù)雜度為
，經(jīng)數(shù)學(xué)證明（
和
"同階函數(shù)"），因此生成大根堆的時(shí)間復(fù)雜度是
O(nlogn)。
