C语言_堆的基本操作_请设计int empty(heap h)函数。 该函数判断堆h是否空堆,如果是空堆返回1,否则返回

本片博客主要包含一下几个内容：

堆的基本操作

1、创建堆

2、调整堆（向下调整）

3、插入

4、移除堆顶元素

5、返回堆元素个数

6、判断是不是空堆

7、返回堆顶元素

8、向上调整堆

9、交换两个数

10、判断堆是否已满，如果满了，就增容；如果没有满，就返回

11、销毁堆

12、小于比较

13、大于比较

14、头文件代码

15、测试代码

---

 

---

1、创建堆

---

void CreateHeap(Heap *hp, HPDataType* arr, int size, Compare Com)
{
	int cur = 0;
	assert (hp != NULL);
	hp->_hp = (HPDataType*)malloc (size * sizeof (HPDataType));
	if (hp->_hp == NULL)
	{
		assert (0);
		return ;
	}
	//拷贝元素
	memcpy (hp->_hp, arr, size*sizeof (HPDataType));
	hp->size = size;
	hp->capacity = size;
	hp->_com = Com;
	//调整成堆
	cur = ((size-1-1)>>1);	//size-1为最大下标，再减一除二为最后一个节点的双亲节点
	for (; cur>=0; cur--)
	{
		AdjustDown (hp, cur);//向下调整堆
	}
}

---

2、调整堆（向下调整）

---

void AdjustDown (Heap* hp, int parent)//parent 为开始调整的节点
{
	int child = 0;
	assert (hp != NULL);
	child = (parent<<1) + 1;  //孩子节点等于双亲节点乘二加一
	while (child < hp->size)
	{
		if (child+1 < hp->size)//如果右孩子存在，找左右孩子中最小的孩子
		{
			if (hp->_com (hp->_hp[child], hp->_hp[child+1]))
			{
				child += 1;
			}
		}
 
		if (hp->_com(hp->_hp[parent], hp->_hp[child]))
		{
			Swap (&hp->_hp[parent], &hp->_hp[child]);
		}
		else
		{
			return;
		}
		parent = child;
		child = (parent<<1) + 1;
	}
 
}

---

3、插入

 

void InsertHeap (Heap* hp, HPDataType data)	//插入元素
{
	assert (hp != NULL);
	//判断还有没有空间，有的话就插入元素，没有就增容再插入元素
	CheakHeap (hp);
	hp->_hp[hp->size] = data;
	hp->size++;
	//向上调整堆
	AdjustUp (hp, (hp->size)-1);
 
}

---

---

4、移除堆顶元素

//移除元素，（把堆顶元素和最后一个元素交换，size--就把堆顶元素删除了，最后在调整一下堆顶元素）
 
void RemoveHeap (Heap* hp)
{
	assert (hp != NULL);
	Swap (&hp->_hp[0], &hp->_hp[hp->size-1]);
	hp->size--;
	AdjustDown (hp, 0, hp->_com);
}

---

5、返回堆元素个数

---

int SizeHeap (Heap* hp)	//返回堆元素个数
{
	assert (hp != NULL);
	return hp->size;
}

---

6、判断是不是空堆

---

int IsHeapEmpty (Heap* hp)	//判断是不是空堆，空堆返回1，非空返回0
{
	assert (hp != NULL);
	return (hp->size == 0);
}

---

7、返回堆顶元素

---

HPDataType HeapTop (Heap* hp)	//返回堆顶元素
{
	assert (hp != NULL);
	return hp->_hp[0];
}

---

8、向上调整堆

---

void AdjustUp (Heap* hp, int child)
{
	int parent = 0;
	assert (hp != NULL);
	parent = (child - 1)/2;
	while (child)
	{
		if (!(hp->_com(hp->_hp[child], hp->_hp[parent])))
		{
			Swap (&hp->_hp[child], &hp->_hp[parent]);
		}
		child = parent;
		parent = (child - 1)/2;
	}
 
}

---

9、交换两个数

---

void Swap (HPDataType*p, HPDataType* q)
{
	HPDataType tmp;
	assert (p != NULL && q != NULL);
	tmp = *p;
	*p = *q;
	*q = tmp;
}

 

---

10、判断堆是否已满，如果满了，就增容；如果没有满，就返回

---

