第六章—“堆排序”算法实现(不包含作业和思考题)

[天浩]

这是本人实现的堆排序算法，但不包含作业题目和思考题的实现，欢迎指正！
三个部分：头文件heapsort.h、程序实现heapsort.c、测试程序heapsort_test.c

第一个文件头文件heapsort.h:
#ifndef _HEAPSORT_H
#define _HEAPSORT_H

#define PARENT(i) (i/2) //父元素的位置
#define LEFT(i) (i*2+1) //左子树的位置
#define RIGHT(i) (i*2+2) //右子树的位置
#define LARGEST 32768 //最大元素，即哨兵元素，可以根据情况而取合适的值
#define LEAST (-32768) //最小元素，即哨兵元素，可以根据情况而取合适的值

//heap_size其实是要随时更新的，但是还未设计出这个更新的函数，可以用全局指针，但是很麻烦，
//所以，在以下的函数中，多了一个参数heap_size,以明确告诉函数heap_size是多少。

//提示错误，并退出
void error(char * s);
//交换两个指针的值
void exchange(int * a, int * b);

//使以i为跟的子树成为最大堆
void max_heapify(int A[], int i, int heap_size);
//使以i为跟的子树成为最小堆
void min_heapify(int A[], int i, int heap_size);

//建立最大堆
void buld_max_heap(int A[], int heap_size);
//建立最小堆
void buld_min_heap(int A[], int heap_size);

//建立最大堆的一个变种
void buld_max_heapII(int A[], int heap_size);
//建立最小堆
void buld_min_heap(int A[], int heap_size);

//最大堆排序
void max_heapsort(int A[], int heap_size);
//最小堆排——书中没有给出这个算法
void min_heapsort(int A[], int heap_size);

//插入一个元素到最大堆
void max_heap_insert(int A[], int key, int heap_size);
//插入一个元素到最小堆
void min_heap_insert(int A[], int key, int heap_size);

//返回最大堆里的最大元素
int heap_maximum(int A[]);
//返回最小堆里的最小元素
int heap_minimum(int A[]);

//去掉并返回A中最大关键字的元素
int heap_extract_max(int A[], int heap_size);
//去掉并返回A中最小关键字的元素
int heap_extract_min(int A[], int heap_size);

//将元素x关键字值增加到key，这里key值不能小于x的原关键字的值
void heap_increase_max_key(int A[], int i, int key);
//将元素x关键字值减小到key，这里key值不能大于x的原关键字的值
void heap_increase_min_key(int A[], int i, int key);

#endif

第二个文件——实现程序heapsort.c:
#include<stdlib.h>
#include<stdio.h>
#include"heapsort.h"

//出错提示
void error(char * s){
printf("%s\n",s);
exit(1);
}

//交换数据a,b
void exchange(int *a,int *b){
int c;
c = *a;
*a = *b;
*b = c;
}

//使以i为跟的子树成为最大堆
void max_heapify(int A[], int i, int heap_size){
int l, r, largest;

l = LEFT(i);
r = RIGHT(i);
if((l < heap_size)&&(A[i] < A[l]))
largest = l;
else largest = i;
if((r < heap_size)&&(A[largest] < A[r]))
largest = r;
if(largest != i){
exchange(&A[i], &A[largest]);
max_heapify(A, largest, heap_size);
}
}

//使以i为跟的子树成为最小堆
void min_heapify(int A[], int i, int heap_size){
int l, r, least;

l = LEFT(i);
r = RIGHT(i);
if((l < heap_size)&&(A[i] > A[l]))
least= l;
else least = i;
if((r < heap_size)&&(A[least] > A[r]))
least = r;
if(least != i){
exchange(&A[i], &A[least]);
min_heapify(A, least, heap_size);
}

}

//建立最大堆
void buld_max_heap(int A[], int heap_size){
int i;
for(i = heap_size/2; i >= 0; --i)
max_heapify(A, i, heap_size);
}

//建立最大堆的一个变种
void buld_max_heapII(int A[], int heap_size){
int i;
for(i = 1;i < heap_size; ++i)
max_heap_insert(A, i, A[i]);

}

//建立最小堆
void buld_min_heap(int A[], int heap_size){
int i;
for(i = heap_size/2; i >= 0; --i)
min_heapify(A, i, heap_size);
}

//建立最小堆的一个变种
void buld_min_heapII(int A[], int heap_size){
int i;
for(i = 1; i < heap_size; ++i)
min_heap_insert(A, i, A[i]);

}

//最大堆排序
void max_heapsort(int A[], int heap_size){
int i, n;

buld_max_heap(A, heap_size);
n = heap_size;
for(i = n-1; i >= 1; --i){
exchange(&A[0], &A[i]);
--n;
max_heapify(A, 0, n);
}
}

