前言:堆当然也可以使用 STL 里的 priority_queue ,可以参考浅谈STL,不过优先队列有时候不够灵活,不能完成特殊操作。
文中如有错误还望指出

概念浅析

堆,就是利用二叉树,保证每次从数中取出优先级最高的一个元素,解释为优先队列会更好理解。
它能保证无论在什么时候,根节点一定是树中优先级最高的元素。
概念在后面还会再解释一些,实在不懂可以百度。
这里为了演示方便,做的是大根堆,也就是根节点是树中最大的元素。

主要函数

MaxHeap Create(int MaxSize);                      //建造一个大根堆
bool IsFull(MaxHeap x);                           //判断堆是否为满
void Insert (MaxHeap H,ElementType x);            //将x插入到大根堆
ElementType Delete(MaxHeap x);                    //返回堆顶最大值并删除

实现过程

首先,你需要有一个储存堆的结构体。

Struct MaxHeap{
    ElementType *Elements;    //堆中元素
    int size;                 //当前堆的大小
    int MaxSize;              //堆的最大大小
}

然后,是 Create 函数的实现。

MaxHeap Create (int MaxSize){
    MaxHeap H = malloc( sizeof(MaxHeap) );                        //动态分配内存
    H->Elements=malloc( (MaxSize + 1) * sizeof( ElementType ) );
    //为指定大小的堆动态分配内存,由于下标从1开始,所以要分配MaxSize+1个元素
    H->size=0;                                                    //当前没有元素,所以当前堆大小为0
    H->MaxSize=MaxSize;                                           //最大大小大作参数传入
    H->Elements[0] = MaxData;                                     //MaxData为哨兵,不用着急,后面会谈到
    return H;                                                     //返回这个对堆
}

bool IsFull(MaxHeap x)

这个的实现就很简单了,只需要判断当前元素个数是不是上限个数即可。

bool IsFull(MaxHeap x){
    return x->size >= MaxSize-1;   //判断当前元素是不是元素上限,最好MaxSize要多预留一个空间
}

void insert (MaxHeap H,ElementType x)

这个的实现就牵扯到大根堆的原理了。
而大根堆就是利用二叉树实现的,顾名思义,大根堆,说明根节点是整棵树中最大的。而其中结点的两个子树值,都小于这个结点,然后利用完全二叉树来实现。例如下面两张图都是大根堆:

堆1
堆2

在图中可见,56>40>19,19>18>9,40>3,21>10满足大根堆的定义。
插入的问题首先是要插入到哪,显然应该插入到Elements[++size]里。
但是如果插入一个元素,就有可能不再是大根堆,例如:

堆3

在这张图中,新插入一个元素56,而13<56,所以不符和大根堆的定义。问题是怎么调整呢?
一个方法就是将56与其父节点比较,如果56大于它的父节点,就让它的父节点代替自己的位置,依次向上直到根节点。显然在数组模拟的完全二叉树中,一个结点的父亲的编号就是自己的编号除以2(下取整),例如6号的父亲是3,5号的父亲是2。这样就能很容易地写出代码了。

void insert(MaxHeap H,ElementType x){
    H->Elements[++H->size]=x;
    int i;
    for(i=size;H->Elements[i]>H->Elements[i/2];i/=2)
        H->Elements[i]=Elements[i/2];
        //例如上面的图,i出来循环后值应该为1,因为他是树中最大的嘛。
        //但是在这个代码中,i/2是有可能指向0的,所以我们要在Elements[0]设一个极大值保证没有元素会跑到0这个点或者加个i>=1的条件
        //这就是Elements[0]在前面讲到的MaxData
    H->Elements[i]=x;
}

ElementType Delete(MaxHeap x)

删除大根堆的元素就是把大根堆的根节点删除。因为大根堆的特点不符合二叉搜索树,所以是不能用二叉搜索树的方法的。
其中一个解决方式就是用堆中的最后一个元素代替,之后再进行调整操作。
这个调整操作怎么实现呢?试想一下,一个大根堆的根节点一定是最大的,而每个结点又是一个根节点。也就是说,当大根堆中的根节点去掉后,这个根节点的左右孩子中最大的一个就是这个堆中的最大元素了。所以当我们拿最后一个结点替换根结点时,只需要将其与左右孩子中最大的元素作比较即可。如果这个结点小,就拿大的结点覆盖掉它,直到碰上比自己小的结点。

ElementType Delete(MaxHeap x){
    //函数作用:返回根节点值并将其删除
    int parent,child;
    ElementType MaxItem,tmp;            //tmp是用来替换根节点的值
    MaxItem=x->Elements[1];             //MaxItem是一会要返回的根节点值
    tmp=x->Elements[size--];            //tmp的值为第一个替换掉根节点的元素的值,即编号最后的那个结点
    for(parent=1;parent*2<x->size;parent=child){
        child=parent*2;                //假设左儿子比较大
        if(child!=x->size && x->Elements[child]<x->Elements[child+1])++child;
        //如果有右儿子,且右儿子比左儿子大,那么child指向右儿子
        if(tmp > x->Elements[child])break;            //如果tmp比自己的儿子大,tmp就可以待在这个位置,就break
        else x->Elements[parent]=x->Elements[child];  //否则就把parent所在的结点的值改为child的值,也可以用swap
    }
    x->Elements[parent]=tmp;                          //如果前面用的是swap,这里就可以不要了。其实用swap更好理解
    return MaxItem;
}

完结撒花✿
部分图片/代码来源:MOOC牛逼

发表评论

邮箱地址不会被公开。