数据结构初阶：详解二叉树（二）：堆

用户11831438

发布于 2025-12-30 13:46:23

2640

四、实现顺序结构二叉树

一般堆使用顺序结构的数组来存储数据，堆是一种特殊的二叉树，堆是一棵完全二叉树，具有二叉树的特性的同时，还具备其他的特性

4.1 堆的概念和结构

根节点最大的堆就叫最大堆（大根堆），根节点最小的堆就叫最小堆（小根堆）。

小根堆（堆顶为最小值）：

大根堆（堆顶为最大值）：

堆具有以下性质

堆中某个结点的值总是不大于或不小于其父结点的值；（若堆中的某个结点的值总是不大于其父结点的值为大堆，若堆中的某个结点的值总是不小于其父结点的值为小堆）
堆总是一棵完全二叉树

在实现堆顺序结构之前，我们要先学习二叉树的其他性质：

上图中的性质对于实现堆具有重要的作用！！！接下来，让我们一起手撕堆的代码吧。

4.2 堆的相关代码

4.2.1 堆的结构

从上面的学习中，我们发现堆的底层其实是一个数组，哦~数组，那堆的结构不就是一个顺序表的结构嘛：

typedef int HDType;//给int取个别名为HDType
typedef struct Heap
{
	HDType* arr;//存储数据的数组
	int size;//有效数据个数
	int capacity;//数组的大小
}HP;//给结构体取个别名HP

这里有个问题，有没有小伙伴知道堆有哪几种？其实堆分为以下几种：

ok，既然我们已经知道堆的结构了，那如果我们不给堆中插入任何数据，那这个堆是什么样的？这就引出了堆的初始化，堆最开始的模样其实就是一个空堆

4.2.2 堆的初始化

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

4.2.3 入堆

既然已经有了一个可以使用的空堆，那我们就可以往堆中插入数据了~~

当我们堆的空间足够时，可以进行入堆操作

但是，当堆的空间不够时，我们是不是应该对堆的空间进行增容操作，从而使堆的空间足够，这样的话，我们就可以进行插入操作了。

通过上面的学习，我们知道可以将堆分为大堆和小堆，在插入数据的过程中，堆的性质和容易遭到破坏，那我们该如何解决呢？ok，这就要轮到向上调整算法大展身手了。

4.2.3.1 向上调整算法

将新数据插入到数组的尾上，再进行向上调整算法，直到满足堆。 向上调整算法思路：

先将数据插入到堆的末尾，即最后一个孩子之后
插入之后如果堆的性质遭到破坏，比较插入的孩子结点和其父节点的大小关系，如果大于父节点，就和父节点交换，如果小于，就不交换

我么通过图形来看一下实现的过程：

1、向上调整算法建大堆

void AdjustUp(int* 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;
		}
	}
}

操作过程

2、向上调整算法建小堆

void AdjustUp(int* 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;
		}
	}
}

4.2.3.1 入堆完整代码

