数据结构:堆

发布于:2025-02-11 ⋅ 阅读:(52) ⋅ 点赞:(0)

目录

1.堆的概念

2.堆的结构

3.堆的初始化

4.堆的销毁

5.堆的插入

6.堆的删除

7.判断堆是否为空


1.堆的概念

堆的性质:

  • 堆中某个结点的值总是不大于或不小于其父结点的值;

  • 堆总是一棵完全二叉树。

以下堆的结构默认大堆 :

2.堆的结构

堆是非线性数据结构,相当于一维数组,有两个直接后继 。

//大堆
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;
	int _size;    //数组中元素的个数
	int _capacity;  //数组的容量
}Heap;

堆是怎样存储在数组中呢?

在数组下标中,若当前节点数组中的下标 i, 则其父节点下标 (i-1)/2,其左子节点的下标为 i*2+1,其右子节点的下标为i*2+1+1

若一个节点的下标为3,其父节点的小标为1,其左孩子节点的下标为7,右孩子结点的下标为8。

3.堆的初始化

/初始化
void HeapInit(Heap* php)
{
	assert(php);
	php->_a = (HPDataType*)malloc(sizeof(HPDataType)*5);
	php->_size = 0;
	php->_capacity = 5;
}

4.堆的销毁

// 堆的销毁
void HeapDestory(Heap* php)
{
	free(php->_a);
	php->_size = 0;
	php->_capacity = 0;
}

5.堆的插入

 首先插入时,判断数组空间是否已满,若满了则扩容,接着在数组的最后进行插入,然后进行向上调整(向上调整就是判断父亲和孩子的大小,若孩子大于父亲则进行交换,)

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustUp(Heap* php, int child)
{
	assert(php);
  // 找到插入节点的父结点的下标
	int parent = (child - 1) / 2;
	while (child > 0)
	{
  //   若孩子结点大于父亲结点,则父亲和孩子进行交换,然后改变父亲结点和孩子结点的下标
		if (php->_a[child] > php->_a[parent])
		{
			Swap(&php->_a[child], &php->_a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
// 堆的插入
void HeapPush(Heap* php, HPDataType x)
{
	assert(php);
	//扩容
	if (php->_size == php->_capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->_a, sizeof(HPDataType) * php->_capacity * 2);
		if (tmp == NULL)
		{
			perror("push::realloc");
			return;
		}
		php->_a = tmp;
		php->_capacity *= 2;
	}
	
	php->_a[php->_size] = x;
	php->_size++;
	//向上调整
	//                插入元素的数组下标
	AdjustUp(php, php->_size - 1);
}

6.堆的删除

这里的删除是删除数组中第一个元素(即最大的的元素),首先将数组中最后一个元素和第一个元素进行交换,然后进行向下调整,满足大堆的条件

void AdjustDown(Heap* php,int n,int parent)
{
	assert(php);
 //找到左孩子
	int child = parent * 2 + 1;
	while (child < n)
	{
		//判断右孩子是否存在, 若存在则将左孩子和右孩子进行比较
        // 若右孩子大于左孩子,则将右孩子与父亲作比较,即child++,找到右孩子下标 
		if (child + 1 < n && php->_a[child] < php->_a[child + 1])
		{
			child++;
		}
		
		//当父母小于孩子时,交换,同时重新赋值父亲结点和孩子结点
		if(php->_a[parent] < php->_a[child])
		{
			Swap(&php->_a[parent], &php->_a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
// 堆的删除
void HeapPop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php));
   //删除头元素
	Swap(&php->_a[0], &php->_a[php->_size - 1]);
	php->_size--;
	//向下调整
    //  需要从根节点进行调整
	AdjustDown(php,php->_size,0);
}

7.判断堆是否为空

// 堆的判空   空1,非空0
int HeapEmpty(Heap* php)
{
	assert(php);
	return php->_size == 0;
}


网站公告

今日签到

点亮在社区的每一天
去签到