1. AI技术聚合首页
  2. IT

【数据结构 —— 堆的实现（顺序表）】

青葱年少 • • IT • 阅读 60

数据结构 —— 堆的实现（顺序表）

  • 一.堆
    • 1.1堆的定义及结构
      • 1.1.1.堆的定义
      • 1.1.2.堆的性质
      • 1.1.3.堆的结构
  • 二.堆的实现
    • 2.1.头文件的实现 —— （Heap.h）
    • 2.2.源文件的实现 —— （Heap.c）
      • 2.2.1.小堆的源文件
      • 2.2.2.大堆的源文件
    • 2.3.源文件的实现 —— （test.c）
  • 三.实际数据测试展示
    • 3.1.插入数据
      • 3.1.1.小堆插入 ——（调试窗口展示）
      • 3.1.2.大堆插入 ——（调试窗口展示）
    • 3.2 打印前k个最值 ——（小型top-k问题）
      • 3.2.1.小堆打印前k个最小值 —— （运行展示）
      • 3.2.2.大堆打印前k个最大值 —— （运行展示）
    • 3.3简单类堆排序 ——（非真堆排序）
      • 3.3.1.类小堆排序 ——（运行展示）
      • 3.3.2.类大堆排序 ——（运行展示）
    • 3.4 打印前k个最值 ——（大型top-k问题）
      • 3.2.1.小堆打印前k个最小值 —— （运行展示）
      • 3.2.1.小堆打印前k个最大值 —— （运行展示）
    • 3.5.真堆排序
      • 3.5.1.升序 —— （运行展示）
      • 3.5.2.降序 ——（运行展示）

一.堆

1.1堆的定义及结构

1.1.1.堆的定义

堆就是以二叉树的顺序存储方式来存储元素，同时又要满足父亲结点存储数据都要大于儿子结点存储数据（也可以是父亲结点数据都要小于儿子结点数据）的一种数据结构。堆只有两种即大堆和小堆，大堆就是父亲结点数据大于儿子结点数据，小堆则反之。

1.1.2.堆的性质

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

1.1.3.堆的结构

用图画展示就如下图所示：
(1).小堆展示

(2).大堆展示

二.堆的实现

2.1.头文件的实现 —— （Heap.h）

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 size;
	int capacity;
}HP;

//创建/销毁
void HeapInit(HP* php);
void HeapDestroy(HP* php);
//插入/删除
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
//获取堆顶元素
HPDataType HeapTop(HP* php);
//判空/统计堆内元素个数
bool HeapEmpty(HP* php);
int HeapSize(HP* php);
//交换函数
void Swap(HPDataType* p1, HPDataType* p2);
//向上调整
void AdJustUp(HPDataType* a, int child);
//向下调整
void AdJustDown(HPDataType* a, int size, int parent);

2.2.源文件的实现 —— （Heap.c）

2.2.1.小堆的源文件

Heap.c

#include"Heap.h"


//小堆
//创建/销毁
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向上调整函数
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 = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//插入/删除
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)//判断数组空间不够就扩容
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdJustUp(php->a, php->size - 1);

}
//向下调整函数
void AdJustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child+1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapPop(HP* php)
{
	assert(php);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdJustDown(php->a, php->size, 0);
}
//获取堆顶元素
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];

}
//判空/统计堆内元素个数
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
int HeapSize(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->size;
}

2.2.2.大堆的源文件

Heap.h

#include"Heap.h"


//大堆
//创建/销毁
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向上调整函数
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 = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//插入/删除
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)//判断数组空间不够就扩容
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdJustUp(php->a, php->size - 1);

}
//向下调整函数
void AdJustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child+1 < size && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapPop(HP* php)
{
	assert(php);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdJustDown(php->a, php->size, 0);
}
//获取堆顶元素
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];

}
//判空/统计堆内元素个数
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
int HeapSize(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->size;
}

2.3.源文件的实现 —— （test.c）

大堆/小堆的相关测试代码，我都放在一个测试源文件里了，注意区分。

test.c

#include"Heap.h"

