当前位置： 首页 > article >正文

数据结构二叉树——堆

article 2024/11/15 7:28:33

一：堆的实现

堆是一二叉树的一种（完全二叉树）。

堆数据结构的设计：采用数组来存储。

优点：堆是完全二叉树，存储高效，并且除了最后一层外，每一层都被完全填满，并且所有的节点都尽可能地向左对齐，同时可以通过 索引来理清父子关系。

typedef int HPDataType;

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

堆的一些接口实现：

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

// 销毁:
void HPDestroy(HP* php)；

// 判断堆是否为空
bool is_HPEmpty(HP* php);

// 往堆里面插入元素(在最后一个叶子结点插入):
void HPPush(HP* php, HPDdataType x);

// 弹出堆顶元素(取堆顶元素)：
void HPPop(HP* php);

// 取堆顶的数据
HPDataType Top(HP* php);

初始化和销毁和链表的操作差不多：

插入接口算法的实现：

1：扩容

2：在堆的最后一个叶子节点后面插入数据

3：向上调整，使其仍然是一个堆（大堆或者小堆）

扩容部分算法也是和链表一样的，

向上调整算法：

核心思考逻辑：

依次用将父亲和孩子节点值比较，如果大小有区别就交换

更新孩子和父亲的坐标位置

当不满足大小关系或者调整到最上面一个位置的时候就退出循环

代码：

