1. Toy模板网首页
  2. > Toy博客

数据结构从入门到精通——堆

8月前 作者：鲜于言悠905 分类：Toy博客 阅读(43) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构从入门到精通——堆。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

堆是一种特殊的树形数据结构，具有完全二叉树的特性。在堆中，父节点的值总是大于或等于（大顶堆）或小于或等于（小顶堆）其子节点的值。堆通常用于实现优先队列，其中每个元素都有一个优先级，优先级最高的元素总是位于堆的根节点。堆的插入和删除操作的时间复杂度都是O(log n)，因此堆是一种高效的数据结构。此外，堆还可以用于实现内存管理，例如垃圾回收和内存分配等。

一、二叉树的顺序结构及实现 (堆）

1.1二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
数据结构从入门到精通——堆,数据结构从入门到精通,数据结构,算法,c语言,leetcode,r-tree,lsm-tree,suffix-tree

1.2堆的概念及结构

如果有一个关键码的集合K = {K0 ，K1 ，K2 ，…，Kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <=K2*i+1 且Ki <=K2*i+2 ( Ki>=K2*i+1 且Ki >= K2*i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

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

数据结构从入门到精通——堆,数据结构从入门到精通,数据结构,算法,c语言,leetcode,r-tree,lsm-tree,suffix-tree

二、堆的练习题

  1. 下列关键字序列为堆的是：（）
    A、 100,60,70,50,32,65
    B 、60,70,65,50,32,100
    C、 65,100,70,32,50,60
    D、 70,65,100,32,50,60
    E、 32,50,100,70,65,60
    F 、50,100,70,65,60,32

  2. 已知小根堆为8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（）。
    A 、1
    B、 2
    C 、3
    D 、4

  3. 一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为
    A、(11 5 7 2 3 17)
    B、(11 5 7 2 17 3)
    C、(17 11 7 2 3 5)
    D、(17 11 7 5 3 2)
    E、(17 7 11 3 5 2)
    F、(17 7 11 3 2 5)

  4. 最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是（）
    A、[3，2，5，7，4，6，8]
    B、[2，3，5，7，4，6，8]
    C、[2，3，4，5，7，8，6]
    D、[2，3，4，5，6，7，8]

答案

1.A
2.C
3.C
4.C

三、堆的实现

3.1堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

数据结构从入门到精通——堆,数据结构从入门到精通,数据结构,算法,c语言,leetcode,r-tree,lsm-tree,suffix-tree

3.2堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

int a[] = {1,5,3,8,7,6};

数据结构从入门到精通——堆,数据结构从入门到精通,数据结构,算法,c语言,leetcode,r-tree,lsm-tree,suffix-tree

3.3建堆时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

数据结构从入门到精通——堆,数据结构从入门到精通,数据结构,算法,c语言,leetcode,r-tree,lsm-tree,suffix-tree
因此：建堆的时间复杂度为O(N)。

3.4堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

数据结构从入门到精通——堆,数据结构从入门到精通,数据结构,算法,c语言,leetcode,r-tree,lsm-tree,suffix-tree

3.5堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

数据结构从入门到精通——堆,数据结构从入门到精通,数据结构,算法,c语言,leetcode,r-tree,lsm-tree,suffix-tree

3.6堆的代码实现

typedef int HPDataType;
typedef struct Heap
{
 	HPDataType* _a;
 	int _size;
 	int _capacity; 
}Heap;
 
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

四、堆的具体实现代码

Heap.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int capacity;
	int size;
}HP;

void Swap(HPDataType* a, HPDataType* b);//数据交换函数
void AdjustUp(HPDataType* a, int child);//向上交换
void AdjustDown(HPDataType* a, int n,int parent);//向下交换
//堆的初始化
void HPInit(HP* php);
//堆的销毁
void HPDestroy(HP* php);

//插入数据
void HPPush(HP* php,HPDataType x);

HPDataType HPTop(HP* php);//堆顶元素
//删除堆顶元素
void HPPop(HP* php);
bool HPEmpty(HP* php);

Heap.c

#include "Heap.h"
void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity =  php->size = 0;
}
void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}
void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType temp = *a;
	*a = *b;
	*b = temp;
}
void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		size_t newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* newnode = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);
		if (newnode == NULL)
		{
			perror("newnode realloc : ");
			return;
		}
		php->a = newnode;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);
}
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 HPPop(HP* php)
{
	assert(php);
	assert(!HPEmpty(php));
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent* 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
HPDataType HPTop(HP* php)
{
	assert(php);
	return php->a[0];
}
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

Test.c

#include"Heap.h"

int main()
{
	//int a[] = { 50,100,70,65,60,32 };
	int a[] = { 60,70,65,50,32,100 };

	HP hp;
	HPInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&hp, a[i]);
	}

	printf("%d\n", HPTop(&hp));
	HPPop(&hp);
	printf("%d\n", HPTop(&hp));
	while (!HPEmpty(&hp))
	{
		printf("%d\n", HPTop(&hp));
		HPPop(&hp);
	}

	HPDestroy(&hp);

	return 0;
}

