iis服务器助手广告广告

扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >数据结构之堆的具体使用
  • 482

0
分享到

数据结构之堆的具体使用

2024-04-02 19:04:59 482人浏览 泡泡鱼
摘要

目录堆的概念及结构定义堆堆的初始化插入数据判空删除堆顶的数据获取堆顶数据获取元素个数打印销毁堆Topk问题代码总结堆的概念及结构 定义堆 实现堆的功能首先要定义堆的结构体 typ

堆的概念及结构

在这里插入图片描述

在这里插入图片描述

定义堆

实现堆的功能首先要定义堆的结构体

typedef int HPDataTpye;

typedef struct Heap
{
	HPDataTpye* a;		//存储数据
	int size;           //保存元素个数
	int capacity;       //存储容量
}HP;

堆的初始化

思路：

  • 先开辟一块空间，将传入的数据存放到堆的结构体中
  • 将堆中数据建堆排序
  • 将堆结构中容量，元素个数初始化

开辟空间不难，那么如何建堆呢？

这里有两种思路，一是从上往下调整，二是从下往上调整

思路一：
从上往下调整

将传入的结点当做父节点，比较其两个子节点，将子节点与父节点比较，如果不满足堆的条件就交换，并将原先子节点的位置当成父节点，重复上述操作。如果满足堆的条件就结束操作。（注意：该程序是建立在左右子树都为大堆基础上的）

在这里插入图片描述

代码如下

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}
// 条件：左右子树都是小堆/大堆
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 选出左右孩子中小 or 大的那个
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}

		// 1、如果小 or 大的孩子比父亲小 or 大，则交换，继续往下调整
		// 2、如果小 or 大 的孩子比父亲大 or 小，则结束调整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

思路二：
从下往上建

将传入的结点当做子节点，找到其父结点并与之比较，不满足堆的条件就交换，并将原父结点的位置当成子节点重复之前操作。满足堆的条件则退出程序。（注意：该程序建立在除传入的子节点外，其余结点都满足堆条件基础上的）

在这里插入图片描述

代码实现

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}
void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	//while (parent >= 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(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

// 条件：左右子树都是小堆/大堆
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 选出左右孩子中小 or 大的那个
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}

		// 1、如果小 or 大的孩子比父亲小 or 大，则交换，继续往下调整
		// 2、如果小 or 大 的孩子比父亲大 or 小，则结束调整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	//while (parent >= 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 Heapinit(HP* PHP, HPDataTpye* a, int n)
{
	assert(php);
	//开辟空间
	php->a = (HPDataTpye*)malloc(sizeof(HPDataTpye)*n);
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//转移数据
	memcpy(php->a, a, sizeof(HPDataTpye)*n);
	//建堆排序
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, n, i);
	}

	php->capacity = n;
	php->size = n;
}

插入数据

思路：

  • 检查是否满容量，满了就扩容
  • 插入数据，并将size+1

代码：

void HeapPush(HP* php, HPDataTpye x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		HPDataTpye* tmp = (HPDataTpye*)realloc(php->a, 2 * php->capacity*sizeof(HPDataTpye));
		if (php->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->capacity *= 2;
	}
	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

判空

思路：

判空只需判断其元素个数是否为0即可

代码：

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

删除堆顶的数据

思路：

  • 先判空处理
  • 将堆顶数据和最后一个叶结点数据交换
  • 从上往下调整堆

在这里插入图片描述

代码：

void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	//交换头尾数据
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

获取堆顶数据

思路：

先判空，再取出堆顶数据

代码：

HPDataTpye HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	return php->a[0];
}

获取元素个数

直接返回size

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

打印

void HeapPrint(HP* php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

销毁堆

将开辟的空间释放，并将size,capacity赋值为0

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

Topk问题

问：如何取出一组数据中最大的前K个值

有人会想到把所有数据建大堆，取出堆顶数据再删除该数据，重复操作K次
操作如下

void TestHeap()
{
	int a[] = { 27, 37, 28, 18, 19, 34, 65, 4, 25, 49, 15 };
	HP hp;
	HeapInit(&hp, a, sizeof(a) / sizeof(int));
	HeapPrint(&hp);

	printf("\n");

	int k = 0;
	scanf("%d", &k);
	printf("找出数组中最小的前%d个：", k);
	while (!HeapEmpty(&hp)&&k--)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	printf("\n");
}

在这里插入图片描述

如果该组数据个数为一万，十万呢？

这时用该方法不但耗费时间而且十分耗内存，那有没有时间复杂符度较小的用堆实现的方法呢？
答案是有的，那就是Topk算法

Topk基本思路如下：

用数据集合中前K个元素来建堆
求前k个最大的元素，则建小堆
求前k个最小的元素，则建大堆用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

代码实现

void PrintTopK(int* a, int n, int k)
{
	HP hp;
	HeapInit(&hp, a, k);

	for(int i = k; i < n; i++)
	{
		if (a[i]>HeapTop(&hp))
		{
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
		}
	}
	HeapPrint(&hp);
	HeapDestroy(&hp);
}

检测

这里利用随机数来检测

void TestTopk()
{
	int n = 100000;
	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);
}

