作者丨写代码的牛顿
来源丨编程学习总站
01
—
认识堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，它的最好、最好、平均复杂度都为nlog(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 && root->right != NULL){
if(root->data > root->left->data){
swap(&root->data, &root->left->data);
}
if(root->data > root->right->data){
swap(&root->data, &root->right->data);
}
}else if(root->left != NULL){
if(root->data > root->left->data){
swap(&root->data, &root->left->data);
}
}else if(root->right != NULL){
if(root->data > root->right->data){
swap(&root->data, &root->right->data);
}
}
return root;
}int get_balance_factor(tree_node_t *root){
if(root->left != NULL && root->right != NULL){
return root->left->height - root->right->height;
}else if(root->left != NULL && root->right == NULL){
return root->left->height;
}else if(root->left == NULL && root->right != NULL){
return 0 - root->right->height;
}
return 0;
}
tree_node_t *sub_tree_insert_node(tree_node_t *root, int data){
if(root == NULL){
return new_tree_node(data);
}
int factor = get_balance_factor(root);
if(factor <= 0){
//插入左边
//printf("to left\n");
root->left = sub_tree_insert_node(root->left, data);
}else{
//插入右边
//printf("to right\n");
root->right = sub_tree_insert_node(root->right, data);
}
//printf("current node: %d\n", root->data);
return up_filter(root);
}
void update_height(tree_node_t *root){
if(root == NULL){
return;
}
update_height(root->left);
update_height(root->right);
if(root->left != NULL && root->right != NULL){
root->height = root->left->height < root->right->height ? root->left->height : root->right->height;
root->height++;
}else{
root->height = 1;
}
}
void heap_sort_insert_node(tree_node_t **root, int data){
if(root == NULL){
return;
}
*root = sub_tree_insert_node(*root, data);
update_height(*root);
}获取结点函数实现：
tree_node_t *add_sub_tree_to_tree(tree_node_t *root, tree_node_t *sub){
if(sub == NULL || root == NULL){
return root;
}
add_sub_tree_to_tree(root, sub->left);
add_sub_tree_to_tree(root, sub->right);
return sub_tree_insert_node(root, sub->data);
}
int heap_sort_get_node(tree_node_t **root){
if(root == NULL || *root == NULL){
return INT_NAN;
}
tree_node_t *tree_root = *root;
int data = tree_root->data;
//printf("first node: %d\n", tree_root->data);
if(tree_root->left == NULL && tree_root->right == NULL){
free_tree_node(tree_root);
*root = NULL;
}else if(tree_root->left == NULL && tree_root->right != NULL){
//右孩子非空，右孩子代替原结点
*root = tree_root->right;
free_tree_node(tree_root);
}else if(tree_root->right == NULL && tree_root->left != NULL){
//左孩子非空，左孩子代替原结点
*root = tree_root->left;
free_tree_node(tree_root);
}else{
//左右孩子非空
tree_node_t *temp = NULL;
tree_node_t *free_node = tree_root;
if(tree_root->left->data < tree_root->right->data){
//左孩子小于右孩子，左孩子代替原结点
temp = tree_root->left->right;
tree_root->left->right = tree_root->right;
*root = tree_root->left;
}else{
//右孩子小于左孩子，右孩子代替原结点
temp = tree_root->right->left;
tree_root->right->left = tree_root->left;
*root = tree_root->right;
}
free_tree_node(free_node);
*root = add_sub_tree_to_tree(*root, temp);
destroy_heap_tree(temp);
}
return data;
}
void destroy_heap_tree(tree_node_t *root){
if(root == NULL){
return;
}
destroy_heap_tree(root->left);
destroy_heap_tree(root->right);
free_tree_node(root);
}—
算法验证
#include <stdio.h>
#include "heap_sort.h"
int main()
{
int arr[8] = {8, 2, 9, 1, 6, 9, 0, 4};
int i = 0;
tree_node_t *root = NULL;
printf("输入原始序列\n");
for(i = 0; i < 8; i++){
printf("%d, ", arr[i]);
heap_sort_insert_node(&root, arr[i]);
}
printf("\n");
printf("最小堆输出\n");
for(i = 0; i < 8; i++){
printf("%d, ", heap_sort_get_node(&root));
}
printf("\n");
return 0;
}输入原始序列
8, 2, 9, 1, 6, 9, 0, 4,
最小堆输出
0, 1, 2, 4, 6, 8, 9, 9,-End-
最近有一些小伙伴，让我帮忙找一些 面试题 资料，于是我翻遍了收藏的 5T 资料后，汇总整理出来，可以说是程序员面试必备！所有资料都整理到网盘了，欢迎下载！
面试题】即可获取文章引用微信公众号"程序员大咖",如有侵权,请联系管理员删除!