堆的初始化

//堆的初始化
void HPInit(HP* php);

void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity =  php->size = 0;
}

堆是一种特殊的树形数据结构，通常用于实现优先队列。在初始化堆时，需要按照一定规则将元素填充到堆中。一般来说，堆的初始化可以采用从上到下、从左到右的方式遍历数组，对于每个非叶子节点，将其与其子节点中较大的一个进行交换，确保父节点的值不小于其子节点的值，从而满足堆的性质。这种操作被称为堆化或调整。通过遍历整个数组并进行堆化操作，最终可以得到一个满足堆性质的堆结构。

堆的销毁

//堆的销毁
void HPDestroy(HP* php);

void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

堆的销毁是释放由堆分配的内存空间的过程。当不再需要堆上分配的对象时，必须显式地销毁它们以释放内存，防止内存泄漏。销毁操作通常通过调用对象的析构函数来完成，它会执行必要的清理任务，如释放对象拥有的资源。销毁后，对象变得无效，不应再被使用。在C++中，可以使用delete操作符来销毁堆上分配的对象。在销毁过程中，需要特别注意避免重复销毁和野指针问题。

数据交换函数

void Swap(HPDataType* a, HPDataType* b);//数据交换函数


void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType temp = *a;
	*a = *b;
	*b = temp;
}

堆的向上交换

void AdjustUp(HPDataType* a, int child);//向上交换


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

void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		size_t newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* newnode = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);
		if (newnode == NULL)
		{
			perror("newnode realloc : ");
			return;
		}
		php->a = newnode;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);
}

元素入堆是指将一个元素插入到堆（Heap）这种数据结构中的过程。堆通常是一种特殊的树形数据结构，其每个父节点的值都大于或等于（在最大堆中）或小于或等于（在最小堆中）其子节点的值。元素入堆的过程通常涉及到调整堆的结构，以保持其性质。在插入新元素后，可能需要通过“上浮”或“下沉”操作来调整元素位置，确保堆的性质得以维持。这个过程对于堆排序、优先队列等算法至关重要。

堆的向下交换

void AdjustDown(HPDataType* a, int n,int parent);//向下交换


void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent* 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

堆的向下交换是堆排序算法中的一个重要步骤。在堆排序中，首先构建一个最大堆或最小堆，然后通过不断将堆顶元素与堆尾元素交换并重新调整堆结构，达到排序的目的。向下交换是指将堆顶元素与其子节点中较大的（对于最大堆）或较小的（对于最小堆）元素交换位置，然后重新调整子堆，以保持堆的性质。这个过程重复进行，直到整个堆排序完成。向下交换是堆排序算法中的关键步骤，能够确保堆的性质得以维持，从而实现快速排序。

元素出堆

void HPPop(HP* php);


