揭秘数据结构的魔力：用堆（Heap）打造高效排序

1. 向上调整法建堆

2. 向下调整建堆的时间复杂度

所以向下调整法建堆的时间复杂度为O(N)，向下调整法的时间复杂度为logN

d. 堆的插入

void HPPush(HP* php, HPDataType x){assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror(\"realloc fail!\");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);}

ⅰ. 时间复杂度

运用了一次向上调整法时间复杂度为O(logN)

e. 堆的删除

堆的删除要交换堆顶元素和最后一个元素，把size--，在用一次向下调整法就可以了，不可以直接删除堆顶元素再建堆，一来这样时间复杂度增大了，二是删除堆顶元素，元素之间关系错乱了，父子变叔侄，兄弟变父子

void HPPop(HP* php){assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);}

ⅰ. 时间复杂度

运用了一次向下调整法，时间复杂度为O(logN)

f. 堆的判空

bool HPEmpty(HP* php){assert(php);return php->size == 0;}

ⅰ. 时间复杂度

时间复杂度为O(1)

g. 取堆元素

HPDataType HPTop(HP* php){assert(php);return php->a[0];}

ⅰ. 时间复杂度

时间复杂度为O(1)

h. 堆的摧毁

void HPDestroy(HP* php){assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;}

i. 堆的排序（堆的向上调整法和向下调整法不传结构体的原因）

void HPSort(HPDataType* a, int n){//这里不用建大堆选出最大数,建堆的时间复杂度为O(N)// 取出最大数后再N-1个数进行建堆，执行次数为N-1//n个数，执行次数为N+N-1+N-2.....+1;时间复杂度为O(N^2)//，和冒泡排序时间复杂度为一样，没有时间上的优势for(int i=(n-1-1)/2;i>=0;i--){AdjustDown(a, n, i);}//对数组进行升序排列//需要建大堆//收尾交换//把最后一个值不放在堆中,建大堆选出最大数，将其放在最后int end = n-1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);end--;}}

原因：由于向上调整法和向下调整法传结构体每次都需要建一个堆，太耗费时间，但如果传数组，在用调整法时就不需要写一个堆的结构体，比如堆的排序

ⅰ. 时间复杂度

向下调整法建堆的时间复杂度为O(N)，排序的时间复杂度为和向上调整时间一样，计算方式一样，为O(NlogN)，总的时间复杂度为O(NlogN)。

习题：在很大的数据个数中找出最大的k个数，借用文件的形式实现

#define _CRT_SECURE_NO_WARNINGS 1#include#include#include#includevoid Swap(int *a,int *b){int tmp = *a;*a = *b;*b = tmp;}void createNData(){ srand((unsigned int)time(NULL));const char* file = \"data.txt\";//要打开的文件FILE* fin = fopen(file, \"w\");if (fin == NULL){perror(\"fopen fail\");return;}for (int i = 1; i <= 20; i++){int x = rand() % 10000 + 1;fprintf(fin, \"%d\\n\", x);}fclose(fin);}void AdjustDown(int* a, int n, int parent){int child = parent * 2 + 1;while (child < n){if (child + 1  a[child + 1]){child++;}if (a[parent] > a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void topk(){int k;int x;const char* file = \"data.txt\";//要打开的文件printf(\"要找出的最大数字的个数:>\");scanf(\"%d\", &k);FILE* fout = fopen(\"data.txt\", \"r\");if (fout == NULL){perror(\"fopen fail\");return;}int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror(\"malloc fail\");return;}for (int i = (k - 1 - 1)/2 ; i >= 0; i--){AdjustDown(minheap, k, i);}while (fscanf(fout, \"%d\", &x) != EOF){if (x > minheap[0]){minheap[0] = x;AdjustDown(minheap, k, 0);}}for (int i = 0; i < k; i++){printf(\"%d\\n\", minheap[i]);}fclose(fout);}int main(){createNData();topk();return 0;}

堆的实现全部代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1#include\"Heap.h\"int main(){HPDataType a[] = { 50,100,480,76,31,31,226 };HPSort(a, sizeof(a) / sizeof(a[0]));//之前向上调整和向下调整就是为了这里//直接传a数组，而不是for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++){printf(\"%d \", a[i]);//排升序}HP hp;//HPInitArray(&hp,a,sizeof(a)/sizeof(HPDataType));//HPInit(&hp);//HPInitArray(&hp, a, sizeof(a) / sizeof(HPDataType));//for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)//{//HPPush(&hp, a[i]);//}//printf(\"%d\", HPTop(&hp));//HPPop(&hp);//for (int i = 0; i a[i]);//}return 0;}

Heap.c

Heap.h

#define _CRT_SECURE_NO_WARNINGS 1#include#include#include#include#include#includetypedef int HPDataType;typedef struct Heap{HPDataType* a;int size;int capacity;}HP;void HPInit(HP* php);void HPInitArray(HP* php, HPDataType* a, int n);void HPDestroy(HP* php);// 插入后保持数据是堆void HPPush(HP* php, HPDataType x);HPDataType HPTop(HP* php);// 删除堆顶的数据void HPPop(HP* php);void HPSort(HPDataType* a, int n);bool HPEmpty(HP* php);void AdjustUp(HPDataType* a, int child);void AdjustDown(HPDataType* a, int n, int parent);void Swap(HPDataType* px, HPDataType* py);