void  CheakHeap (Heap* hp)	//判断堆是否已满，如果满了，就增容；如果没有满，就返回
{
	int newCapacity = 0;
	int i = 0;
	HPDataType* temp;
	assert (hp != NULL);
	if (hp->capacity > hp->size)
	{
		return ;
	}
	//如果堆已满，增容
	newCapacity = 2 * (hp->capacity)+3;
	temp = (HPDataType*)malloc (newCapacity * sizeof (HPDataType));	//开辟新空间
	if (temp == NULL)
	{
		perror ("CheakHeap::malloc>>");
		return ;
	}
	//拷贝元素
	for (; i<hp->size; ++i)	
	{
		temp[i] = hp->_hp[i];
	}
	//释放原空间
	free (hp->_hp);
	hp->_hp = NULL;
	
	//让原空间指向新开辟的空间
	hp->_hp = temp;
	hp->capacity = newCapacity;
}

---

11、销毁堆

---

void DestroyHeap (Heap* hp)
{
	assert (hp != NULL);
	free (hp->_hp);
	hp->_hp = NULL;
	hp->capacity = 0;
	hp->size = 0;
	printf ("销毁成功\n");
}

---

12、小于比较

---

//Less 和 Greater两个函数用来比较两个数的大小，在建堆时用函数指针的形式调用，用来分别建大堆小堆
int Less (HPDataType pLeft, HPDataType pRight)	//小于比较
{
	assert (pLeft != NULL && pRight != NULL);
	if (pLeft > pRight)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

---

13、大于比较

---

int Greater (HPDataType pLeft, HPDataType pRight)	//大于比较
{
	if (pLeft > pRight)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

---

14、头文件代码

---

#ifndef __HEAP_H__
#define __HEAP_H__
 
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
 
//堆：是一个数组，其中的元素是按照二叉树的顺序在数组中存放的
 
	//任意一个节点的数据都比其左右孩子都小---小堆
	//任意一个节点的数据都比它的左右孩子大---大堆
typedef int HPDataType;
typedef int (*Compare) (HPDataType pLeft, HPDataType pRight);
 
typedef struct Heap
{
	HPDataType* _hp;
	int capacity;
	int size;
	Compare _com;
}Heap;
 
 
void CreateHeap(Heap *hp, HPDataType* arr, int size, Compare Com);	//创建堆
void AdjustDown (Heap* hp, int parent);	//调整堆（向下调整）
void InsertHeap (Heap* hp, HPDataType data);	//插入
void RemoveHeap (Heap* hp);	//移除元素，（把堆顶元素和最后一个元素交换，size--就把堆顶元素删除了，最后在调整一下堆顶元素）
int SizeHeap (Heap* hp);	//返回堆元素个数
int IsHeapEmpty (Heap* hp);	//判断是不是空堆
HPDataType HeapTop (Heap* hp);	//返回堆顶元素
void AdjustUp (Heap* hp, int child);	//向上调整堆
void Swap (HPDataType* p, HPDataType*q);	//交换两个数
void  CheakHeap (Heap* hp);	//判断堆是否已满，如果满了，就增容；如果没有满，就返回
void DestroyHeap (Heap* hp);	//销毁堆
int Less (HPDataType pLeft, HPDataType pRight);	//小于比较
int Greater (HPDataType pLeft, HPDataType pRight);	//大于比较
 
 
#endif 

---

15、测试代码

---

#include "Heap.h"
 
void test_Heap()
{
	//test_CreateHeap
	int ret = 0;
	HPDataType top = 0;
	int arr[] = {53, 17, 78, 9, 45, 65, 87, 23, 31};
	Heap hp;
	CreateHeap (&hp, arr, sizeof(arr)/sizeof(arr[0]), Less);
	//test_SizeEmptyTopHeap
	ret = SizeHeap(&hp);
	printf ("堆的大小为：%d\n", ret);
	ret = IsHeapEmpty(&hp);
	if (ret == 1)
	{
		printf ("这是空堆！\n");
	}
	else
	{
		printf ("不是空堆！\n");
	}
	top = HeapTop(&hp);
	printf ("堆顶元素是：%d\n", top);
	//test_InsertHeap
	InsertHeap(&hp, 5);
	//test_RemoveHeap
	RemoveHeap(&hp);
	DestroyHeap (&hp);
}
 
int main ()
{
	test_Heap();
	return 0;
}