void HPPop(HP* php)
{
	assert(php);
	assert(!HPEmpty(php));
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

出堆操作是堆数据结构中的一种常见操作，主要用于从堆中移除并返回堆顶元素（即具有最大或最小值的元素）。在执行出堆操作时，首先需要将堆顶元素与堆的最后一个元素交换位置，然后调整剩余元素以维持堆的性质。对于最大堆，堆顶元素总是最大的，而对于最小堆，堆顶元素总是最小的。出堆操作的时间复杂度通常为O(log n)，其中n是堆中元素的数量。通过出堆操作，可以高效地获取并删除堆中的最大或最小元素，从而在各种算法和数据结构中实现高效的数据处理和查询。

堆顶元素

HPDataType HPTop(HP* php);//堆顶元素


HPDataType HPTop(HP* php)
{
	assert(php);
	return php->a[0];
}

堆是否为空

bool HPEmpty(HP* php);

bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

五、堆的应用

5.1 数组向上调整建堆

void HPInitArray(HP* php, HPDataType* a, int n)

void HPInitArray(HP* php, HPDataType* a, int n)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("php->a malloc :");
		return;
	}
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->capacity = php->size = n;
	//向上排序 时间复杂度N*log N
	for (int i = 1; i < php->size; i++)
	{
		AdjustUp(php->a, i);
	}
}

数组向上调整建堆是一种构建堆（Heap）的方法，通常用于实现堆排序算法。该方法从数组的中间位置开始，将每个元素作为潜在的堆顶，然后通过向上调整操作，确保以该元素为根的子树满足堆的性质（最大堆或最小堆）。向上调整操作包括将根节点与其子节点比较，并在必要时交换它们的位置，以确保堆的性质得以维持。通过从数组的中间位置到第一个元素的顺序进行向下调整，最终可以构建出一个完整的堆结构。这种方法的时间复杂度为O(nlogn)，其中n是数组的长度。
数据结构从入门到精通——堆,数据结构从入门到精通,数据结构,算法,c语言,leetcode,r-tree,lsm-tree,suffix-tree

数据结构从入门到精通——堆,数据结构从入门到精通,数据结构,算法,c语言,leetcode,r-tree,lsm-tree,suffix-tree

5.2数组向下调整建堆

void HPInitArray(HP* php, HPDataType* a, int n)

void HPInitArray(HP* php, HPDataType* a, int n)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("php->a malloc :");
		return;
	}
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->capacity = php->size = n;
	向上排序 时间复杂度N*log N
	//for (int i = 1; i < php->size; i++)
	//{
	//	AdjustUp(php->a, i);
	//}
	//向下排序,时间复杂度N
	for (int i = (php->size - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}
}

数组向下调整建堆是指在构建一个最大堆（或最小堆）时，从数组末尾开始，逐个向上调整每个非叶子节点，使其满足堆的性质。具体步骤如下：

  1. 从最后一个非叶子节点开始，向前遍历数组。
  2. 对于每个节点，检查其是否满足堆的性质，即是否大于（或小于）其子节点。
  3. 如果不满足堆的性质，则将其与其较大的子节点交换位置，并继续向下调整子树，直到满足堆的性质。
  4. 重复步骤2和3，直到遍历完所有节点。

通过这种向下调整的方式，可以高效地构建一个最大堆（或最小堆），为后续的堆排序等操作提供基础。这种办法的时间复杂度是O(N).
数据结构从入门到精通——堆,数据结构从入门到精通,数据结构,算法,c语言,leetcode,r-tree,lsm-tree,suffix-tree
数据结构从入门到精通——堆,数据结构从入门到精通,数据结构,算法,c语言,leetcode,r-tree,lsm-tree,suffix-tree

5.3堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

  • 建堆
    • 升序：建大堆
    • 降序：建小堆
  • 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

数据结构从入门到精通——堆,数据结构从入门到精通,数据结构,算法,c语言,leetcode,r-tree,lsm-tree,suffix-tree

void HeapSort(HPDataType* a, int 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--;
	}
}

堆排序是一种基于二叉堆数据结构的排序算法。它首先将待排序序列构造成一个大顶堆（或小顶堆），然后依次将堆顶元素（最大值或最小值）与堆尾元素交换并删除，再通过调整堆结构使其保持为堆，重复此过程直至堆为空。这样，就能得到一个有序序列。堆排序的时间复杂度O(nlogn)，空间复杂度为O(1)。

5.4TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

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

  • 用数据集合中前K个元素来建堆
    • 前k个最大的元素，则建小堆
    • 前k个最小的元素，则建大堆
  • 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
ps：剩余的数据可能是非递增的，想要递增的话，可以自己添加排序算法文章来源地址https://www.toymoban.com/news/detail-840768.html