//小堆
//int main()
//{
//	HP ph;
//	HeapInit(&ph);
//
//	int a[] = { 4,6,2,1,5,8,2,9};
//	for (int i = 0; i < (sizeof(a) / sizeof(int)); i++)
//	{
//		HeapPush(&ph, a[i]);//插入
//	}
//
//	//获取前k个最小值
//	/*int k = 3;
//	while (k--)
//	{
//		printf("%d\n", HeapTop(&ph));
//		HeapPop(&ph);
//	}*/
//	//小堆排序
//	while (!HeapEmpty(&ph))
//	{
//		printf("%d ", HeapTop(&ph));
//		HeapPop(&ph);
//	}
//
//	return 0;
//}

//大堆
//int main()
//{
//	HP ph;
//	HeapInit(&ph);
//	int a[] = { 4,6,2,1,5,8,2,9 };
//	for (int i = 0; i < (sizeof(a) / sizeof(int)); i++)
//	{
//		HeapPush(&ph, a[i]);
//	}
//	//前k个最大值
//	/*int k = 3;
//	while (k--)
//	{
//		printf("%d\n", HeapTop(&ph));
//		HeapPop(&ph);
//	}*/
//	//大堆排序
//	while(!HeapEmpty(&ph))
//	{
//		printf("%d ", HeapTop(&ph));
//		HeapPop(&ph);
//	}
//	return 0;
//}

//升序
//void HeapSort(int* a, int n)
//{
//	//建大堆/向上调整建堆/O(N*longN)
//	/*for (int i = 0; i < n; i++)
//	{
//		AdJustUp(a, i);
//	}*/
//	int end = n - 1;
//	//向下调整建堆
//	// O(N)
//	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
//	{
//		AdJustDown(a,n, i);
//	}
//	//O(N*longN)
//	while(end > 0)
//	{
//		Swap(&a[0], &a[end]);
//		AdJustDown(a, end, 0);
//		end--;
//	}
//}

//降序
//void HeapSort(int* a, int n)
//{
//	建小堆/向上调整建堆/O(N*longN)
//	/*for (int i = 0; i < n; i++)
//	{
//		AdJustUp(a, i);
//	}*/
//	int end = n - 1;
//	向下调整建堆
//	 O(N)
//	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
//	{
//		AdJustDown(a, n, i);
//	}
//	O(N*longN)
//	while (end > 0)
//	{
//		Swap(&a[0], &a[end]);
//		AdJustDown(a, end, 0);
//		end--;
//	}
//}
//int main()
//{
//	int a[] = { 4,6,2,1,5,8,2,9 };
//	int size = sizeof(a) / sizeof(int);
//	HeapSort(a, size);
//	for (int i = 0; i < size; i++)
//	{
//		printf("%d ", a[i]);
//	}
//	printf("\n");
//	return 0;
//}




//创造数据通过随机数
//void CreateNDate()
//{
//	int n = 100000;
//	srand(time(0));
//	const char* file = "date.txt";
//	FILE* fin = fopen(file, "w");
//	if (fin == NULL)
//	{
//		perror("fopen error");
//		return;
//	}
//	for (int i = 0; i < n; i++)
//	{
//		int x = (rand() + i) % 100000;
//		fprintf(fin, "%d\n", x);
//	}
//	fclose(fin);
//}
//
//void PrintTopk(const char* file, int k)
//{
//	FILE* fout = fopen(file, "r");
//	if (fout == NULL)
//	{
//		perror("fopen error");
//		return;
//	}
//	int* minheap = (int*)malloc(sizeof(int) * k);
//	if (minheap == NULL)
//	{
//		perror("malloc error");
//		return;
//	}
//	//创建一个k个值的小堆
//	for (int i = 0; i < k; i++)
//	{
//		fscanf(fout, "%d", &minheap[i]);
//		AdJustUp(minheap, i);
//	}
//	//让后从文件先读取k个数，形成小堆，让后再依次读取文件的数据和堆顶的数据比对，
//	// 如果比堆顶的数大就覆盖替换，让后向下调整，再形成小堆，
//	// 最后堆里剩下的就是这些数据里最大的前k个值
//	int x = 0;
//	while (fscanf(fout, "%d", &x) != EOF)
//	{
//		if (x < minheap[0])
//		{
//			minheap[0] = x;
//			AdJustDown(minheap, k, 0);
//		}
//	}
//
//	for (int i = 0; i < k; i++)
//	{
//		printf("%d ", minheap[i]);
//	}
//	printf("\n");
//
//	free(minheap);
//	fclose(fout);
//
//
//}


