愿所有美好如期而遇
目录
堆的介绍：
首先，堆是不完全二叉树。
不完全二叉树：除了最后一层外，其他层每一层都是满的，最后一层节点从左到右排。
再者，堆分为大堆和小堆。
大堆：父母节点的值大于等于孩子节点
小堆：父母节点的值小于等于孩子节点
关于堆的实现及相关的其他问题：
我们在主函数中将定义一个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也为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--;
}求堆顶数据：
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) / 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)。
