前言
这时上次学妹课程的一道作业题，我花了点时间做了下，其题目内容为：
试写一程序，可以对一二元树（binary）进行堆积排序（heap sort）
(a)使用者可自己决定输入二元树的节点个数
(i)node数不超过50
(b)节点值由随机方式产生，并印出随机设值结果
(i)以时间复杂度O(n)的方式设值 (ii)假设值不可重复
(iii)最大值不可大于node数 (例如node数为9，因此最大值为9)
(c)使用者可决定使用MAX-HEAP或者是MIN-HEAP来排序
(d)须将重建堆积得过程印出，以及最后输出排序结果
Sample Output：
后面在网上查了下堆排序的介绍，才对堆有了一点理解。其定义为：堆是一种近似完全二叉树的结构，并满足堆性质，即子节点的键值索引总是小于(或大于)它的父节点。因此堆的任何一颗子树仍然是堆。
实验说明
堆排序的步骤为：
a. 按照大堆或者小堆的方式将输入进来的数组初始化为对应的堆。在此过程中先从最后一个非叶子节点开始慢慢后退到根节点，有点递归的味道，因为一旦一个节点的2个子节点树都进行了堆初始化后，父节点和子节点即使不满足堆对关系，也只需要调换其中一个位置再重新初始化过，而另一个子树就无需堆初始化了（每个子节点的其中一个树都无需堆初始化），这样比较节省算法的速度。
b. 交换堆中跟节点和最后一个未排序的节点的位置，然后继续将参与排序的树进行步骤a的堆形式初始化。
产生不重复的随机数，且需要满足它的时间复杂度为O(n)，这是本题比较刁难的地方。我这里采用方法是：对需排序的数组产生同样大小的标记数组，如果对应位置的数字已经经过随机数发生器产生过，则标志设置为1，否则设置为0，以后每当产生一个随机数，只需判断其对应位置的标志而已，这一操作的时间复杂度为O(1)，所以产生n个不重复的随机数的时间复杂度为O(n),其本质是利用空间来换取时间。
C/c++知识总结：
double floor ( double x );
该函数返回不大于x的最大整数，c/c++中有该函数的存在，如果x是正实数，则返回的整数字x去掉小数的部份。如果x是负实数，则返回的是x去掉小数点后继续减1。
实验结果
采用大端模式对10个数字进行堆排序的结果为：
采用小端模式对10个数字进行堆排序的结果为：
实验代码：
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
#define MAX_HEAP_MODE 0
#define MIN_HEAP_MODE 1
unsigned int heap_node_number = 20;
bool heap_sort_mode = MAX_HEAP_MODE;//默認為大堆排序模式
char choose_sort_mode; //手動輸入選擇小端大端模式的變量
vector<int> heap_tree;
/****
*產生不重複的隨機數，且要滿足時間複雜度為O(n)
*因此不能夠每次產生一個隨機數后，依次與前面已經產生過的隨機數做比較了，因為這樣的時間複雜度為O(n*n)
*因此本函數採用的方法是以空間換時間，多建立一個vector，用來存儲對應的標誌位，如果對應數字已經產生了
*則無需再產生，這樣的話每次判斷只有1下，即每次判斷的時間複雜度為O(1)，產生n個隨機數的時間複雜度就為O(n)了
****/
void GenerateRandomNumber(vector<int> &create_rand_num, int num) {
int count = 0; //記錄已經產生的滿足條件的隨機數的個數
int sum_num = num; //保留所需的隨機數個數值
srand( ( unsigned ) time( 0 ) ); //初始化隨機數種子，這樣的話每次產生的隨機數序列會有不同
vector<bool> rand_flag(num, 0); //以空間換時間的標記向量
while(num) {
int data = rand()%sum_num; //產生0~sum_num之間的隨機數
int temp_flag = rand_flag.at(data); //將產生的隨機數序列放入向量中
if(0 == temp_flag) { //第一次出現
create_rand_num.push_back(data); //將產生的非重複數據放入向量數組中
rand_flag.at(data) = 1; //并將其標誌位賦值為1
count ++;
num = sum_num - count ; //還需要num個隨機數
}
}
}
/****
*人機交互的輸入輸出初始化函數
****/
void Init() {
cout << "請輸入堆排序節點的個數(1~50之間的整數): ";
cin >> heap_node_number;
if(heap_node_number > 50 || heap_node_number < 1) {
cout << "輸入錯誤！請重新輸入1~50之間的整數：" << endl;
Init() ; //重新輸入排序的個數
return ;
}
else
cout << endl;
cout << "請選擇堆排序模式(a)Max Mode, (b)Min Mode: ";
cin >> choose_sort_mode;
if(choose_sort_mode == 'a' || choose_sort_mode == 'A') {
cout <<"當前堆排序模式為：大端模式" <<endl << endl;
heap_sort_mode = MAX_HEAP_MODE;
}
else if(choose_sort_mode == 'b' || choose_sort_mode == 'B') {
cout << "當前堆排序模式為：小端模式" << endl << endl;
heap_sort_mode = MIN_HEAP_MODE;
}
GenerateRandomNumber(heap_tree, heap_node_number);
cout << "二元樹的內容：" << endl ;
for(int i = 0; i < heap_tree.size(); i++) {
cout << "[" << heap_tree.at(i) <<"] ";
}
cout << " " << endl << endl;
}
/****
*輸出堆排序的中間過程
****/
void OutputHeapProcess(vector<int> &heap_tree, int display_mode) {
if(0 == display_mode)
cout << "堆積的內容為：" << endl;
else if(1 == display_mode)
cout << "重建的堆積為：" << endl;
for(int i = 0; i < heap_tree.size(); i++)
cout << "[" << heap_tree.at(i) << "] ";
cout << endl << endl;
}
/****
*該函數的功能是：將heap_tree指定的位置節點select_node開始的子樹調整為堆
*的形式，其結果仍然保留在heap_tree樹中。
*該函數的調用必須配合select_node節點的子樹本身已經滿足堆的形式，也就是說該函數是
*數heap_tree從底往上被調用的
****/
void AdjustChildHeapTree(vector<int> &heap_tree, int select_node, int len, bool heap_sort_mode) {
int i = select_node; //i為需要調整數的根節點在heap_tree的下標
int child_num = 2*i + 1; //i節點的左孩子的下標
if(0 == heap_sort_mode) {
while( child_num < len ) { //子樹中所有的節點都必須調整
if(child_num+1 < len && heap_tree.at(child_num)<heap_tree.at(child_num+1))
child_num ++; //如果右孩子的值大於左孩子的值，則將孩子的下標設置為右孩子的下標，其實就是選擇2個孩子中值較大的那個座標
if(heap_tree.at(i) > heap_tree.at(child_num))
break; //如果根節點的值大於最大的孩子的值，則表示滿足大堆要求，直接退出
else {
/****交換父節點和子節點的位置****/
int temp = heap_tree.at(child_num);
heap_tree.at(child_num) = heap_tree.at(i);
heap_tree.at(i) = temp;
/****重新給父節點和子節點賦下標值****/
i = child_num;
child_num = 2*i +1;
}
}
}
else if(1 == heap_sort_mode) {
while( child_num < len ) { //子樹中所有的節點都必須調整
if(child_num+1 < len && heap_tree.at(child_num)>heap_tree.at(child_num+1))
child_num ++; //如果右孩子的值大於左孩子的值，則將孩子的下標設置為右孩子的下標，其實就是選擇2個孩子中值較大的那個座標
if(heap_tree.at(i) < heap_tree.at(child_num))
break; //如果根節點的值大於最大的孩子的值，則表示滿足大堆要求，直接退出
else {
/****交換父節點和子節點的位置****/
int temp = heap_tree.at(child_num);
heap_tree.at(child_num) = heap_tree.at(i);
heap_tree.at(i) = temp;
/****重新給父節點和子節點賦下標值****/
i = child_num;
child_num = 2*i +1;
}
}
}
return ;
}
void HeapSort(vector<int> &heap_tree, bool heap_sort_mode) {
int len = heap_tree.size();
/****
*堆排序步驟1：
*將heap_tree從最後一個非葉子節點開始初始化為堆的形式
****/
for(int i = len/2; i >= 0; i--)
AdjustChildHeapTree(heap_tree, i, len, heap_sort_mode);
OutputHeapProcess(heap_tree, 0);
/****
*堆排序步驟2：
*將根節點和最後一個節點調換位置
****/
for(int i = 0; i < len-1; i++) {
int temp = heap_tree.at(0);
heap_tree.at(0) = heap_tree.at(len-i-1);
heap_tree.at(len-i-1) = temp;
AdjustChildHeapTree(heap_tree, 0, len-i-1, heap_sort_mode);//因為最後一個數已經是排序好了的，不需要參與下面的堆調整
OutputHeapProcess(heap_tree, 1);
}
}
int main() {
Init();
HeapSort(heap_tree, heap_sort_mode);
return 0;
}