四、建堆的时间复杂度
建堆的时间复杂度如下：
通过上图的分析及推算，建堆的时间复杂度为O(N)
五、源代码
Heap.h
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> #include <time.h> typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP; //堆的初始化 void HeapInit(HP* hp); //堆的销毁 void HeapDestroy(HP* hp); //堆的数据打印 void HeapPrint(HP* hp); //堆的数据交换 void Swap(HPDataType* px, HPDataType* py); //向上调整 void AdjustUp(int* a, int child); //向下调整 void AdjustDown(int* a, int n, int parent); //堆的数据插入 void HeapPush(HP* hp, HPDataType x); //堆的数据删除 void HeapPop(HP* hp); //取堆顶的数据 HPDataType HeapTop(HP* hp); //堆的数据个数 int HeapSize(HP* hp); //堆的判空 bool HeapEmpty(HP* hp);
Heap.c
#include "Heap.h" //堆的初始化 void HeapInit(HP* hp) { assert(hp); hp->a = NULL; hp->capacity = hp->size = 0; } //堆的销毁 void HeapDestroy(HP* hp) { assert(hp); free(hp->a); hp->capacity = hp->size = 0; } //堆的数据打印 void HeapPrint(HP* hp) { assert(hp); for (int i = 0; i < hp->size; i++) { printf("%d ", hp->a[i]); } printf("\n"); } //堆的数据交换 void Swap(HPDataType* px, HPDataType* py) { HPDataType tmp = *px; *px = *py; *py = tmp; } //向上调整（大堆用大于，小堆用小于） void AdjustUp(int* a, int child) { assert(a); int parent = (child - 1) / 2; while (child > 0) { if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } //向下调整（大堆用大于，小堆用小于） void AdjustDown(int* a, int n, int parent) { assert(a); int child = parent * 2 + 1; while (child < n) { //选出左右孩子中小的那个 if (child + 1 < n && a[child + 1] > a[child]) { ++child; } //如果小的孩子小于父亲，则交换，并继续向下调整 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } //堆的数据插入 void HeapPush(HP* hp, HPDataType x) { assert(hp); if (hp->size == hp->capacity) { size_t newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2; HPDataType* tmp = realloc(hp->a, sizeof(HPDataType) * newcapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } hp->a = tmp; hp->capacity = newcapacity; } hp->a[hp->size] = x; hp->size++; AdjustUp(hp->a, hp->size - 1); } //堆的数据删除 void HeapPop(HP* hp) { assert(hp); assert(!HeapEmpty(hp)); Swap(&hp->a[0], &hp->a[hp->size - 1]); hp->size--; AdjustDown(hp->a, hp->size, 0); } //取堆顶的数据 HPDataType HeapTop(HP* hp) { assert(hp); assert(!HeapEmpty(hp)); return hp->a[0]; } //堆的数据个数 int HeapSize(HP* hp) { assert(hp); return hp->size; } //堆的判空 bool HeapEmpty(HP* hp) { assert(hp); return hp->size == 0; }
test.c
#include "Heap.h" void PrintTopK(int* a, int n, int k) { // 1. 建堆--用a中前k个元素建堆 // 2. 将剩余n-k个元素依次与堆顶元素交换，不满足则替换 HP hp; HeapInit(&hp); //创建一个k个数的小堆 for (int i = 0; i < k; ++i) { HeapPush(&hp,a[i]); } //剩下的N-K个数跟堆顶的数据比较，比他大就替换他进堆 for (int i = k; i < n; ++i) { if (a[i] > HeapTop(&hp)) { /*HeapPop(&hp); HeapPush(&hp, a[i]);*/ hp.a[0] = a[i]; AdjustDown(hp.a, hp.size, 0); } } HeapPrint(&hp); HeapDestroy(&hp); } //在N个数中找出最大的前k个 or 在N个数中找出最小的前k个 void TestTopk() { int n = 10000; int* a = (int*)malloc(sizeof(int) * n); srand(time(0)); for (size_t i = 0; i < n; ++i) { a[i] = rand() % 1000000; } //再去设置10个比100w大的数 a[5] = 1000000 + 1; a[1231] = 1000000 + 2; a[531] = 1000000 + 3; a[5121] = 1000000 + 4; a[115] = 1000000 + 5; a[2335] = 1000000 + 6; a[9999] = 1000000 + 7; a[76] = 1000000 + 8; a[423] = 1000000 + 9; a[3144] = 1000000 + 10; PrintTopK( a, n, 10); } void TestHeap() { int a[] = { 70,56,30,25,15,10,75 }; HP hp; HeapInit(&hp); for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) { HeapPush(&hp, a[i]); } HeapPrint(&hp); HeapPop(&hp); HeapPrint(&hp); HeapDestroy(&hp); } //排升序建大堆 排降序建小堆 //堆排序 void HeapSort(int* a, int n) { assert(a); //把a数组构建成堆（假设构建成小堆） //方法1 // //for (int i = 1; i < n; i++) //{ // AdjustUp(a, i); //} //方法2 //O(N) for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } for (int i = 0; i < 7; ++i) { printf("%d ", a[i]); } printf("\n"); //移除选数，调堆 //O(N*logN) for (int end = n - 1; end > 0; --end) { Swap(&a[end], &a[0]); //再调堆，选出次小的数 AdjustDown(a, end, 0); } } int main() { //TestHeap(); //TestTopk(); int a[] = { 70,56,30,25,15,10,75 }; for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) { printf("%d ", a[i]); } printf("\n"); HeapSort(a, sizeof(a) / sizeof(a[0])); for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) { printf("%d ", a[i]); } printf("\n"); return 0; }
