一、什么是大顶堆
堆是树的一种特殊形式,特点如下:
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