//向上调整算法,使其是一个大堆/小堆
void AdjustUp(int* 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;
		}
	}
	////小堆
	//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 HeapPush(HP* php, HDType num)
{
	//空间不够，需要扩容
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HDType* tmp = (HDType*)realloc(php->arr, sizeof(HDType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newcapacity;
	}
	//空间足够，直接入堆
	php->arr[php->size++] = num;
	//向上调整算法,使其是一个大堆/小堆
	AdjustUp(php->arr, php->size - 1);
}

4.2.4 出堆

在堆的结构中，实现出堆操作，一般是对堆顶数据进行出堆操作，那我们该如何操作呢？ 思路：

向将堆顶数据和堆尾数据交换，然后堆尾数据直接出堆（堆顶和堆尾互换后，堆尾为堆顶数据）
堆顶数据和堆尾数据互换后，若互换前为大堆/小堆，堆顶数据为最值，互换后，堆顶数据不为最值，需要对堆进行向下调整，使其还是一个大堆/小堆。

步骤一：

步骤一是一个很简单的操作，但是很多小伙伴看到步骤二时，就在想，这要怎么实现啊，什么是向下调整？不懂。

4.2.4.1 向下调整算法

向下调整算法有一个前提：左右子树必须是一个堆，才能进行调整

思路： 大堆： 找出堆顶左右孩子中较大的一个，比较较大孩子和父节点的大小关系，如果较大孩子大于父节点，就交换，然后让父节点走到孩子结点的位置，进行下一轮孩子结点和父节点的比较，直到孩子结点的下标不在堆的范围内，如果较大孩子小于父节点就不交换 小堆： 找出堆顶左右孩子中较小的一个，比较较小孩子和父节点的大小关系，如果较小孩子小于父节点，就交换，然后让父节点走到孩子结点的位置，进行下一轮孩子结点和父节点的比较，直到孩子结点的下标不在堆的范围内，如果较小孩子大于父节点就不交换

向下调整算法--大堆

void AdjustDown(int* arr, int parent, int size)
{
	//大堆
	int child = parent * 2 + 1;
	while (child < size)
	{
		//找出左右孩子中的较大的一个
		if (child+1<size && 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 AdjustDown(int* arr, int parent, int size)
{
	//小堆
	int child = parent * 2 + 1;
	while (child < size)
	{
		//找出左右孩子中的较小的一个
		if (child + 1 < size && arr[child] > arr[child + 1])
		{
			child++;
		}
		//比较较小孩子和父节点的大小，小就交换
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

4.2.4.2 出堆完整代码

//向下调整算法，使其还是一个大堆/小堆
void AdjustDown(int* arr, int parent, int size)
{
	//大堆
	int child = parent * 2 + 1;
	while (child < size)
	{
		//找出左右孩子中的较大的一个
		if (child+1<size && arr[child] < arr[child + 1])
		{
			child++;
		}
		//比较较大孩子和父节点的大小，大就交换
		if (arr[child] > arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}


	////小堆
	//int child = parent * 2 + 1;
	//while (child < size)
	//{
	//	//找出左右孩子中的较小的一个
	//	if (child + 1 < size && 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 HeapPop(HP* php)
{
	assert(!HeapEmpty(php));
	swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;
	//向下调整算法，使其还是一个大堆/小堆
	AdjustDown(php->arr, 0, php->size);
}

操作过程：

4.2.5 取堆顶元素

数组中下标为0处的数据为堆顶数据

//取堆顶元素
HDType HeapTop(HP* php)
{
	assert(!HeapEmpty(php));
	return php->arr[0];
}

4.2.6 判断堆是否为空

当有效数据个数为0时，说明这个堆中没有数据

//判断堆是否为空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

4.2.7 堆的销毁

void HeapDestory(HP* php)
{
	assert(php);
	if (php->arr)
	{
		free(php->arr);
	}
	php->arr = NULL;
	php->size = php->capacity = 0;
}

堆的完整代码 heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>	
typedef int HDType;
typedef struct Heap
{
	HDType* arr;
	int size;
	int capacity;
}HP;
//堆的初始化
void HeapInit(HP* php);
//入堆
void HeapPush(HP* php, HDType num);
//出堆
void HeapPop(HP* php);
//取堆顶元素
HDType HeapTop(HP* php);
//判断堆是否为空
bool HeapEmpty(HP* php);
//打印
void Print(HP* php);
//销毁
void HeapDestory(HP* php);
//向下调整算法，使其还是一个大堆/小堆
void AdjustDown(int* arr, int parent, int size);
//向上调整算法,使其是一个大堆/小堆
void AdjustUp(int* arr, int child);
void swap(int* x, int* y);

heap.c

#define _CRT_SECURE_NO_WARNINGS
#include"heap.h"
//堆的初始化
void HeapInit(HP* php)
{
	assert(php);
	php->arr = NULL;
	php->size = php->capacity = 0;
}
void swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//向上调整算法,使其是一个大堆/小堆
void AdjustUp(int* 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;
		}
	}
	///*小堆
	//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 AdjustDown(int* arr, int parent, int size)
{
	//大堆
	int child = parent * 2 + 1;
	while (child < size)
	{
		//找出左右孩子中的较大的一个
		if (child+1<size && arr[child] < arr[child + 1])
		{
			child++;
		}
		//比较较大孩子和父节点的大小，大就交换
		if (arr[child] > arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}


	////小堆
	//int child = parent * 2 + 1;
	//while (child < size)
	//{
	//	//找出左右孩子中的较小的一个
	//	if (child + 1 < size && 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 HeapPush(HP* php, HDType num)
{
	//空间不够，需要扩容
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HDType* tmp = (HDType*)realloc(php->arr, sizeof(HDType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newcapacity;
	}
	//空间足够，直接入堆
	php->arr[php->size++] = num;
	//向上调整算法,使其是一个大堆/小堆
	AdjustUp(php->arr, php->size - 1);
}
//出堆--操作的是堆顶
void HeapPop(HP* php)
{
	assert(!HeapEmpty(php));
	swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;
	//向下调整算法，使其还是一个大堆/小堆
	AdjustDown(php->arr, 0, php->size);
}
//取堆顶元素
HDType HeapTop(HP* php)
{
	assert(!HeapEmpty(php));
	return php->arr[0];
}
//判断堆是否为空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
//打印
void Print(HP* php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->arr[i]);
	}
	printf("\n");
}
//销毁
void HeapDestory(HP* php)
{
	assert(php);
	if (php->arr)
	{
		free(php->arr);
	}
	php->arr = NULL;
	php->size = php->capacity = 0;
}

test.c

#include"heap.h"
void test1()
{
	HP hp;
	HeapInit(&hp);
	HeapPush(&hp, 56);
	HeapPush(&hp, 32);
	HeapPush(&hp, 47);
	HeapPush(&hp, 25);
	HeapPush(&hp, 36);
	HeapPush(&hp, 70);
	Print(&hp);
	HeapPop(&hp);
	Print(&hp);
	int top = HeapTop(&hp);
	printf("%d\n", top);
	HeapDestory(&hp);
}
int main()
{
	test1();
	return 0;
}

ok，既然我们已经学习了堆的相关操作，接下来让博主来演示一个操作，我们对上面的test.c文件中的代码进行改写，改成下面图片中的代码：

当我们运行上面的代码时，会发生什么意想不到的情况：

😯，这怎么变成了一个有序的数组，这难道就是传说中的堆排序嘛！！！

ok啊，我们想一想，如果堆排序是这么写的，代码量是不是有点子多啊，实现一个堆排序，需要写关于堆的一系列代码，想想都可怕😨，那堆排序是怎么写的呢？

五、堆排序

堆排序借用的是堆的思想

排序思想 1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是对结构的顶端 2.将顶端的数和末尾的数交换，此时，末尾的数为最大值，剩余待排序数的个数为n-1 3.将剩余的n-1个数进行向下调整，使其还是一个大根堆，再将顶端数与n-1位置的数交换，如此重复执行，便能得到一个有序数组

注意：升序建大堆，降序建小堆

5.1 堆排序--向下调整算法

5.1.1 构建堆

如果构建大根堆呢？

首先我们给定一个无序的序列，将其看做成一个堆结构，将序列里的值按照从上往下，从左往右依次填充到二叉树中。

我们根据上面的步骤利用向下调整算法对该序列建大根堆

通过上面的操作，就将序列构建成一个大根堆。

建堆代码：

void HeapSort(int* arr, int size)
{
	//利用向下调整算法建堆
	for (int i = (size - 1 - 1)/2; i >=0; i--)
	{
		AdjustDown(arr, i, size);
	}
for (int i = 0; i < size; i++)
{
	AdjustUp(arr, i);
}
}

那我们怎么将一个大根堆变成一个有序序列呢？

步骤如下： 1、将堆顶数据和堆尾数据互换，堆尾数据出堆，然后对堆顶进行一次堆的向下调整（使其还是一个大堆），调整时被交换到最后的那个最大的数不参与向下调整（已经出堆）。 2、完成步骤1后，这棵树除最后一个数之外，其余数又成一个大堆，然后又将堆顶数据与堆的最后一个数据交换，这样一来，第二大的数就被放到了倒数第二个位置上，然后该数又不参与堆的向下调整…反复执行下去，直到堆中只有一个数据时便结束。此时该序列就是一个升序。

5.1.2 堆排序代码（建大堆）

//升序--建大堆
//使用向下调整算法
void AdjustDown(int* 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 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)//当end=0时，数据已经有序
	{
		swap(&arr[0], &arr[end]);
		end--;
		AdjustDown(arr, 0, end + 1);
	}
}
void test2()
{
	int arr[] = { 56,32,47,25,36,70 };
	int size = sizeof(arr) / sizeof(arr[0]);
	printf("排序前:");
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	HeapSort(arr, size);
	printf("\n");
	printf("排序后:");
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{   
    test2();
    return 0;
}

如果想使用向下调整算法建小堆，操作过程类似，只不过是需要找出左右孩子中的较小的，比较父节点和较小孩子结点的值，小就交换，否则不交换

5.1.3 堆排序代码--（建小堆）

//降序--建小堆
//使用向下调整算法
void AdjustDown(int* arr, int parent, int n)
{
	//小堆
    int child = parent * 2 + 1;
    while (child < size)
    {
        //找出左右孩子中的较小的一个
	    if (child + 1 < size && 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 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)//当end=0时，数据已经有序
	{
		swap(&arr[0], &arr[end]);
		end--;
		AdjustDown(arr, 0, end + 1);
	}
}
void test2()
{
	int arr[] = { 56,32,47,25,36,70 };
	int size = sizeof(arr) / sizeof(arr[0]);
	printf("排序前:");
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	HeapSort(arr, size);
	printf("\n");
	printf("排序后:");
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{   
    test2();
    return 0;
}

5.2 堆排序--向上调整算法

5.2.1 构建堆

如果使用向上调整算法建堆，我们就需要一个数据一个数据的建堆：

构建堆的代码：

void HeapSort(int* arr, int size)
{
	//利用向上调整算法建堆
	for (int i = 0; i < size; i++)
    {
	    AdjustUp(arr, i);
    }
}

5.2.2 堆排序代码--（建小堆）

//向上调整算法,使其是一个大堆/小堆
void AdjustUp(int* 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 HeapSort(int* arr, int size)
{
	//利用向上调整算法建堆
	for (int i = 0; i < size; i++)
	{
		AdjustUp(arr, i);
	}
	int end = size - 1;
	while (end > 0)
	{
		swap(&arr[0], &arr[end]);
		end--;
		AdjustDown(arr, 0, end + 1);
	}
}
void test2()
{
	int arr[] = { 56,32,47,25,36,70 };
	int size = sizeof(arr) / sizeof(arr[0]);
	printf("排序前:");
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	HeapSort(arr, size);
	printf("\n");
	printf("排序后:");
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
    test2();
    return 0;
}

5.2.3 堆排序代码--（建大堆）

//向上调整算法,使其是一个大堆/小堆
void AdjustUp(int* 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 HeapSort(int* arr, int size)
{
	//利用向上调整算法建堆
	for (int i = 0; i < size; i++)
	{
		AdjustUp(arr, i);
	}
	int end = size - 1;
	while (end > 0)
	{
		swap(&arr[0], &arr[end]);
		end--;
		AdjustDown(arr, 0, end + 1);
	}
}
void test2()
{
	int arr[] = { 56,32,47,25,36,70 };
	int size = sizeof(arr) / sizeof(arr[0]);
	printf("排序前:");
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	HeapSort(arr, size);
	printf("\n");
	printf("排序后:");
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
    test2();
    return 0;
}

5.3 时间复杂度

5.3.1 向上调整算法的时间复杂度

向上调整算法的时间复杂度：O（logn）

5.3.2 向下调整算法的时间复杂度

向下调整算法的时间复杂度：O（logn）

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

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

这时候就有同学就问了，这是什么原因造成的？

建议使用向下调整算法建堆！！！

5.3.5 堆排序的时间复杂度

综上所知：

六、TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，⼀般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。

最佳的方式就是用堆来解决，基本思路如下： 1、从数据中提取K个数据进行建堆

前K个最大数据，建小堆；
前K个最小数据，建大堆

2、遍历剩余的n-k个数据，将n-k个数据依次与堆顶元素进行比较，不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素

ok，通过上面的思路，我们就知道如何解决一个TOP-K问题了。

以前K个最大数据，建小堆为例

第一步，创建n个数据 由于数据量比较庞大，所以我们需要将数据保存在文件中

利用随机数的生成，在文件中随机生成n个数据。

第二步：从数据文件中提取k个数据，建小堆

第三步：剩余的n-k个数据依次与堆顶数据比较，比堆顶数据小就替换堆顶数据，然后进行向下调整，使其还是一个小堆。

第四步：打印数据

完整代码：

//TOP-K问题

//交换代码
void swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//向下调整算法，使其还是一个大堆/小堆
void AdjustDown(int* arr, int parent, int size)
{
	//小堆
	int child = parent * 2 + 1;
	while (child < size)
	{
		//找出左右孩子中的较小的一个
		if (child + 1 < size && 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 CreateData()
{
	int n = 1000;
	srand(time(0));
	FILE* pf = fopen("data.txt", "w");
	if (pf == NULL)
	{
		perror("fopen fail!");
		exit(1);
	}
	for (int i = 0; i < n; i++)
	{
		int data = rand() % n + 1;
		fprintf(pf, "%d\n", data);
	}
}

void test3()
{
	//第一步：创建数据
	//CreateData();

	//第二步：从数据文件中提取k个数据，建小堆
	int k = 0;
	printf("k= ");
	scanf("%d", &k);
	int* DataBase = (int*)malloc(sizeof(int) * k);
	if (DataBase == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	FILE* pf = fopen("data.txt", "r");
	if (pf == NULL)
	{
		perror("fopen fail!");
		exit(2);
	}
	for (int i = 0; i < k; i++)
	{
		fscanf(pf, "%d", &DataBase[i]);
	}
	//使用向下调整算法建堆
	for (int i = (k-1-1)/2; i >= 0; i--)
	{
		AdjustDown(DataBase, i, k);
	}

	//第三步：剩余的n-k个数据依次与堆顶数据比较，
	// 比堆顶数据小就替换堆顶数据，然后进行向下调整
	int data = 0;
	while (fscanf(pf, "%d", &data) != EOF)
	{
		if (data > DataBase[0])
		{
			DataBase[0] = data;
			AdjustDown(DataBase, 0, k);
		}
	}


	//第四步：打印数据
	for (int i = 0; i < k; i++)
	{
		printf("%d ", DataBase[i]);
	}
}
int main()
{
	test3();
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-18，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构