// 向上调整建堆
void AdjustUp(HPDataType* a, HPDataType child)
{
	assert(a != NULL);

	HPDataType parent = (child - 1) / 2;

	while (child > 0)
	{
		if (a[parent] > a[child])
		{
			swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

插入部分还要用到一个交换函数：

弹出堆顶元素接口实现：

1：将堆顶元素和堆的采用最后一个元素交换

2：覆盖删除掉堆顶元素

3：将堆顶元素用向下调整算法重新调整成一个堆

整体接口代：

#define _CRT_SECURE_NO_WARNINGS 1

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

typedef int HPDataType;

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

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

// 销毁:
void HPDestroy(HP* php);

// 判断堆是否为空
bool is_HPEmpty(HP* php);

// 往堆里面插入元素(在最后一个叶子结点插入):
void HPPush(HP* php, HPDataType x);

// 弹出堆顶元素(取堆顶元素)：
void HPPop(HP* php);

// 取堆顶的数据
HPDataType Top(HP* php);

// 向上调整建堆
void AdjustUp(HPDataType* a, HPDataType child);

// 向下调整
void AdjustDown(HPDataType* a, int num, HPDataType parent);

// 打印函数
void Printf(int* a, int num);

// 堆排序
void HeapSort(HPDataType* arr, int size);

#define _CRT_SECURE_NO_WARNINGS 1
#include "HP(practise).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;

}

// 判断堆是否为空
bool is_HPEmpty(HP* php)
{
	assert(php);

	return php->size == 0;

}

// 交换函数
void swap(HPDataType* num1, HPDataType* num2)
{
	HPDataType tmp = *num1;
	*num1 = *num2;
	*num2 = tmp;
}

// 向上调整建堆
void AdjustUp(HPDataType* a, HPDataType child)
{
	assert(a != NULL);

	HPDataType parent = (child - 1) / 2;

	while (child > 0)
	{
		if (a[parent] < a[child])
		{
			swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

// 往堆里面插入元素(在最后一个叶子结点插入):
void HPPush(HP* php, HPDataType x)
{
	assert(php);

	// 判断是否有足够的空间，不够的话就扩容
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));

		if (tmp == NULL)
		{
			perror("realloc fali!");
			return;
		}

		php->a = tmp;
		php->capacity = newcapacity;
	}

	php->a[php->size++] = x;

	// 向下调整建堆

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

// 向下调整
void AdjustDown(HPDataType* a, int num, HPDataType parent)
{
	HPDataType child = parent * 2 + 1;

	while (child < num)
	{
		// 假设法找到比较小的一个孩子节点
		if (child + 1 < num && a[child] > a[child + 1])
		{
			child++;
		}

		if (a[parent] > a[child])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

// 取堆顶的数据
HPDataType Top(HP* php)
{
	assert(php);

	return php->a[php->size - 1];
}

// 弹出堆顶元素(取堆顶元素)：
void HPPop(HP* php)
{
	assert(php);

	// 算法思想：
	// 先把堆顶的元素和最后一个元素交换，然后再覆盖删除
	// 交换好元素之后需要向下调整使其还是一个大堆或者小堆

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

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


// 打印函数
void Printf(HPDataType a[], int num)
{
	for (int i = 0; i < num; i++)
	{
		printf("%d  ", a[i]);
	}
	printf("\n");
}

// 堆排序
void HeapSort(HPDataType arr[], int size)
{

	// 先建堆
	// 再排序

	// 降序建小堆
	// 升序建大堆

	// 向上调整建堆(相当于push操作)
	//for (int i = 0; i < size; i++)
	//{
	//	AdjustUp(arr, i);
	//}

	// 向下调整建堆:从最后一个非叶子结点开始调整
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)  //  因为下标从0开始并且倒数第一个非叶子结点是最后一个下标减一除以2
	{
		AdjustDown(arr, size, i);
	}

	// 交换第一个和最后一个元素，指针依次往前挪,第一个元素向下调整使其成为相应的堆
	int end = size-1;

	while (end > 0)
	{
		swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}


}

测试函数：

#define _CRT_SECURE_NO_WARNINGS 1
#include "HP(practise).h"

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

	HPPush(&hp, 1);
	HPPush(&hp, 2);
	// printf("%d", is_HPEmpty(&hp)); // 判断是否为空堆
	HPPush(&hp, 3);
	HPPush(&hp, 4);

	// 取堆顶元素
	printf("%d", Top(&hp));

	// Printf(hp.a, hp.size);
	// HPPop(&hp);
	// HPPop(&hp);
	// Printf(hp.a, hp.size);

	HPDestroy(&hp);

}

void TestHeapSort()
{
	// 给定一个数组，使用堆排序来将其排好

	int arr[] = { 11, 9, 5, 12, 13, 15};

	int size = sizeof(arr) / sizeof(arr[0]);

	HeapSort(arr, sizeof(arr) / sizeof(arr[0]));

	Printf(arr, size);
}

//void makeheap()
//{
//	int arr[] = { 11, 9, 5, 12, 13, 15 };
//	int size = sizeof(arr) / sizeof(arr[0]);
//
//	for (int i = (size-1-1) / 2; i >= 0; i--)
//	{
//		AdjustDown(arr, size, i);
//	}
//
//	Printf(arr, size);
//}

int main()
{

	TestHeap01();
	
	//TestHeapSort();

	//makeheap();

	return 0;
}

二：堆排序：

步骤：

1：先建一个堆

2：堆排序

升序建大堆，降序建小堆。

1：向上调整建堆

2：向下调整建堆

三：top K问题：

从一堆数据中选出前K个排名的数据

1：建一个小堆：

2：依次将所有数据和堆顶数据比较，根据所需要的排名要求再决定替换堆顶数据，然后小堆向下调整，依然是一个小堆，最后调整完成之后这个小堆里面的数据就是这K个需要选出来的数据，如果需要有序的话也可以重新进行排序

案例:从文件中读写数据，然后找出最大的K个数据。

#define _CRT_SECURE_NO_WARNINGS 1

#include "HP(practise).h"


void CreateNDate()
{
	// 造数据
	int n = 10000;
	srand((unsigned int)time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (size_t i = 0; i < n; ++i)
	{
		int x = rand() % 1000000;
		// 使用fprintf将产生的随机数据写入打开的文件流中
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

void PrintTopK(int k)
{
	CreateNDate();
	int* TopK_Heap = (int*)malloc(sizeof(int) * k);
	FILE* fp = fopen("data.txt", "r");
	if (fp == NULL)
	{
		ferror(fp);
		return;
	}

	// 使用fscanf将文件中的数据读出来，然后写入数组中
	for (int i = 0; i < k; i++)
	{
		fscanf(fp, "%d", &TopK_Heap[i]);
	}

	// 建堆
	for (int i = 0; i < k; i++)
	{
		(TopK_Heap, k, i);
	}

	// 从文件中取数据和堆顶AdjustDown数据比较，如果比堆顶数据大或者小就向下调整
	int x = 0;

	while(fscanf(fp, "%d", &x) > 0)
	{
		if (x > TopK_Heap[0])
		{
			TopK_Heap[0] = x;
			AdjustDown(TopK_Heap, k, 0);
		}
	}

	// 打印
	for (int i = 0; i < k; i++)
	{
		printf("%d ", TopK_Heap[i]);
	}
}

int main()
{
	int k;
	scanf("%d", &k);
	PrintTopK(k);

	return 0;
}


 


http://www.kler.cn/a/289950.html

相关文章：

  • SQL集合运算
  • 1.7 JS性能优化
  • C++ 的协程
  • acwing算法基础02一高精度,前缀和，差分
  • 服务器显卡和桌面pc显卡有什么不同
  • 【MySQL】MySQL函数之JSON_EXTRACT
  • Scott Brinker：Martech中的AI会让买家体验更好还是更糟？这取决于…….
  • Unity版本升级2022 Gradle 升级7.x版本调整
  • 代码随想录 刷题记录-27 图论 (4)拓扑排序
  • Rides实现分布式锁，保障数据一致性,Redisson分布式事务处理
  • python学习之路 - PySpark快速入门
  • docker实战基础三(Docker基础命令)
  • lvgl 自定义组件介绍二
  • yolo训练策略--使用 Python 和 OpenCV 进行图像亮度增强与批量文件复制之（图像增强是按梯度变化优化）
  • 光盘安全隔离与信息单向导入系统-信刻
  • 以人口金字塔图为例，在线绘制左右双侧堆叠条形图
  • 如何设计店铺租赁租凭平台？Java SpringBoot实现全攻略
  • 后端是否开启异步执行，看打印日志的线程信息
  • 多线程篇（可见性 原子性 有序性（原子性））（持续更新迭代）
  • 09J621-2《电动采光排烟天窗》技术详解
  • openharmony历程一：安装ubuntu20.04
  • Vue基础语法
  • ai聊天软件哪个好用？分享5款实用的智能聊天软件
  • Linux云计算学习笔记11 （计划任务）
  • SpringBoot 大学生体质测试管理系统
  • 记录k8s的pod生命周期笔记