图解排序算法-堆排序（附源码）
时间：2021-08-19 16:27:59
手机看文章
扫描二维码
随时随地手机看文章
[导读]01—认识堆排序堆排序是利用堆这种数据结构而设计的一种排序算法，它的最好、最好、平均复杂度都为nlog(n)，它也是不稳定排序算法。堆是具有以下性质的完全二叉树：每个结点的值都大于等于其左右孩子结点的值，称为最大堆。每个结点的值都小于等于其左右孩子结点的值，称为最小堆。如下图：0...
01—认识堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，它的最好、最好、平均复杂度都为nlog(n)，它也是不稳定排序算法。堆是具有以下性质的完全二叉树：每个结点的值都大于等于其左右孩子结点的值，称为最大堆。每个结点的值都小于等于其左右孩子结点的值，称为最小堆。如下图：
02—堆排序思想及其实现无论网上还是书本上介绍堆排序的实现都是用数组实现，但是今天我们用二叉树的思想实现堆排序。堆排序思想：将待排序列构造成一个最小堆，此时整个序列的最小值就是堆的根结点，新结点插入都将从左子树开始填充到右子树，新插入的结点先成为叶子结点，再从新插入的结点开始往上遍历，如果父结点的值比该结点的值大则交换数据，直到父结点的值比其结点的值小为止。重复对n个值进行操作，依次取出根结点，则整个序列是有序的。定义堆结点和声明操作函数：
#define INT_NAN (0xFFFFFFFF - 1)
typedef struct tree_node{
struct tree_node *left;
struct tree_node *right;
int data;
int height;
}tree_node_t;
extern tree_node_t *new_tree_node(int data);
extern int heap_sort_get_node(tree_node_t **root);
extern void heap_sort_insert_node(tree_node_t **root, int data);
extern void destroy_heap_tree(tree_node_t *root);
extern void tree_print(tree_node_t *root);堆结点里的高度并不是二叉树的高度，由于二叉堆是完全二叉树，因此只要结点的左右子树不是满二叉树且高度不一致时，就可继续插入结点，直到左右子树都是满二叉树且高度一致，再往下一层插入结点。新建堆结点函数实现：
tree_node_t *new_tree_node(int data){
tree_node_t *node = malloc(sizeof(tree_node_t));
if(node == NULL){
return NULL;
}
node->data = data;
node->left = NULL;
node->right = NULL;
node->height = 1;
return node;
}释放堆结点函数实现：
if(node == NULL){
return;
}
node->left = NULL;
node->right = NULL;
free(node);
}二叉堆插入结点步骤：将新插入的结点按照层级结构成为叶子结点，再从新结点往根结点遍历，如果其父结点的值比该结点的值小，则交换数据，这个过程称为上滤。新插入的结点不断上滤，直到父结点的值比其结点的值小则停止上滤。如图所示：
交换数据函数实现：
void swap(int *a, int *b){
int c = *a;
*a = *b;
*b = c;
}上滤操作函数实现：
tree_node_t *up_filter(tree_node_t *root){
if(root == NULL){
return NULL;
}
if(root->left != NULL 
下载文档
