【数据结构】堆(Heap):堆的实现、堆排序、TOP-K问题

堆的概念及结构

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。

小根堆：父亲节点大于等于孩子节点

大根堆：父亲节点小于等于孩子节点 

堆的实现 

实现堆的接口

#define CRT_SECURE_NO_WARNING 1
#pragma once
#include
#include
#include
#include
#include
 
//二叉树-堆
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
 
 
void AdjustUp(HPDataType* a, int child);
 
void AdjustDown(HPDataType* a, int n, int parent);
 
//交换
void Swap(HPDataType* p1, HPDataType* p2);
//打印
void HeapPrint(HP* php);
//初始化
void HeapInit(HP* php);
//
void HeapInitArray(HP* php, int* a, int n);
//销毁
void HeapDestroy(HP* php);
//插入
void HeapPush(HP* php, HPDataType x);
//删除
void HeapPop(HP* php);
//返回最顶数据
HPDataType HeapTop(HP* php);
//判空
bool HeapEmpty(HP* php);

堆的初始化

//初始化
void HeapInit(HP* php)
{
	assert(php);
 
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

堆的打印

void HeapPrint(HP* php)
{
	assert(php);
 
	//最后一个孩子下标为size-1
	for (size_t i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

堆的销毁

//销毁
void HeapDestroy(HP* php)
{
	assert(php);
 
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

获取最顶的根数据

//获取根数据
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
 
	return php->a[0];
}

 交换

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

堆的插入（插入最后）

先考虑扩容，将数据插到最后，再用向上调整法。

//插入数据
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
 
	//扩容
	if (php->size == php->capacity)//有效元素个数和容量是否相等
	{
		//相等的情况分两种：1.容量为0，先扩4个sizeof   2.容量占用满了,扩2个
		int newCapacity =php->capacity == 0 ? 4 : php->capacity * 2;
		//返回扩容后的内存新地址							//扩容后的新大小
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
		
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
 
		//扩容后的新地址
		php->a = tmp;
		//新容量
		php->capacity = newCapacity;
	}
 
	//   php->size下标位置  先将x放最后，后面再调整
	php->a[php->size] = x;
	//   有效数据++
	php->size++;
	//   向上调整     //size-1为新插入数据的下标
	AdjustUp(php->a, php->size - 1);
 
}

向上调整（这次用的是小堆）

向上调整的前提：左右子树是堆 ，时间复杂度O(logN)

//向上调整                    //新插入的数据下标
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 HeapPop(HP* php)
{
	assert(php);
	//确保有元素可删
	assert(php->size > 0);
 
	//最后一个孩子和要删除的根交换
	Swap(&php->a[0], &php->a[php->size - 1]);
	//有效元素size减减，相当于删除了交换后的原来的根
	--php->size;
 
	//删除后向下调整
	AdjustDown(php->a, php->size, 0);
 
}

向下调整（这次用的小堆）

向下调整的前提：左右子树是堆 

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	//n下标位置已经没有数了
	while (child < n)
	{
		//选小的孩子往上浮（小堆）
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}
		//若小的孩子都小于父，则交换
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//交换后下来的数重新变成parent，继续向下调整
			parent = child;
			child = parent * 2 + 1;
		}
	}
}

堆排序

void HeapSort(int* a, int n)
{
	//建堆  这里可以选建大堆还是小堆
	// 向下调整建堆
	// O(N)
	for (int i = (n-1-1)/2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
 
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

TOP-K问题

先创建一个包含有10000000个数的data.txt文本文件。

void CreateNDate()
{
	// 造数据
	int n = 10000000;
	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) % 10000000;
		fprintf(fin, "%d\n", x);
	}
 
	fclose(fin);
}

前k个建小堆（堆顶元素为k中最小），剩余n-k个依次和堆顶元素比较，比k大就插入堆中（插入堆插入向下调整法），完成后打印前k个元素。

void PrintTopK(const char* filename, int k)
{
	// 1. 建堆--用a中前k个元素建堆
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}
 
	//给堆开辟空间
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		return;
	}
 
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}
 
	// 前k个数建小堆
	for (int i = (k - 2) / 2; i >= 0; --i)
	{
		AdjustDown(minheap, k, i);
	}
 
 
	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	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]);
	}
	printf("\n");
 
	free(minheap);
	fclose(fout);
}

假设k等于5，成功打印出前5个最大的数据