算法设计和数据结构学习堆排序
前言
这时上次学妹课程的一道作业题，我花了点时间做了下，其题目内容为：
试写一程序，可以对一二元树（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 ;
}
参考文献：
http://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F#C.2B.2B.E8.AF.AD.E8.A8.80
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息