堆的介绍与堆的实现和调整
个人主页：Lei宝啊
愿所有美好如期而遇
目录
堆的介绍：
关于堆的实现及相关的其他问题：
堆的初始化：
堆的销毁：
插入建堆：
堆向上调整：
交换两个节点的值：
堆向下调整：
删除根节点：
求堆顶数据：
打印堆的每一个节点的值：
堆排序：
堆的节点数量：
判断堆是否为空：
创建一个多数据文件：
TopK问题(综合)：
向上/向下调整建堆哪个时间复杂度更优秀？
堆的介绍：
首先，堆是不完全二叉树。
不完全二叉树：除了最后一层外，其他层每一层都是满的，最后一层节点从左到右排。
再者，堆分为大堆和小堆。
大堆：父母节点的值大于等于孩子节点
小堆：父母节点的值小于等于孩子节点
关于堆的实现及相关的其他问题：
我们在主函数中将定义一个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);堆的初始化：
void HeapInit(Heap* php)
{assert(php);php->data = NULL;php->size = 0;php->capacity = 0;
}
堆的销毁：
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也为0while (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--;
}求堆顶数据：
Heaptype HeapTop(Heap* php)
{assert(php);return php->data[0];
}打印堆的每一个节点的值：
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--;}
}堆的节点数量：
void HeapSize(Heap* php)
{assert(php);return php->size;
}判断堆是否为空：
void HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}创建一个多数据文件：
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)。
