【数据结构】堆(一)

2024-02-29 1598阅读

温馨提示：这篇文章已超过395天没有更新，请注意相关的内容是否还可用！

😛作者：日出等日落

📘 专栏：数据结构

                         如果我每天都找出所犯错误和坏习惯，那么我身上最糟糕的缺点就会慢慢减少。这种自省后的睡眠将是多么惬意啊。

【数据结构】堆(一)

目录

🎄堆的概念及结构：

 🎄堆的实现：

✔基本接口函数：

✔结构体：

✔HeapInit函数： 

✔HeapDestory函数：

✔HeapPrint函数： 

✔HeapPush函数：

✔HeapPop函数：

✔HeapTop函数：

🎄完整代码：

✔Heap.h:

✔Heap.c:

✔Text.c:

🎄堆的概念及结构：

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

堆的性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值
  • 堆总是一棵完全二叉树
  • 简单来说：
  • 父节点都比其的子节点大的完全二叉树叫做大堆。
  • 父节点都比其的子节点小的完全二叉树叫做小堆。

    如图： 

    【数据结构】堆(一)

     【数据结构】堆(一)

     🎄堆的实现：

    ✔基本接口函数：

    //堆的初始化
void HeapInit(HP* hph);
//堆的销毁
void HeapDestory(HP* hph);
//堆的打印
void HeapPrint(HP* hph);
// 堆的插入
void HeapPush(HP * hph, HPDataType x);
// 堆的删除
void HeapPop(HP* hph);
// 取堆顶的数据
HPDataType HeapTop(HP* hph);
// 堆的数据个数
int HeapSize(HP* hph);
// 堆的判空
int HeapEmpty(HP* hph);

    ✔结构体：

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

    ✔HeapInit函数： 

    //堆的初始化
void HeapInit(HP* hph)
{
	assert(hph);
	hph->a = NULL;
	hph->capacity = hph->size = 0;
}

    ✔HeapDestory函数：

    //堆的销毁
void HeapDestory(HP* hph)
{
	assert(hph);
	free(hph->a);
	hph->a = NULL;
	hph->capacity = 0;
	hph->size = 0;
}

    ✔HeapPrint函数： 

    //堆的打印
void HeapPrint(HP* hph)
{
	for (int i = 0; i size; ++i)
	{
		printf("%d ", hph->a[i]);
	}
	printf("\n");
}

    ✔HeapPush函数：

    当capacity==size时扩容（包括初始化的方案），当size==0时，扩容4个空间，否则扩容二倍的空间，capacity也跟着扩大，当push后size++。

    【数据结构】堆(一)

     Swap交换函数：

    void Swap(HPDataType* p1, HPDataType* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
    //向上调整
//child和parent都是下标
void AdjusUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[parent] capacity == hph->size)
	{
		int newcapacity = hph->capacity == 0 ? 4 : hph->capacity * 2;
		HPDataType* tmp = (HPDataType* )realloc(hph->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail:");
			exit(-1);
		}
		hph->a = tmp;
		hph->capacity = newcapacity;
	}
	hph->a[hph->size] = x;
	hph->size++;
	//向上调整
	AdjusUp(hph->a, hph->size - 1);
}

    ✔HeapPop函数：

    出堆顶的元素，让第一个位置的值和最后一个位置的值交换，再size--就相当于删除了，但交换上去的值在根节点的位置上，我们无法维持是大堆的情况，因此还需要向下调整Ajustdown。

     【数据结构】堆(一)

    //向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child  a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
// 堆的删除
void HeapPop(HP* hph)
{
	assert(hph);
	assert(!HeapEmpty(hph));
	Swap(&hph->a[0], &hph->a[hph->size - 1]);
	hph->size--;
	AdjustDown(hph->a, hph->size, 0);
}

    ✔HeapTop函数：

    // 取堆顶的数据
HPDataType HeapTop(HP* hph)
{
	assert(hph);
	assert(hph->size > 0);
	return hph->a[0];
}

    🎄完整代码：

    ✔Heap.h:

    #define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 
#include 
#include 
typedef int HPDataType;
typedef struct heap
{
	HPDataType* a;
	int capacity;
	int size;
}HP;
//堆的初始化
void HeapInit(HP* hph);
//堆的销毁
void HeapDestory(HP* hph);
//堆的打印
void HeapPrint(HP* hph);
// 堆的插入
void HeapPush(HP * hph, HPDataType x);
// 堆的删除
void HeapPop(HP* hph);
// 取堆顶的数据
HPDataType HeapTop(HP* hph);
// 堆的数据个数
int HeapSize(HP* hph);
// 堆的判空
int HeapEmpty(HP* hph);

    ✔Heap.c:

    #define _CRT_SECURE_NO_WARNINGS 1
#include "heap.h"
//堆的打印
void HeapPrint(HP* hph)
{
	for (int i = 0; i size; ++i)
	{
		printf("%d ", hph->a[i]);
	}
	printf("\n");
}
//堆的初始化
void HeapInit(HP* hph)
{
	assert(hph);
	hph->a = NULL;
	hph->capacity = hph->size = 0;
}
//堆的销毁
void HeapDestory(HP* hph)
{
	assert(hph);
	free(hph->a);
	hph->a = NULL;
	hph->capacity = 0;
	hph->size = 0;
}
void Swap(HPDataType* p1, HPDataType* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向下调整
//child和parent都是下标
void AdjusUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[parent] capacity == hph->size)
	{
		int newcapacity = hph->capacity == 0 ? 4 : hph->capacity * 2;
		HPDataType* tmp = (HPDataType* )realloc(hph->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail:");
			exit(-1);
		}
		hph->a = tmp;
		hph->capacity = newcapacity;
	}
	hph->a[hph->size] = x;
	hph->size++;
	//向下调整
	AdjusUp(hph->a, hph->size - 1);
}
//向上调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child  a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
// 堆的删除
void HeapPop(HP* hph)
{
	assert(hph);
	assert(!HeapEmpty(hph));
	Swap(&hph->a[0], &hph->a[hph->size - 1]);
	hph->size--;
	AdjustDown(hph->a, hph->size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(HP* hph)
{
	assert(hph);
	assert(hph->size > 0);
	return hph->a[0];
}
// 堆的数据个数
int HeapSize(HP* hph)
{
	assert(hph);
	return hph->size;
}
// 堆的判空
int HeapEmpty(HP* hph)
{
	assert(hph);
	return hph->size == 0;
}

    ✔Text.c:

    #define _CRT_SECURE_NO_WARNINGS 1
#include "heap.h"
void Heap()
{
	int arry[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
	HP hph;
	HeapInit(&hph);
	HeapPrint(&hph);
	for (int i = 0; i
VPS购买请点击我

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

相关阅读

目录[+]