一文彻底搞清楚二叉树和堆：从概念到存储结构解析

#include"Heap.h"
//初始化堆
void HPInit(HP* php)
{
	php->arr = NULL;
	php->size = php->capacity = 0;
}
//堆的销毁
void HPDestroy(HP* php)
{
	if (php->arr)
		free(php->arr);
	php->arr = NULL;
	php->size = php->capacity = 0;
}
//堆的打印
void HPPrint(HP* php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->arr[i]);
	}
	printf("\n");
}
//孩子结点和父结点交换
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		//大堆：>
		//小堆：<
		if (arr[child] > arr[parent])
		{
			//调整
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}
//堆的插入
void HPPush(HP* php, HPDataType x)
{
	assert(php);
	//判断空间是否足够
	if (php->size == php->capacity)
	{
		int newCapcity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapcity*sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newCapcity;
	}
	php->arr[php->size] = x;
	AdjustUp(php->arr, php->size);
	++php->size;
}
// 判空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{
	int child = parent * 2 + 1;//左孩子
	while (child < n)
	{
		//大堆：<
		//小堆：>
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}
		//大堆: >
		//小堆：<
		if (arr[child] > arr[parent])
		{
			//调整
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}
//删除堆顶元素
void HPPop(HP* php)
{
	assert(!HPEmpty(php));
	// 0 php->size-1
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	--php->size;
	//向下调整
	AdjustDown(php->arr, 0, php->size);
}

//取堆顶数据
HPDataType HPTop(HP* php)
{
	assert(!HPEmpty(php));
	return php->arr[0];
}
//求size
int HPSize(HP* php)
{
	assert(php);
	return php->size;
}

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//堆的结构
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* arr;
	int size;     //有效数据个数
	int capacity; //空间大小
}HP;
void Swap(int* x, int* y);
void AdjustUp(HPDataType* arr, int child);
void AdjustDown(HPDataType* arr, int parent, int n);
void HPInit(HP* php);
void HPDestroy(HP* php);
void HPPrint(HP* php);
void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);
//取堆顶数据
HPDataType HPTop(HP* php);
// 判空
bool HPEmpty(HP* php);
int HPSize(HP* php);

