c语言实现大顶堆思路及代码

c语言实现大顶堆思路及代码

一、什么是大顶堆

        堆是树的一种特殊形式，特点如下：

        1、一定是一颗完全二叉树；

        2、堆本身以及其子树根节点一定是最大（大顶堆），或者最小（小顶堆）；

二、思路

        创建大顶堆，我们需要创建以下东西

        结点：

        1、data：指向数组的指针

        2、size：堆当前的长度        

        3、capacity：堆的最大容量（因为存数据的地方是数组，所以需要这个）

        函数

        1、establish：创建堆，这一步中前面是将数据依次放入数组，不管数据大小，之后再利用adjust函数调整成堆；

        2、adjust：调整堆，具体思路是从下往上调整，先调整最后一个有子节点的父节点，调整好后再调整前一个父节点，直到调整到第一个节点为止；

        3、maxnum：没啥好说的，就输出个最大值

        4、insert：往堆中插入数据，思路是直接插到最后一个节点，然后把他和父节点比较，如果比父节点大，就和父节点调换位置，直到插入数据小于它的父节点，因为本身就是插入堆中，所以调换之后他还会是个堆

        5、del：删除数据，堆中最大值，因为本来就是个大顶堆，所以就是删除根节点，再把最后一个节点放到第一个节点，再用第一个节点从上往下调整，思路和insert差不多

        6、ergodic：遍历：就遍历一下，没啥说的

#include
#include

typedef struct heap
{
	int* data;
	int size;
	int capacity;
}heap;

//函数：1.创建堆：返回指针、2.插入：返回指针、3.删除：返回数据、4.遍历：直接输出不返回、5.调整：返回指针、6.最大值：返回数字
heap* establish(heap*p);
heap* adjust(heap* p);
int maxnum(int a, int b);
heap* insert(heap* p);
int del(heap* p);
void ergodic(heap* p);

int main()
{
	heap* p = (heap*)malloc(sizeof(heap));
	p = establish(p);
	printf("%dn", p->size);
	p = insert(p);
	printf("%dn", p->size);
	ergodic(p);
	int a = del(p);
	printf("%dn", a);
	ergodic(p);
}

heap* establish(heap*p)
{
	printf("please enter  the number of datan");
	int max;
	scanf("%d", &max);
	p->capacity = max + 1;
	p->data = (int*)malloc(sizeof(int) * p->capacity);
	p->data[0] = 9999;
	printf("please enter the data you want to type ,999 means end n");
	for (int i = 1;; i++)
	{
		scanf("%d", &p->data[i]);
		if (p->data[i]==999)
		{
			printf("the heap is establishedn");
			p->size = i - 1;
			break;
		}
		if (i==p->capacity-1)
		{
			printf("the heap is established and the capacity is fulln");
			p->size = p->capacity-1;
			break;
		}
	}
	p = adjust(p);
	return p;
}

int maxnum(int a, int b)
{
	return a > b ? a : b;
}

heap* adjust(heap* p)
{
	int lastparent, child;
	int parent = p->size / 2;
	for (; parent > 0; parent--)
	{
		lastparent = parent;
		child = parent * 2;
		for ( ; lastparent*2 <= p->size ; lastparent=child)
		{
			child = lastparent * 2;
			if (child == p->size)//only left child
			{
				int tmp = p->data[child];
				if (p->data[child] > p->data[lastparent])
				{
					p->data[child] = p->data[lastparent];
					p->data[lastparent] = tmp;
				}
			}
			else //have two childs
			{
				if (p->data[lastparent] < max(p->data[child], p->data[child + 1]))
				{
					if (p->data[child + 1] > p->data[child])
					{
						child++;
						int tmp = p->data[child];
						p->data[child] = p->data[lastparent];
						p->data[lastparent] = tmp;
					}
					else
					{
						int tmp = p->data[child];
						p->data[child] = p->data[lastparent];
						p->data[lastparent] = tmp;
					}
				}
			}
		}
	
	}
	return p;
}

void ergodic(heap* p)
{
	int i = 1;
	for ( ; i <= p->size; i++)
	{
		printf("%dn", p->data[i]);
	}
}

heap* insert(heap* p)
{
	//判断是否堆满
	if (p->size==p->capacity-1)
	{
		printf("the capacity of the heap is fulln");
		return p;
	}
	int insertdata;
	printf("please enter the number that you want to insertn");
	scanf("%d", &insertdata);
	int child = ++p->size;
	p->data[p->size] = insertdata;
	for (int parent =child/2; insertdata>p->data[parent]; )
	{
		int tmp = p->data[parent];
		p->data[parent] = insertdata;
		p->data[child] = tmp;
		child = parent;
		parent /= 2;
	}
	return p;
}

int del(heap* p)
{
	//判断是否堆空
	if (p->size==0)
	{
		printf("the heap is emptyn");
		return 0;
	}
	int data = p->data[1];
	int tmp = p->data[p->size--];
	p->data[1] = tmp;
	int parent = 1;
	int child;
	if (p->size==parent)
	{
		return data;
	}
	else
	{
		for (; parent*2 <= p->size; parent=child)
		{
			child = parent * 2;
			if (parent*2==p->size && tmpdata[parent])
			{
				p->data[parent] = p->data[child];
				p->data[child] = tmp;
			}
			else
			{
				if (tmpdata[child], p->data[child+1]))
				{
					if (p->data[child] > p->data[child + 1])
					{
						p->data[parent] = p->data[child];
						p->data[child] = tmp;
					}
					else
					{
						child++;
						p->data[parent] = p->data[child];
						p->data[child] = tmp;
					}
				}
			}
		}
	}
	return data;
}