//最小堆排序——书中没有给出这个算法
void min_heapsort(int A[], int heap_size){
int i, n;

buld_min_heap(A, heap_size);
n = heap_size;
for(i = n-1; i >= 1; --i){
--n;
buld_min_heap(&A[n-i], n);
min_heapify(A, 0, n);
}
}

//以下开始是优先级队列算法，这里实现的优先级最大的弱点就是：
//
//所以buld_max_heap()成了保持堆整齐的函数,
//而在heap_extract_max()函数中,则要在exchange()函数后把A[heap_size-1]赋值为负无穷大/小，
//这样更安全。

//还有一个问题：这里所实现的优先级是整数，可以是负数，而现实当中一般用不小于0的整数来表示优先级。
//如果要修改，则用unsigned int代替int,相应的max_heapify()、buld_max_heap()等函数也做同样的修改
//非常危险的是也相当有趣的是，当传递给函数的参数类型是int时，将自动执行类型转换到unsigned int，
//这时如果传递给函数一个优先级为-1的元素，而执行类型转换成unsigned int就成类int类型的最大数，可见
//保持表示优先级数据类型一致是多么的重要^ _ ^

//将元素x关键字值增加到key，这里key值不能小于x的原关键字的值
void max_heap_increase_key(int A[], int i, int key){
if(A[i] > key)
error("max_heap_increase_key: the key is smaller than
current
key!");
A[i] = key;
while((i > 0)&&(A[PARENT(i)]<A[i])){
exchange(&A[PARENT(i)], &A[i]);
i = PARENT(i);
}
}

//将元素x关键字值减小到key，这里key值不能大于x的原关键字的值
void min_heap_increase_key(int A[], int i, int key){
if(A[i] < key)
error("min_heap_increase_key: the key is greater than
current
key!");
A[i] = key;
while((i > 0)&&(A[PARENT(i)] < A[i])){
exchange(&A[PARENT(i)], &A[i]);
i = PARENT(i);
}
}

//插入一个元素到最大堆
void max_heap_insert(int A[], int key, int heap_size){
++heap_size;
max_heap_increase_key(A,heap_size-1,key);

}

//插入一个元素到最小堆
void min_heap_insert(int A[], int key, int heap_size){
++heap_size;
min_heap_increase_key(A,heap_size-1,key);
}

//返回最大堆里的最大元素
int heap_maximum(int A[]){
return A[0];

}

//返回最小堆里的最小元素
int heap_minimum(int A[]){
return A[0];
}

//去掉并返回A中最大关键字的元素
int heap_extract_max(int A[], int heap_size){
int max;

if(heap_size < 0)
error("heap_extract_max: heap_underflow!");
max = A[0];
exchange(&A[0], &A[heap_size-1]);
A[heap_size-1] = LEAST;
--heap_size;
max_heapify(A, 0, heap_size);
return max;
}

//去掉并返回A中最小关键字的元素
int heap_extract_min(int A[], int heap_size){
int min;

if(heap_size < 0)
error("heap_extract_max: heap_underflow!");
min = A[0];
exchange(&A[0], &A[heap_size-1]);
A[heap_size-1] = LARGEST;
--heap_size;
min_heapify(A, 0, heap_size);
}

第三个文件——测试程序heapsort_test.c:
//由于display函数的参数* s，本程序的测试结果是自解释的

#include<stdio.h>
#include"heapsort.h"

int array[20] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7,};

//显示堆中的元素，参数* s 是最近调用函数的函数名
void display(int A[], int n, char * s){
int i;

printf("%s\n",s);
for(i = 0; i < n; ++i)
printf("%d\t", A[i]);
printf("\n");
}

int main(){
//列出原始数组
display(array, 10, "array:");

buld_max_heap(array, 10);
display(array, 10, "buld_max_heap:");
printf("heap_maximum: %d\n", heap_maximum(array));

max_heapsort(array, 10);
display(array, 10, "max_heapsort:");

buld_max_heap(array, 10);
buld_min_heap(array, 10);
display(array, 10, "buld_min_heap:");
printf("heap_minimum: %d\n", heap_minimum(array));

min_heapsort(array, 10);
display(array, 10, "min_heapsort:");

buld_max_heap(array, 10);
display(array, 10, "buld_max_heap:");
heap_extract_max(array, 10);
display(array, 10, "heap_extract_max:");

buld_max_heap(array, 10);
display(array, 10, "buld_max_heap:");
max_heap_insert(array, 5, 10);
display(array, 11, "max_heap_insert:");
return 0;
}