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

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);
}