更新日期：2010/1/29

#include <iostream>
#include <ctime>
using namespace std;

/*二元樹索引(index)的相關存取方法 */
int get_parent_index(int index); //取得父節點索引 
int get_left_index(int index);   //取得左子節點索引 
int get_right_index(int index);  //取得右子節點索引  
//**********************************
 
/*堆積排序(傳入將要排序的陣列及其陣列大小) */
void HeapSort(int A[], int size);
　　
　　//單一子結點最大堆積樹調整
void Max_Heapify(int A[], int index, int size);
　　
　　//建立最大堆積樹(讓上層值比下層值大)
void Build_Max_Heap(int A[], int size);
　　
　　//在螢幕上印出此二元樹陣列的內容 (不印出元素0)
void print_tree(int A[], int size);
　　
//PS: 陣列形式的二元樹，元素0是放著不用的 
//*******************************************

int main()
{
　　const int size=9; //陣列元素的個數
　　int k[size];// k(0 To size-1)，陣列，但因規則定義成二元樹
　　
    //為各個元素安置亂數
　　srand(time(NULL)); //亂數種子
　　for (int i=1; i<size; i++)
　　　　k[i] = rand() % (size*size); //亂數範圍( 0 ~ (size*size-1) )
　　
　　cout << "排序前二元樹陣列: "; 
　　print_tree(k, size);
　　
　　HeapSort(k, size);//堆積排序 
　　
　　cout << "排序後二元樹陣列: "; 
　　print_tree(k, size);

　　system("pause");
　　return 0;　　
}

//印出二元樹陣列
void print_tree(int A[], int size)
{
　　for (int i = 1; i<size; i++)
　　　　cout << A[i] << " "; 
　　cout << endl; 
}

//堆積排序
void HeapSort(int A[], int size)
{
　　Build_Max_Heap(A, size); //建立最大堆積樹

　　cout << "HeapSort開始: ";
　　print_tree(A, size); 
　　
　　// for i = size-1 to 1 step -1
　　for (int i = size-1; i>0; i--){    
　　　　// 元素(1) 和 元素(i) 交換 
　　　　int temp = A[1];
　　　　A[1] = A[i];
　　　　A[i] = temp;
　　　　
　　　　Max_Heapify(A, 1, i); //單一子結點最大堆積樹調整
　　　　
　　　　cout << "HeapSort過程: ";
　　　　print_tree(A, size); 
　　}
}

//建立最大堆積樹
void Build_Max_Heap(int A[], int size)
{
　　cout << "Build_Max_Heap開始: ";
　　print_tree(A, size); 
　　
　　// for i= size-1 to 1 step -1
　　for (int i = size-1; i>0; i--){ 
　　　　Max_Heapify(A, i, size);
　　　　
　　　　cout << "Build_Max_Heap過程: ";
　　　　print_tree(A, size); 
　　} 
}

//單一子結點最大堆積樹調整
void Max_Heapify(int A[], int index, int size) 
{
　　int r = get_right_index(index); //取得右子索引
　　int l = get_left_index(index);  //取得左子索引
　　
　　int largest = index; //假設元素index比其左右子都來的大，事後再驗證改寫。
　　if (l < size) /*And*/ if (A[l] > A[largest])
　　　　largest = l;
　　if (r < size) /*And*/ if (A[r] > A[largest])
　　　　largest = r;
　　　　
　　if (largest != index){ //假設不成立時，將進行改寫，使之假設成立，並進入下一個程序堆疊，使改變的一方成立。
        //陣列A中，元素index和元素largest交換
　　　　int temp = A[index];
　　　　A[index] = A[largest];
　　　　A[largest] = temp; 
　　　　
　　　　Max_Heapify(A, largest, size); //PS: 此時元素(largest)已經不是最大了。
　　}
}

//取得父節點索引
int get_parent_index(int index)
{
　　return index / 2; //整數除法 
}

//取得左子節點索引
int get_left_index(int index)
{
　　return index * 2;
}

//取得右子節點索引
int get_right_index(int index)
{
　　return index * 2 + 1;
}