运行结果

在这里插入图片描述

代码总结

Heap.h 头文件

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include<time.h>

typedef int HPDataTpye;

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

void Swap(int* px, int* py);
void AdjustDown(int* a, int n, int parent);
void AdjustUp(int* a, int child);


//void HeapInit(HP* php);
//初始化
void HeapInit(HP* php, HPDataTpye* a, int n);
// 插入x，保持他继续是堆
void HeapPush(HP* php, HPDataTpye x);
//判空
bool HeapEmpty(HP* php);
// 删除堆顶数据，删除后保持他继续是堆
void HeapPop(HP* php);
// 获取堆顶的数据，也就是最值
HPDataTpye HeapTop(HP* php);
//获取堆中元素个数
int HeapSize(HP* php);
//打印
void HeapPrint(HP* php);
//销毁堆
void HeapDestroy(HP* php);

Heap.c 函数文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

// 条件：左右子树都是小堆/大堆
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 选出左右孩子中小 or 大的那个
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}

		// 1、如果小 or 大的孩子比父亲小 or 大，则交换，继续往下调整
		// 2、如果小 or 大 的孩子比父亲大 or 小，则结束调整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	//while (parent >= 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 HeapInit(HP* php, HPDataTpye* a, int n)
{
	assert(php);
	//开辟空间
	php->a = (HPDataTpye*)malloc(sizeof(HPDataTpye)*n);
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//转移数据
	memcpy(php->a, a, sizeof(HPDataTpye)*n);
	//建堆排序
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, n, i);
	}

	php->capacity = n;
	php->size = n;
}

// 插入x，保持它继续是堆
void HeapPush(HP* php, HPDataTpye x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		HPDataTpye* tmp = (HPDataTpye*)realloc(php->a, 2 * php->capacity*sizeof(HPDataTpye));
		if (php->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->capacity *= 2;
	}
	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

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

// 删除堆顶数据，删除后保持他继续是堆
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

// 获取堆顶的数据，也就是最值
HPDataTpye HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	return php->a[0];
}


int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

void HeapPrint(HP* php)
{
	for (int 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->capacity = php->size = 0;
}

test.c 测试文件

#include "Heap.h"

void TestHeap()
{
	int a[] = { 27, 37, 28, 18, 19, 34, 65, 4, 25, 49, 15 };
	HP hp;
	HeapInit(&hp, a, sizeof(a) / sizeof(int));
	HeapPrint(&hp);

	printf("\n");

	int k = 0;
	scanf("%d", &k);
	printf("找出数组中最小的前%d个：", k);
	while (!HeapEmpty(&hp)&&k--)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	printf("\n");
}

void PrintTopK(int* a, int n, int k)
{
	HP hp;
	HeapInit(&hp, a, k);

	for(int i = k; i < n; i++)
	{
		if (a[i]>HeapTop(&hp))
		{
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
		}
	}
	HeapPrint(&hp);
	HeapDestroy(&hp);
}

void TestTopk()
{
	int n = 100000;
	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);
}

int main()
{
	//TestHeap();
	TestTopk();

	return 0;
}

到此这篇关于数据结构之堆的具体使用的文章就介绍到这了,更多相关数据结构 堆内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: 数据结构之堆的具体使用

