堆的介绍与堆的实现和调整

个人主页：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)。

---