愿所有美好如期而遇
目录
堆的介绍：
首先，堆是不完全二叉树。
不完全二叉树：除了最后一层外，其他层每一层都是满的，最后一层节点从左到右排。
再者，堆分为大堆和小堆。
大堆：父母节点的值大于等于孩子节点
小堆：父母节点的值小于等于孩子节点
关于堆的实现及相关的其他问题：
我们在主函数中将定义一个Heap hp;
typedef int Heaptype; typedef struct Heap { Heaptype* data; int size; int capacity; }Heap; //堆的初始化 void HeapInit(Heap* php); //堆的销毁 void HeapDestroy(Heap* php); //插入建堆 void HeapPush(Heap* php, Heaptype num); //堆向上调整 void Ajustup(Heaptype* a, int child); //交换两个节点的值 void Swap(Heaptype* p1, Heaptype* p2); //堆向下调整 void AjustDown(Heaptype* a, int n, int parent); //删除根节点 void HeapPop(Heap* php); //求得堆顶数据 Heaptype HeapTop(Heap* php); //打印堆的每一个节点的值 void HeapPrint(Heaptype* arr, int size); //堆排序 void HeapSort(Heaptype* arr, int size); //堆的节点数量 void HeapSize(Heap* php); //判读堆是否为空 void HeapEmpty(Heap* php); //创建一个多数据文件 void CreateNDate(); //TopK问题 void PrintTopK(int k);
堆的初始化：
1. void HeapInit(Heap* php) 2. { 3. assert(php); 4. 5. php->data = NULL; 6. php->size = 0; 7. php->capacity = 0; 8. }
堆的销毁：
void HeapDestroy(Heap* php) { assert(php); free(php->data); php->data = NULL; php->size = 0; php->capacity = 0; }
插入建堆：
void HeapPush(Heap* php, Heaptype num) { assert(php); if (php->size == php->capacity) { int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2; Heaptype* temp = (Heaptype*)realloc(php->data, sizeof(Heaptype) * newcapacity); if (temp == NULL) { perror("realloc fail"); printf("\n%s", __LINE__); } php->data = temp; php->capacity = newcapacity; } php->data[php->size++] = num; //插入后当即向上调整，以保证还是个堆 Ajustup(php->data, php->size - 1); }
堆向上调整：
//堆向上调整，调整一轮，建堆就循环插入去建 void Ajustup(Heaptype* a, int child) { int parent = (child - 1) / 2; //当child == 0 的时候，parent也为0 while (child > 0) { if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } }
交换两个节点的值：
void Swap(Heaptype* p1, Heaptype* p2) { Heaptype temp = *p1; *p1 = *p2; *p2 = temp; }
堆向下调整：
//堆向下调整 void AjustDown(Heaptype* a, int n, int parent) { //从叶子节点开始 int child = parent * 2 + 1; while (child < n) { //找出最小孩子 if (child + 1 < n && a[child] > a[child + 1]) { child++; } else { if (a[parent] > a[child]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } }
删除根节点：
void HeapPop(Heap* php) { assert(php); assert(php->size > 0); Swap(&php->data[0], &php->data[php->size - 1]); AjustDown(php->data, php->size - 1, 0); php->size--; }
求堆顶数据：
1. Heaptype HeapTop(Heap* php) 2. { 3. assert(php); 4. 5. return php->data[0]; 6. }
打印堆的每一个节点的值：
void HeapPrint(Heaptype* arr, int size) { assert(arr); for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } }
堆排序：
void HeapSort(Heaptype* arr, int size) { assert(arr); //向上调整建堆(小堆) /*int num = size; for (int i = 0; i < num; i++) { Ajustup(arr, i); }*/ //向下调整建堆 int last = (size - 1 - 1) / 2; for (int i = last; i >= 0; i--) { AjustDown(arr, size, i); } //排序 int end = size - 1; while (end > 0) { Swap(&arr[0], &arr[end]); AjustDown(arr, end, 0); end--; } }
堆的节点数量：
1. void HeapSize(Heap* php) 2. { 3. assert(php); 4. 5. return php->size; 6. }
判断堆是否为空：
1. void HeapEmpty(Heap* php) 2. { 3. assert(php); 4. 5. return php->size == 0; 6. }
创建一个多数据文件：
void CreateNDate() { int n = 10000; srand((unsigned int)time(NULL)); const char* file = "heap.txt"; FILE* pf = fopen(file, "w"); { if (pf == NULL) { perror("fopen fail"); return; } } for (int i = 0; i < n; i++) { int num = rand() % 1000000; fprintf(pf, "%d\n", num); } fclose(pf); }
TopK问题(综合)：
void PrintTopK(int k) { Heaptype* arr = (Heaptype*)malloc(sizeof(Heaptype) * k); if (arr == NULL) { perror("malloc fail"); return; } FILE* pf = fopen("heap.txt", "r"); if (pf == NULL) { perror("fopen fail"); return; } for (int i = 0; i < k; i++) { fscanf(pf, "%d", &arr[i]); } //调整为小堆 int n = (k - 1 - 1) / 2; for (int i = n; i >= 0; i--) { AjustDown(arr, k, i); } //由于我们建1的是大小为k的堆，堆顶的数值最小，当新的数据大于堆 //顶时，进堆，而堆顶的数据被替换，之后堆向下调整 int a = 0; while (fscanf(pf, "%d", &a) != EOF) { if (a > arr[0]) { arr[0] = a; AjustDown(arr, k, 0); } } //此时堆里的数据是最大的k个数 for (int i = 0; i < k; i++) { printf("%d ", arr[i]); } fclose(pf); free(arr); }
向上/向下调整建堆哪个时间复杂度更优秀？
答案是堆向下调整，时间复杂度为O(N),堆向上调整时间复杂度为O(N*logN)。