直接建数据

void PrintTopK(int* a, int n, int k)
{
 // 1. 建堆--用a中前k个元素建堆
 
 // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
}
 
void TestTopk()
{
 	int n = 10000;
 	int* a = (int*)malloc(sizeof(int)*n);
 	srand(time(0));
 	for (size_t i = 0; i < n; ++i)
	 {
 		a[i] = rand() % 1000000;
 	}
	a[5] = 1000000 + 1;
 	a[1231] = 1000000 + 2;
 	a[531] = 1000000 + 3;
 	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
 	a[2335] = 1000000 + 6;
 	a[9999] = 1000000 + 7;
 	a[76] = 1000000 + 8;
 	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
 	PrintTopK(a, n, 10);
}

文件建数据

void CreateNDate()
{
	int k = 10000;
	srand((unsigned int)time(NULL));
	FILE* pf = fopen("data.txt", "w");
	if (pf == NULL)
	{
		perror("pf fopen :");
		return;
	}
	for (int i = 0; i < k; i++)
	{
		fprintf(pf, "%d\n", rand()%10000 + i );
	}
	fclose(pf);
}

完整代码

test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
void CreateNDate()
{
	int k = 10000;
	srand((unsigned int)time(NULL));
	FILE* pf = fopen("data.txt", "w");
	if (pf == NULL)
	{
		perror("pf fopen :");
		return;
	}
	for (int i = 0; i < k; i++)
	{
		fprintf(pf, "%d\n", rand()%10000 + i );
	}
	fclose(pf);
}
void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}
void AdjustDown(int* a, int n, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
int main()
{
	//CreateNDate();
	int k = 0;
	printf("输入需要排序的个数:  \n", &k);
	scanf("%d", &k);
	int* a = (int*)malloc(sizeof(int) * k);
	FILE* pf = fopen("data.txt", "r");
	if (pf == NULL)
	{
		perror("pf fopen :");
		return;
	}
	for (int i = 0; i < k; i++)
	{
		fscanf(pf, "%d", &a[i]);
	}
	for (int i = (k - 1 - 1) / 2 ; i >= 0; i--)
	{
		AdjustDown(a, k, i);
	}
	int x = 0;
	while (fscanf(pf, "%d", &x) != EOF)
	{
		if (a[0] < x)
		{
			a[0] = x;
			AdjustDown(a, k, 0);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", a[i]);
	}

	fclose(pf);
	return 0;
}
数据交换
void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}
向下调整
void AdjustDown(int* a, int n, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
主函数
int main()
{
	//CreateNDate();  在需要新数据的时候开启或关闭
	int k = 0;
	printf("输入需要排序的个数:  \n", &k);
	scanf("%d", &k);
	int* a = (int*)malloc(sizeof(int) * k);
	FILE* pf = fopen("data.txt", "r");
	if (pf == NULL)
	{
		perror("pf fopen :");
		return;
	}
	for (int i = 0; i < k; i++)
	{
		fscanf(pf, "%d", &a[i]);
	}
	for (int i = (k - 1 - 1) / 2 ; i >= 0; i--)
	{
		AdjustDown(a, k, i);
	}
	int x = 0;
	while (fscanf(pf, "%d", &x) != EOF)
	{
		if (a[0] < x)
		{
			a[0] = x;
			AdjustDown(a, k, 0);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", a[i]);
	}

	fclose(pf);
	return 0;
}

到了这里，关于数据结构从入门到精通——堆的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构从入门到精通——冒泡排序

    数据结构从入门到精通——冒泡排序

    冒泡排序是一种简单的排序算法，通过重复遍历待排序数列，比较相邻元素的大小并交换位置，使得每一轮遍历后最大（或最小）的元素都会“冒泡”到数列的一端，直到整个数列有序。这种算法的时间复杂度较高，但在处理小规模数据或近乎有序的数据时表现良好，除此之

    2024年04月16日
    浏览(37)
  • 数据结构从入门到精通——直接插入排序

    数据结构从入门到精通——直接插入排序

    直接插入排序是一种简单的排序算法，其工作原理是逐个将待排序元素插入到已排序序列中的适当位置，直到全部元素排序完毕。算法从第二个元素开始，将其与前面的元素进行比较，如果当前元素小于前一个元素，则将其插入到前一个元素之前，否则继续向前比较。重复此

    2024年03月21日
    浏览(49)
  • 数据结构从入门到精通——树和二叉树

    数据结构从入门到精通——树和二叉树

    树和二叉树是计算机科学中常用的数据结构，它们在数据存储、搜索、排序等多个领域都有着广泛的应用。从简单的二叉树出发，我们可以逐步理解更复杂的树结构，如红黑树、AVL树等。 二叉树是一种每个节点最多有两个子节点的树结构，通常子节点被称为“左子节点”和“

    2024年03月15日
    浏览(101)
  • 数据结构从入门到精通——排序的概念及运用

    数据结构从入门到精通——排序的概念及运用

    排序是将数据按照一定规则重新排列的过程，常见规则有升序、降序等。排序算法如冒泡排序、快速排序等，广泛用于数据库、搜索引擎等场景，提高数据检索效率。此外，排序也应用于统计分析、机器学习等领域，以获取有序数据集或发现数据间的关联。 排序是一种将一组

    2024年03月21日
    浏览(40)
  • Redis从入门到精通【高阶篇】之底层数据结构字典(Dictionary)详解

    Redis从入门到精通【高阶篇】之底层数据结构字典(Dictionary)详解

    上个篇章回顾，我们上个章节，讲了Redis中的快表（QuickList），它是一种特殊的数据结构，用于存储一系列的连续节点，每个节点可以是一个整数或一个字节数组。快表是Redis中的底层数据结构之一，常用于存储有序集合（Sorted Set）等数据类型的底层实现。 那么本章讲解Red

    2024年02月09日
    浏览(50)
  • Redis从入门到精通【高阶篇】之底层数据结构跳表(SkipList)

    Redis从入门到精通【高阶篇】之底层数据结构跳表(SkipList)

    上个篇章回顾，我们上个章节我们学习了《Redis从入门到精通【高阶篇】之底层数据结构整数集(IntSet)详解》，我们从源码层了解整数集由一个头部和多个数据块组成。头部中存储了整数集的元素个数、编码方式和数据块的起始地址等信息。数据块中存储了实际的整型数据，当

    2024年02月09日
    浏览(47)
  • Redis从入门到精通【高阶篇】之底层数据结构压缩列表(ZipList)详解

    Redis从入门到精通【高阶篇】之底层数据结构压缩列表(ZipList)详解

    前面的Redis从入门到精通的基础篇和进阶篇都是在使用层面和概念层面，本章节，我们了解一下redis的底层数据结构，上几个章节，我们讲了SDS,字典 。本章节我们聊一下ZipList。 压缩列表（ZipList）就是redis为了节约内存而设计开发的数据结构，并且作为列表键和哈希键的底层

    2024年02月08日
    浏览(87)
  • Redis从入门到精通【高阶篇】之底层数据结构整数集(IntSet)详解

    Redis从入门到精通【高阶篇】之底层数据结构整数集(IntSet)详解

    上个篇章回顾，我们上个章节我们学习了《Redis从入门到精通【高阶篇】之底层数据结构字典(Dictionary)详解》，我们从源码层了解字典是一种以键值对（key-value）形式存储数据的数据结构。在 Redis 中，字典使用哈希表来实现。哈希表是一种以常数时间复杂度 O(1) 进行插入、删

    2024年02月09日
    浏览(40)
  • 【算法与数据结构】112、LeetCode路径总和

    【算法与数据结构】112、LeetCode路径总和

    所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 ：本题通过计算根节点到叶子节点路径上节点的值之和，然后再对比目标值。利用文章【算法和数据结构】257、LeetCode二叉树的所有路径中的递归算法。 这里要注意，默认路径之和是

    2024年02月11日
    浏览(50)
  • 【算法与数据结构】474、LeetCode一和零

    【算法与数据结构】474、LeetCode一和零

    所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 ：本题要找strs数组的最大子集，这个子集最多含有 m m m 个0和 n n n 个1。本题也可以抽象成一个01背包的问题。其中，strs内的元素就是物品，而 m m m 和 n n n 就是背包的维度。 d p [

    2024年01月22日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包