#include"Heap.h"
void arrPrint(int* arr,int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
//堆排序
void HeapSort1(int* arr, int n)
{
	HP hp; //——————借助数据结构堆来实现堆排序
	HPInit(&hp);
	for (int i = 0; i < n; i++)
	{
		HPPush(&hp, arr[i]);
	}
	int i = 0;
	while (!HPEmpty(&hp))
	{
		int top = HPTop(&hp);
		arr[i++] = top;
		HPPop(&hp);
	}
    HPDestroy(&hp);
}
void HeapSort(int* arr, int n)
{
	//建堆——向下调整算法建堆
	for (int i = (n-1-1)/2; i>=0; i--)
	{
		AdjustDown(arr, i, n);
	}
	//堆排序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
}
void test01()
{
	HP hp;
	HPInit(&hp);
	HPPush(&hp, 56);
	HPPush(&hp, 10);
	HPPush(&hp, 15);
	HPPush(&hp, 30);
	HPPush(&hp, 70);
	HPPush(&hp, 25);
	HPPrint(&hp);
	HPPop(&hp);
	HPPrint(&hp);
	HPPop(&hp);
	HPPrint(&hp);
	HPPop(&hp);
	HPPrint(&hp);
	HPPop(&hp);
	HPPrint(&hp);
    HPDestroy(&hp);
}
void test02()
{
	HP hp;
	HPInit(&hp);
    HPPush(&hp, 56);
	HPPush(&hp, 10);
	HPPush(&hp, 15);
	HPPush(&hp, 30);
	HPPrint(&hp);
    while (!HPEmpty(&hp))
	{
		int top = HPTop(&hp);
		printf("%d ", top);
		HPPop(&hp);
	}
    HPDestroy(&hp);
}
int main()
{
	test01();
	test02();
	int arr[6] = {19,15,20,17,13,10};
	printf("排序之前：");
	arrPrint(arr, 6);
    //堆排序
	HeapSort(arr, 6);
    printf("排序之后：");
	arrPrint(arr, 6);
	return 0;
}

void AdjustUp(HPDataType* a, int child)
 {
 int parent = (child - 1) / 2;
 while(child > 0)
 {
 if (a[child] > a[parent])
 {
 Swap(&a[child], &a[parent]);
 child = parent;
 parent = (parent - 1) / 2;
 }
 else
 {
 break;
 }
 }
 }
 void HPPush(HP* php, HPDataType x)
 {
 assert(php);
 if (php->size == php->capacity)
 {
 size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
 HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
 if (tmp == NULL)
 {
 perror("realloc fail");
 return;
 }
 php->a = tmp;
 php->capacity = newCapacity;
 }
 php->a[php->size] = x;
 php->size++;
 AdjustUp(php->a, php->size-1);
 }

void AdjustDown(HPDataType* arr, int parent, int n)
{
	int child = parent * 2 + 1;//左孩子
	while (child < n)
	{
		//大堆：<
		//小堆：>
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}
		//大堆: >
		//小堆：<
		if (arr[child] > arr[parent])
		{
			//调整
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}
void HPPop(HP* php)
{
	assert(!HPEmpty(php));
	// 0 php->size-1
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	--php->size;
	//向下调整
	AdjustDown(php->arr, 0, php->size);
}

// 1、需要堆的数据结构
// 2、空间复杂度 O(N)
void HeapSort(int* a, int n)
{
HP hp;
for(int i = 0; i < n; i++)
{
HPPush(&hp,a[i]);
}
int i = 0;
while (!HPEmpty(&hp))
{
a[i++] = HPTop(&hp);
HPPop(&hp);
}
HPDestroy(&hp);
}

// 排升序，建⼤堆
// 排降序，建⼩堆
// O(N*logN)
void HeapSort(int* a, int n)
{
 // a数组直接建堆 O(N)
 for (int i = (n-1-1)/2; i >= 0; --i)
 {
 AdjustDown(a, n, i);
 }
 // O(N*logN)
 int end = n - 1;
 while (end > 0)
 {
 Swap(&a[0], &a[end]);
 AdjustDown(a, end, 0);
 --end;
 }
 }

void CreateNDate()
 {
 // 造数据
 int n = 100000;
 srand(time(0));
 const char* file = "data.txt";
 FILE* fin = fopen(file, "w");
 if (fin == NULL)
 {
 perror("fopen error");
 return;
 }
 for (int i = 0; i < n; ++i)
 {
 int x = (rand()+i) % 1000000;
 fprintf(fin, "%d\n", x);
 }
 fclose(fin);
 }
 void topk()
 {
 printf("请输⼊k：>");
 int k = 0;
 scanf("%d", &k);
 const char* file = "data.txt";
 FILE* fout = fopen(file, "r");
 if (fout == NULL)
 {
 perror("fopen error");
 return;
 }
 int val = 0;
 int* minheap = (int*)malloc(sizeof(int) * k);
 if (minheap == NULL)
 {
 perror("malloc error");
 return;
 }
 for (int i = 0; i < k; i++)
 {
 fscanf(fout, "%d", &minheap[i]);
 }
 // 建k个数据的⼩堆
 for (int i = (k - 1 - 1) / 2; i >= 0; i--)
 {
 AdjustDown(minheap, k, i);
 }
 int x = 0;
 while (fscanf(fout, "%d", &x) != EOF)
 {
 // 读取剩余数据，⽐堆顶的值⼤，就替换他进堆
 if (x > minheap[0])
 {
 minheap[0] = x;
 AdjustDown(minheap, k, 0);
 }
 }
 for (int i = 0; i < k; i++)
 {
 printf("%d ", minheap[i]);
 }
 fclose(fout);
 }