本文链接: https://www.lsjlt.com/news/140329.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档
去做题
猜你喜欢
  • 数据结构之堆的具体使用
    目录堆的概念及结构定义堆堆的初始化插入数据判空删除堆顶的数据获取堆顶数据获取元素个数打印销毁堆Topk问题代码总结堆的概念及结构 定义堆 实现堆的功能首先要定义堆的结构体 typ...
    99+
    2022-11-13
  • C++数据结构之堆详解
    目录堆的概念提示：完全二叉树堆的性质最大堆最小堆代码定义有限数组形式动态数组形式操作向下调整结点建立堆初始化打印堆测试main函数结果完整代码堆的概念 堆（heap）是计算机科学中一...
    99+
    2022-11-13
  • Java 数据结构之堆的概念与应用
    目录什么是堆堆的类型小根堆大根堆堆的基本操作：创建堆堆的时间复杂度和空间复杂度堆的应用-优先级队列概念优先级队列基本操作入优先级队列出优先级队列首元素java的优先级队列堆的常见面试...
    99+
    2022-11-12
  • C++数据结构之堆的概念是什么
    今天小编给大家分享一下C++数据结构之堆的概念是什么的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。堆的概念堆（heap）是计...
    99+
    2023-06-29
  • Python二进制数据结构Struct的具体使用
    目录二进制数据结构Struct函数与Struct类打包解包字节序指示符缓冲区二进制数据结构Struct 在C/C++语言中，struct被称为结构体。而在Python中，struct是一个专门的库，用于处理字节串与原...
    99+
    2022-06-02
    Python 二进制数据结构Struct Python 二进制数据结构 Python Struct
  • Python 数据结构之堆栈实例代码
    Python 堆栈 堆栈是一个后进先出(LIFO)的数据结构. 堆栈这个数据结构可以用于处理大部分具有后进先出的特性的程序流 . 在堆栈中, push 和 pop 是常用术语: push: 意思是把...
    99+
    2022-06-04
    堆栈 数据结构 实例
  • C语言数据结构之堆、堆排序的分析及实现
    目录 1.堆的概念结构及分类1.2堆的分类1.2.1 大堆1.2.2 小堆2. 堆的主要接口3.堆的实现3.1 堆的初始化 HeapInit3.2 堆的销毁 HeapDes...
    99+
    2022-11-13
  • Java数据结构之堆(优先队列)的实现
    堆（优先队列）是一种典型的数据结构，其形状是一棵完全二叉树，一般用于求解topk问题。根据双亲节点大于等于孩子节点或双亲节点小于等于孩子节点，可分为大顶堆和小顶堆，本文实现大顶堆。 ...
    99+
    2022-11-13
  • C语言数据结构之堆排序详解
    目录1.堆的概念及结构2.堆的实现2.1 堆的向下调整算法2.2 堆的向上调整算法2.3 建堆（数组）2.4 堆排序2.5 堆排序的时间复杂度1.堆的概念及结构 如果有一个关键码的集...
    99+
    2022-11-13
  • Go数据结构之堆排序示例详解
    目录堆排序堆排序过程动画显示开始堆排序代码实现总结堆排序 堆排序是一种树形选择排序算法。 简单选择排序算法每次选择一个关键字最小的记录需要 O(n) 的时间，而堆排序选择一个关键字最...
    99+
    2022-11-11
  • Java数据结构之堆(优先队列)详解
    目录堆的性质堆的分类堆的向下调整堆的建立堆得向上调整堆的常用操作入队列出队列获取队首元素TopK 问题例子数组排序堆的性质 堆逻辑上是一棵完全二叉树，堆物理上是保存在数组中 。 总...
    99+
    2022-11-13
  • 【数据结构——堆】堆的基本功能和堆排序
    文章目录 前言一、堆的定义1.大根堆2.小根堆3.父亲和孩子之间的关系 二、堆的操作和算法1.堆的初始化2.堆的插入向上调整算法向上调整算法时间复杂度 3. 堆的删除向下调整算法向下...
    99+
    2023-09-04
    数据结构 php 开发语言
  • 深入了解Java数据结构和算法之堆
    目录1、堆的定义2、遍历和查找3、移除4、插入5、完整的Java堆代码总结1、堆的定义 ①、它是完全二叉树，除了树的最后一层节点不需要是满的，其它的每一层从左到右都是满的。注意下面两...
    99+
    2022-11-13
  • C语言 深入解读数据结构之堆的实现
    堆的概念与结构 概念：如果有一个关键码的集合K={ k0，k1 ，k2 ，…，kn-1 },把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足K i<=K ...
    99+
    2022-11-12
  • C语言数据结构之堆排序的优化算法
    目录1.堆排序优化算法1.1建堆的时间复杂度1.1.1 向下调整建堆：O(N)1.1.2 向上调整建堆：O(N*logN)1.2堆排序的复杂度1.2.1原堆排序的时间复杂度...
    99+
    2022-11-13
  • Java数据结构中的堆怎么应用
    本篇内容介绍了“Java数据结构中的堆怎么应用”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！一、堆的创建1、向下调整（以小堆为例） &nbs...
    99+
    2023-06-29
  • C语言结构体指针的具体使用
    目录什么是结构体指针？如何访问结构体成员？如何传递结构体指针作为参数？结构体指针数组在 C语言中，结构体指针是一种非常有用的数据类型，它可以让我们更方便地操作结构体。结构体指针可以指...
    99+
    2023-05-20
    C语言结构体指针
  • C语言结构体的具体使用方法
    目录初识C语言结构体1.为什么要有结构体2.结构体的定义2.1结构体类型的定义2.2定义结构体普通变量及访问2.3定义结构体指针变量及访问初识C语言结构体 1.为什么要有结构体 （1...
    99+
    2022-11-12
  • C语言数据结构二叉树之堆的实现和堆排序详解
    目录一、本章重点二、堆2.1堆的介绍2.2堆的接口实现三、堆排序一、本章重点 堆的介绍堆的接口实现堆排序 二、堆 2.1堆的介绍 一般来说，堆在物理结构上是连续的数组结构，在逻辑结构...
    99+
    2022-11-13
  • Java数据结构之最小堆和最大堆的原理及实现详解
    目录一、前言二、堆的数据结构三、堆的代码实现1. 实现介绍2. 入堆实现3. 出堆实现4. 小堆实现5. 大堆实现一、前言 堆的历史 堆的数据结构有很多种体现形式，包括；2-3堆、B...
    99+
    2022-11-13
软考高级职称资格查询
iis服务器助手广告
软考职称历年真题下载
软考职称资料下载
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作