【数据结构 —— 堆的实现(顺序表)】

数据结构 —— 堆的实现(顺序表)

  • 一.堆
    • 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.降序 ——(运行展示)

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

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

在这里插入图片描述