前言(萌新感想):

以前用STL的queue啊stack啊priority_queue啊,一直很想懂原理,现在终于课上到了priority_queue,还有就是下周期中考,哈哈,所以写几篇blog总结一下。

这里萌新讲下堆这个好东西;

堆的定义:

如果搞过ACM的童鞋应该会使用STL的priority_queue,堆就是STL的priority_queue。

堆是一种特殊的队列,从堆中取元素的依据是元素优先权大小,而不是元素进入队的先后顺序;



直接切入主题吧;





最常用的结构是二叉树,一棵完全二叉树,而完全二叉树由于其结点特别规律,所以可以用数组直接模拟。

下面介绍几个堆(以完全二叉树的形式):

萌新笔记之堆(heap)-LMLPHP

最大堆:每个结点上的元素不小于其子节点元素的值;

最小堆:每个结点上的元素不大于其子节点元素的值;





拿最大堆来讲几个操作:

创建,插入,删除,建立最大元素;

下面参考自陈越姥姥版数据结构

用C语言(窝觉得好**)描述最大堆结构;

先定义:

typedef struct HeapStruct* MaxHeap;
struct HeapStruct
{
int *Elements; //存储元素的数组;
int Size; //堆的当前元素;
int Capacity; //堆的最大容量;
};

有人会说,卧槽为什么要结构体啊,明明说好的数组可以直接处理,为毛不用数组啊,而且结构体里面还有指针,好烦(繁)啊!

萌新想说,这样严谨吧,其实差不多啊,无非是换种方式而已;PS:ACM中不是很常用指针吧,说错,不是不常用指针,而是不常用动态开辟内存,时间很慢。

而且指针如果用的灵活,那是很超神的能力啊!


创建最大堆:

其实。。。他就是动态开辟了一个内存,然后存了一个东西。初学者不用太深究(搞不懂就先放放,先吃西瓜,再捡芝麻)。
MaxHeap Creat(int MaxSize)  //创建容量为MaxSize 空的最大堆
{
MaxHeap H;
int INF=0x3f3f3f3f;
H=(MaxHeap)malloc(sizeof(struct HeapStruct)); //都是动态开辟内存,不用深究
H->Elements=(int *)malloc((MaxSize+1)*sizeof(int));
H->Size=0; //初始化为0;
H->Elements[0]=INF; //作为一个”哨兵“为大于堆中所有可能元素的值;
return H;
}

最大堆的插入:

首先判断堆 是不是已经满了;





我们先假设这个元素插在了Size+1这个结点上,

①:他比他的父节点的值小,OK,那就躺着吧,插入完成;

②:可惜他比他的父节点大啊,那么。。。交换就好了嘛,交换以后一定是合法的啊。

这里有一种写法很牛逼啊,比普通交换好很多;

void Insert(MaxHeap H,int item)     //item 是要插入的元素,这里称目标;
{
int i;
if(isFull(H)) //先判断一下是不是已经满了
{
printf("最大堆已满\n");
return;
}
i=++H->Size; //先默认目标被插在了新开的结点
//对下面的循环细说一下,如果目标比他的父节点大的话,那么交换,可以看到目标并没有存到父节点上,然后i/=2使得往上继续判断,如果>目标就会弹出循环;
//最后很有可能他成了整个完全二叉树的根,这里目标的编号是1,所以这个编号0就发挥作用了,一定比他大啊;
for( ; H->Elements[i/2] < item; i/=2)
H->Elements[i]=H->Elements[i/2];
H->Elements[i]=item;
}

最大堆的删除:

萌新把 根 称做爷爷吧。

一开始爷爷做主。

我们浅显地可以看到拿走了最大的元素(即爷爷被带走了),那么肯定就是要个大的子结点(最大的爸爸)来顶替他的位置。

然后处理大的那个子节点被顶替上去了,所以又要安排一个最大的孙子顶替。

所以一直一直要处理好,但是你这样一直一直顶替会有个问题,可能会构造不成一棵完全二叉树。
处理方法是把最后一个元素拿出来,以这个元素作为替补,因为根已经被删除了,然后就从根往下遍历,如果一旦存在这个元素可以填的位置,就填上去,一定能够保证是一个完全二叉树了;

bool isFull(MaxHeap H)
{ }
void DeleteMax(MaxHeap H)
{
int Parent,Child;
int temp;
if(IsEmpty(H))
{
printf("堆为空\n");
return;
}
temp=H->Elements[H->Size--]; //取末尾元素
//从根开始填
for(Parent=1; Parent*2<=H->Size; Parent = Child)
{
Child=Parent*2;
if(Child!=H->Size&&(H->Elements[Child+1]>H->Elements[Child])) //如果没有右儿子就是左儿子,如果有在左右儿子节点找一个大的,
Child++;
if(temp>=H->Elements[Child]) //如果比末尾元素比两个儿子都大,直接填他就行了
break;
else
H->Elements[Parent]=H->Elements[Child]; //不是的话就替换,然后往下继续判断;
}
H->Elements[Parent]=temp;
}

最大堆的建立:

大致思路就是从底层开始判断,因为完全二叉树的编号很规律,从size/2也就是最后一个结点的父节点开始判断,每次往下看看这个结点能放到哪个位置,

然后依次减减减,也就是判断每一层的结点啊;
void BuildMaxHeap(MaxHeap H)
{
int i,Parent,Child;
int temp;
for(i=H->Size/2; i>0 ; --i)
{
temp=H->Elements[i];
for(Parent=i; Parent*2<=H->Size; Parent=Child)
{
Child=Parent*2;
if(Child!=H->Size&&(H->Elements[Child+1]>H->Elements[Child])) //如果没有右儿子就是左儿子,如果有在左右儿子节点找一个大的,
Child++;
if(temp>=H->Elements[Child]) //如果比末尾元素比两个儿子都大,直接填他就行了
break;
else
H->Elements[Parent]=H->Elements[Child]; //不是的话就替换,然后往下继续判断;
}
H->Elements[Parent]=temp;
}
}

OK,欢迎提出意见~~~~~

04-28 04:04