大顶堆数组_c语言基础知识[通俗易懂]

大顶堆数组_c语言基础知识[通俗易懂]插入和删除还没写,不过删除逻辑和创建差不多,太晚了,明天写#includestdio.h#includestdlib.htypedefstructheap{ int*data; intsize; intcapa

大顶堆数组_c语言基础知识[通俗易懂]"

一、什么是大顶堆

        堆是树的一种特殊形式,特点如下:

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

        2、堆本身以及其子树根节点一定是最大(大顶堆),或者最小(小顶堆);

二、思路

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

        结点:

        1、data:指向数组的指针

        2、size:堆当前的长度        

        3、capacity:堆的最大容量(因为存数据的地方是数组,所以需要这个)

        函数

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

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

        3、maxnum:没啥好说的,就输出个最大值

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

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

        6、ergodic:遍历:就遍历一下,没啥说的

#include<stdio.h>
#include<stdlib.h>

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("%d\n", p->size);
	p = insert(p);
	printf("%d\n", p->size);
	ergodic(p);
	int a = del(p);
	printf("%d\n", a);
	ergodic(p);
}

heap* establish(heap*p)
{
	printf("please enter  the number of data\n");
	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 established\n");
			p->size = i - 1;
			break;
		}
		if (i==p->capacity-1)
		{
			printf("the heap is established and the capacity is full\n");
			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("%d\n", p->data[i]);
	}
}

heap* insert(heap* p)
{
	//判断是否堆满
	if (p->size==p->capacity-1)
	{
		printf("the capacity of the heap is full\n");
		return p;
	}
	int insertdata;
	printf("please enter the number that you want to insert\n");
	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 empty\n");
		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 && tmp<p->data[parent])
			{
				p->data[parent] = p->data[child];
				p->data[child] = tmp;
			}
			else
			{
				if (tmp<max(p->data[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;
}


今天的文章大顶堆数组_c语言基础知识[通俗易懂]分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/88547.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注