1 數組對象
2 可以視為一棵完全二叉樹
3 一個堆可以被看作一棵二叉樹和一個數組，如下圖所示：
4 下標計算（通常使用內聯函數或者宏來定義下標操作）：
5 最大堆：除根節點以外的每個節點i，有A[PARENT(i)] >= A[i]
最小堆：除根節點意外的每個節點i，有A[PARENT(i)] <= A[i]
步驟：
排序過程
1 建堆過程
1） 從第一個非葉子節點開始，對value為8的節點進行調整，無需調整。
2） 對value值為9的節點進行調整。
3） 對value為2的節點調整
4） 對value為3的節點進行調整
----》
5） 對value為7的節點進行調整
---》
建堆完成
2 堆頂元素與當前堆的最後一個元素進行互換。
3 該堆頂元素已達最終位置，排除出堆
4 對剩下的堆進行調整
遞歸進行堆首和堆尾互換以及調整堆的步驟，結果即為排好序的堆。
// heapsort.h
class HeapSort:public BaseSort {
public:
HeapSort(int Array[], int len) : BaseSort() {
this->Array = Array;
this->len = len;
}
void sort();
private:
/* 建堆 */
void buildMaxHeap();
/* 調整堆，以保持最大堆性質 */
void maxHeapIfy( int i , int curlen);
/* 堆排序 */
void heapSort();
/* 返回父節點下標 */
int Parent(int i) {
if ( i % 2 == 0 )
return i/2;
else
return i/2 + 1;
};
/* 返回左孩子節點下標 */
int Left(int i) { return 2 * i + 1; };
/* 返回右孩子節點下標 */
int Right(int i) { return 2 * i + 2; };
private:
int* Array;
int len;
};
相關成員函數實現
// heapsort.cpp
#include "heapsort.h"
void HeapSort::sort() {
heapSort();
}
void HeapSort::heapSort() {
buildMaxHeap();
int i = this->len;
int tmp;
while( i > 0 ) {
tmp = this->Array[0];
this->Array[0] = this->Array[i-1];
this->Array[i-1] = tmp;
i--;
maxHeapIfy(0, i);
}
}
void HeapSort::maxHeapIfy( int i, int curlen ) {
int left, right, largest;
int tmp;
left = Left(i);
right = Right(i);
if ( left < curlen-1
&& Array[left] > Array[i])
largest = left;
else
largest = i;
if ( right < curlen-1
&& Array[right] > Array[largest])
largest = right;
if ( largest != i ) {
tmp = Array[i];
Array[i] = Array[largest];
Array[largest] = tmp;
maxHeapIfy(largest, curlen);
}
}
void HeapSort::buildMaxHeap() {
int i;
for ( i = (len-1)/2 ; i >= 0; i-- ) {
maxHeapIfy(i, len);
if (DEBUG) {
printArray(this->Array, this->len, "midResult");
}
}
}
測試代碼：
/* --------- HeapSort -------- */
int b[10] = {7,3,2,9,8,5,1,10,4,6};
HeapSort* heapsort = new HeapSort(b, len);
heapsort->sort();
printArray(b, len, "HeapSort ");
------------------------------分割線------------------------------
C++ Primer Plus 第6版 中文版 清晰有書簽PDF+源代碼 http://www.linuxidc.com/Linux/2014-05/101227.htm
讀C++ Primer 之構造函數陷阱 http://www.linuxidc.com/Linux/2011-08/40176.htm
讀C++ Primer 之智能指針 http://www.linuxidc.com/Linux/2011-08/40177.htm
讀C++ Primer 之句柄類 http://www.linuxidc.com/Linux/2011-08/40175.htm
將C語言梳理一下，分布在以下10個章節中：