//创造数据通过随机数
void CreateNDate()
{
	int n = 100000;
	srand(time(0));
	const char* file = "date.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		int x = (rand() + i) % 100000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

void PrintTopk(const char* file, int k)
{
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc error");
		return;
	}
	//创建一个k个值的大堆
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
		AdJustUp(minheap, i);
	}
	//让后从文件先读取k个数，形成大堆，让后再依次读取文件的数据和堆顶的数据比对，
	// 如果比堆顶的数小就覆盖替换，让后向下调整，再形成大堆，
	// 最后堆里剩下的就是这些数据里最小的前k个值
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x < minheap[0])
		{
			minheap[0] = x;
			AdJustDown(minheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");

	free(minheap);
	fclose(fout);


}
int main()
{
	//CreateNDate();
	PrintTopk("date.txt", 5);
	return 0;
}

三.实际数据测试展示

3.1.插入数据

3.1.1.小堆插入 ——（调试窗口展示）

3.1.2.大堆插入 ——（调试窗口展示）

3.2 打印前k个最值 ——（小型top-k问题）

3.2.1.小堆打印前k个最小值 —— （运行展示）

3.2.2.大堆打印前k个最大值 —— （运行展示）

3.3简单类堆排序 ——（非真堆排序）

3.3.1.类小堆排序 ——（运行展示）

3.3.2.类大堆排序 ——（运行展示）

3.4 打印前k个最值 ——（大型top-k问题）

大型数据的Top-k问题需要通过随机数的操作和文件的操作来辅助验证完成。不懂得可以查阅我之前相关文件和扫雷游戏的博客，都有介绍随机数和文件的相关操作。

3.2.1.小堆打印前k个最小值 —— （运行展示）

大致思路就是，通过创建文件，然后通过rand函数来生成随机数，将随机数写入文件，然后调用向下调整函数从文件先读取k个数，形成大堆，让后再依次读取文件的数据和堆顶的数据比对，如果比堆顶的数小就覆盖替换，让后向下调整，再形成大堆，最后堆里剩下的就是这些数据里最小的前k个值

注意：调用完一次创造数据的函数后，就要注释掉函数，否则每次的值都会是随机生成的，所以回变化不同
2.由于前K个最小值，要建立大堆，所以要调用大堆的向下调整函数接口

3.2.1.小堆打印前k个最大值 —— （运行展示）

大致思路就是，通过创建文件，然后通过rand函数来生成随机数，将随机数写入文件，然后调用向下调整函数从文件先读取k个数，形成小堆，让后再依次读取文件的数据和堆顶的数据比对，如果比堆顶的数大就覆盖替换，让后向下调整，再形成小堆，最后堆里剩下的就是这些数据里最大的前k个值

注意：1.调用完一次创造数据的函数后，就要注释掉函数，否则每次的值都会是随机生成的，所以回变化不同
2.由于前K个最大值，要建立小堆，所以要调用小堆的向下调整函数接口

3.5.真堆排序

3.5.1.升序 —— （运行展示）

大致思路：升序需要建立大堆，将数组利用大堆的向上调整函数，形成大堆，让后调换顶端的大元素和尾部的小元素，然后再删除尾部的大元素，再调用向下调整函数再次形成大堆，依次这样，最后数组里就形成升序了。

注意：升序是建立大堆，所以调用的都是大堆的函数接口。

3.5.2.降序 ——（运行展示）

大致思路：降序需要建立小堆，将数组利用小堆的向上调整函数，形成小堆，让后调换顶端的小元素和尾部的大元素，然后再删除尾部的小元素，再调用向下调整函数再次形成小堆，依次这样，最后数组里就形成降序了。

注意：升序是建立小堆，所以调用的都是小堆的函数接口。

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
青葱年少的头像青葱年少普通用户
0
上一篇 2023年12月11日
下一篇 2023年12月11日

相关推荐