数据结构与算法——堆

struct TreeNode 
{ 
 struct Node* child; // 左边开始的第⼀个孩⼦结点 
 struct Node* brother; // 指向其右边的下⼀个兄弟结点 
 int data; // 结点中的数据域 
};

//交换数据
void swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//向上调整算法  判断条件：小堆：child < parent      大堆：child > parent
void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0) //child向上调整到祖先结点停止循环
	{
		if (arr[child] > arr[parent])   //判断条件：小堆：child < parent      大堆：child > parent
		{
			swap(&arr[child], &arr[parent]);  
			child = parent;  //向上调整，所以把子结点下标变成父结点下标
			parent = (child - 1) / 2;//向上找父结点
		}
		else {
			break;
		}
	}
}

//堆的插入
void HPPush(HP* php, HPDataType x)
{
	assert(php);
	//判断空间是否足够
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->arr, newcapacity*sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newcapacity;
	}
	php->arr[php->size] = x;
	AdjustUp(php->arr,php->size);
	++php->size;
}

//判空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
// 向下调整算法 小堆：parent > child  arr[child] > arr[child + 1] 大堆：parent < child   arr[child] < arr[child + 1]
void AdjustDown(HPDataType* arr, int parent, int n)
{
	int child = parent * 2 + 1;  //左孩子
	while(child < n )    //n为最大结点个数，不能越界
	{ 
		if (arr[child] < arr[child + 1] && child + 1 < n) //演示大堆，拿子孩子中大的能够和父亲比较，且确保有右孩子
		{
			child++;   //左孩子小于右孩子，将child = child + 1，(大堆)大的和父亲比较
		}
		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)); //检查堆是否有元素（非空堆）。
	swap(&php->arr[0], &php->arr[php->size - 1]);  //交换最后一个子节点和祖先节点的值
	--php->size;
	//向下调整
	AdjustDown(php->arr, 0 , php->size);
}

void tes02()
{
	HP hp;
	HPInit(&hp);

	HPPush(&hp, 56);
	HPPush(&hp, 10);
	HPPush(&hp, 15);
	HPPush(&hp, 30);
	HPPush(&hp, 70);
	HPPush(&hp, 25);
	HPPrint(&hp);

	while (!HPEmpty(&hp)) //如果堆不为空
	{
		int top = HPTop(&hp); //循环取堆顶元素
		printf("%d ", top); //打印
		HPPop(&hp);//出堆顶元素
	}
	HPDestroy(&hp);
}

1. 建堆操作，向下调整
从最后一棵子树开始调整，然后调整parent--继续调整

//堆排序
void HPSort(int* arr, int n)
{
	//建堆，向下调整算法
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)  //初始值就是最后一棵子树，n-1为最后一个子结点，再减1除2就是其父结点也就最后一棵子树开始
	{
		AdjustDown(arr,i,n);
	}
}

2.将堆顶和最后一个数据交换位置，--size，向下调整堆，继续重复该过程

//堆排序
void HPSort(int* arr, int n)
{
	//建堆，向下调整算法
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)  //初始值就是最后一棵子树，n-1为最后一个子结点，再减1除2就是其父结点也就最后一棵子树开始
	{
		AdjustDown(arr,i,n);
	}

	//堆排序
	int end = n - 1; //最后位置一个结点
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		--end;
	}

}

//建堆，向上调整算法
for (int i = 0; i < n; i++)
{
	AdjustUp(arr,i);
}

计算向上调整算法建堆时间复杂度

计算向下调整算法建堆时间复杂度

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()
{
	int k = 0;
	printf("请输入K:");
	scanf_s("%d", &k);

	const char* file = "data.txt";
	FILE* fout = fopen(file,"r");
	if (fout == NULL)
	{
		perror("fopen fail!");
		exit(1);
	}
	//找最大的前K个数据，建小堆
	int* minHeap = (int*)malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{
		perror("malloc fail!");
		exit(2);
	}
	for (int i = 0; i < k; i++)
	{
		fscanf_s(fout, "%d",&minHeap[i]);//保存到申请的数组空间
	}
	//minHeap目前并不是堆结构    所以向下调整建堆（时间复杂度更小）
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minHeap,i,k);
	}
	//建堆后，遍历剩下的n-k个数据，与堆顶进行比较，大于堆顶元素则替换
	int x = 0;//将剩下的数据保存到x里面
	while (fscanf_s(fout, "%d", &x) != EOF)
	{
		//x与堆顶数据比较
		if (x > minHeap[0])
		{
			minHeap[0] = x;//但是此时不是有效堆结构
			AdjustDown(minHeap, 0, k);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}
	fclose(fout);
}

int main()
{
	TopK();
	return 0;
}

时间复杂度：O(n) = k + (n − k)log2k