数据结构——堆

2024-01-14 11:03:13 作者:欧亿体育


Hello,我们又见面了,今天讲的是堆,是数据结构里的堆,可不是我们C语言的堆区那个,今天这篇文章我们写一个数组堆,然后实现堆排序的功能,废话不多说,开始我们今天的学习吧!!

堆的概念与性质

堆是计算机中的一类特殊的数据结构的统称。堆通常是可以被看做一颗完全二叉树的数组对象.

堆的性质:

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

堆又分为大小堆,大堆的特点就是父亲是最大的,后面我会补文章来讲解数的一些概念,小堆就是父亲是最小的

举列子给大家看可能更好的理解。


上面的是小堆,因为我们的父亲最小,下面的是大堆,父亲是最大的数

那我们有没有想过堆的作用是什么
第一个作用就是解决堆排序的问题,我们可以用它来排序数组,因为数组是我们的物理结构,但是不是任何数组都可以用来排序的,我们还得满足它的逻辑结构,那就是左右必须得是子数,满足大小堆的结构.
那我们先来实现一个数组堆,和之前的顺序表和链表一样,我们有我们的结构。


typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType* arry;
	int size;
	int capacity;
}Heap;

这么一看我们定义的结构体就是我们顺序表定义过的结构体!!!

那我们的接口函数实现

typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType* arry;
	int size;
	int capacity;
}Heap;


void HeapInit(Heap* php);

void HeapDestory(Heap* php);

void HeapPrint(Heap* php);

bool HeapEmpty(Heap* php);

void HeapPush(Heap* php, HeapDataType x);

void HeapPop(Heap* php);

HeapDataType HeapTop(Heap* php);

int HeapSize(Heap* php);

那我们一个一个来实现吧,首先就是我们的初始化堆,这个很简单,和顺序表一摸一样的操作就可以实现,我们来看一下吧


void HeapInit(Heap* php)
{
	assert(php);
	php->arry = NULL;
	php->capacity = php->size = 0;
}

这个应该很简单来了,对于我们来说,不懂可以看前面的文章去看看
有了初始化就有销毁,销毁的时我们动态开辟的空间。我们也来实现一下吧

void HeapDestory(Heap* php)
{
	assert(php);
	free(php->arry);

}
现在我们继续实现堆打印的函数
void HeapPrint(Heap* php)
{
	assert(php);
	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->arry[i]);
	}
	printf("\n");
}

遍历一遍数组其实就能实现,因为我们的物理结构就是数组,所以这里很简单,接下来就是怎么放入数组,这个有点难里面有好几个接口函数需要我们手动实现,这里我们拿小堆升序来讲

首先我们插入,应该是从他的尾巴插入,就是数组最后一个,插入的话,我们是不是需要实现一个接口函数检查受否要扩容,检查这个扩容我们已经实现过好几次了,这里我就不讲解了,然后我们需要把要插入的数放进去,size++就行了,但是插入一个数之后,二叉数堆就不是我们之前的小堆,需要进行调整,这里我们就用一个巧妙的方法,向上调整,调整我们的数到合适位置,调整比较的是它的祖先,而不是随意的进行比较,因为我们的堆是小堆,所以这个数如果比他的祖先小,就需要进行调整,最坏的就是这个数是最小的,这时候我们要给定一个条件来结束调整。那我们先来看一下完整的代码吧

void swap(HeapDataType* p1, HeapDataType* p2)
{
	HeapDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;

}
void Adjustup(HeapDataType* arry, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arry[child] < arry[parent])
		{
			swap(&arry[child], &arry[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HeapPush(Heap* php, HeapDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HeapDataType* tmp = (HeapDataType*)realloc(php->arry, sizeof(HeapDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->arry = tmp;
		php->capacity = newcapacity;
	}
	php->arry[php->size] = x;
	php->size++;
	Adjustup(php->arry, php->size - 1);

}

这就是我们的调整,我们走读代码来到调整的部分,我们比较的是父亲和孩子,如果孩子比父亲小就进行交换,反之退出循环,还可以用递归的方法来写,但是一般情况下堆不会使用。

有了数据的插入就有数据的删除,来看看删除的向下调整,也是同样的思路。

void AdjustDown(HeapDataType* arry, int size, int parent)
{
	int child = 2 * parent + 1;
	if (child+1<size && arry[child + 1] < arry[child])
	{
		child++;
	}
	while (child < size)
	{
		if (arry[parent] > arry[child])
		{
			swap(&arry[parent], &arry[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapPop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	swap(&(php->arry[0]), &(php->arry[php->size - 1]));
	php->size--;
	AdjustDown(php->arry, php->size, 0);
}

这个内容主要就是讲pop和push这两个,其他结构函数这里小编一并实现了,不是特别难,我们来看看吧

HeapDataType HeapTop(Heap* php)
{
	assert(php);
	return php->arry[0];
}


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

这两个一个是取出堆顶的数,就是我们的根,第二个是个数。
还有与一个判断堆是否是空的函数,让我们一起来看看吧


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

完整代码

#pragma once
#include
#include
#include
#include


typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType* arry;
	int size;
	int capacity;
}Heap;


void HeapInit(Heap* php);

void HeapDestory(Heap* php);

void HeapPrint(Heap* php);

bool HeapEmpty(Heap* php);

void HeapPush(Heap* php, HeapDataType x);

void HeapPop(Heap* php);

HeapDataType HeapTop(Heap* php);

int HeapSize(Heap* php);
#include"Heap.h"


void HeapInit(Heap* php)
{
	assert(php);
	php->arry = NULL;
	php->capacity = php->size = 0;
}

void HeapDestory(Heap* php)
{
	assert(php);
	free(php->arry);

}


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

bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0;
}
void swap(HeapDataType* p1, HeapDataType* p2)
{
	HeapDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;

}
void Adjustup(HeapDataType* arry, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arry[child] < arry[parent])
		{
			swap(&arry[child], &arry[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HeapPush(Heap* php, HeapDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HeapDataType* tmp = (HeapDataType*)realloc(php->arry, sizeof(HeapDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->arry = tmp;
		php->capacity = newcapacity;
	}
	php->arry[php->size] = x;
	php->size++;
	Adjustup(php->arry, php->size - 1);

}
void AdjustDown(HeapDataType* arry, int size, int parent)
{
	int child = 2 * parent + 1;
	if (child+1<size && arry[child + 1] < arry[child])
	{
		child++;
	}
	while (child < size)
	{
		if (arry[parent] > arry[child])
		{
			swap(&arry[parent], &arry[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapPop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	swap(&(php->arry[0]), &(php->arry[php->size - 1]));
	php->size--;
	AdjustDown(php->arry, php->size, 0);
}

HeapDataType HeapTop(Heap* php)
{
	assert(php);
	return php->arry[0];
}


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

懒得去测试了,大家就这样看看吧,那今天的分享就到这里,我们后面讲讲怎么用堆来实现堆排序吧

在线咨询 拨打电话

电话

010-67916526

微信二维码

微信二维码