当前位置:编程学习 > C/C++ >>

C++ 堆结构(数组实现)

要说最大堆和最小堆,就得先知道最大树和最小树。

每个结点的值都大于(小于)或等于其子节点(如果有的话)值的树,就叫最大(最小)树。

最大堆(最小堆)是最大(最小)完全树。

由于堆是完全二叉树,所以可以用公式化描述,用一维数组来有效的描述堆结构。

利用二叉树的性质:

如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第[log2n]向下取整+1层,每层从左到右),则对任一结点i(1≤i≤n),有:

(1)如果i=1,则结点i无双亲,是二叉树的根;如果i>1,则其双亲是结点[i/2]向下取整。

(2)如果2i>n,则结点i为叶子结点,无左孩子;否则,其左孩子是结点2i。

(3)如果2i+1>n,则结点i无右孩子;否则,其右孩子是结点2i+1。

这样就就可以将堆中结点移到它的父节点或者其中一个子节点处。

堆中进行的操作主要是:插入,删除,以及初始化。

下面只讨论最大堆。

在最大堆中进行插入操作,例如在下图所示的左边的最大堆中进行插入,插入后结构应该是和右边的图一样的。

\
插入时,现将新元素从新堆的父节点开始比较,也就是先从2所在结点开始比较,如果小于父节点的值,那么就直接作为孩子结点插入,如果大于,那么就要现将父节点下移,然后再和父节点的父节点比较,一直比较到根节点为止,所以插入过程,是从叶节点到根的一条路径。

最大堆的删除,从最大堆的删除时,该元素从根部移出。删除后,此时堆需要重新构造,以便于仍然为完全二叉树。例如下图:

\
先将根节点的值20取出后,为了结构仍然是二叉树,所以直接将最后一个结点,也就是保存2的结点去掉,然后将2的值保存下来,然后呢,就从根节点的两个孩子开始比较,看看2 根的左右孩子,这三个元素中,谁最大,那么根节点的值就是谁,然后就将2和空出来的结点的左右孩子(如果有的话)比较,确认子树的根节点的值,这样一步一步确认下去。

用数组初始化堆,数组元素显示按照下面的顺序,一个一个放在结点中

\
然后就从最后一个父节点开始,就是第五个结点,10所在的位置啦,从那里开始构造以该节点为根的最大堆。构造好后就移到下一个结点,15所在结点,以此类推,一直到根节点。

下面是代码:

文件"maxheap.h"


#include <iostream> 
using namespace std; 
 
template <class T> 
class MaxHeap 

private: 
    T *heap; 
    int CurSize; 
    int MaxSize; 
public: 
    MaxHeap(int maxsize=10) 
    { 
        MaxSize=maxsize; 
        CurSize=0; 
        heap=new T[MaxSize+1]; 
    } 
 
    ~MaxHeap() 
    { 
        delete[]heap; 
    } 
 
    int Get_Size() const 
    { 
        return CurSize; 
    } 
 
    T Get_Max() 
    { 
        if(CurSize==0) 
        { 
            cout<<"堆为空"<<endl; 
            return -9999; 
        } 
        else 
        { 
            return heap[1]; 
        } 
    } 
 
    MaxHeap<T> &Insert(const T& x) 
    { 
        if(CurSize==MaxSize) 
        { 
            cout<<"堆满,"<<x<<" 插入失败"<<endl; 
            return *this; 
        } 
        //为x寻找应插入位置 
        //i从新的叶子结点开始,沿着树向上 
        int i=++CurSize; 
        while(i!=1 && x>heap[i/2]) 
        { 
            heap[i]=heap[i/2]; //将元素下移 
            i/=2; //移向父节点 
        } 
         
        heap[i]=x; 
        cout<<x<<" 插入成功"<<endl; 
        return *this; 
    } 
 
    MaxHeap<T> &DeleteMax(T& x) 
    { 
        //将最大元素放入x,并从堆中删除它 
        if(CurSize==0) 
        { 
            x=-9999; 
            return *this; 
        } 
         
        x=heap[1]; 
 
        //重构堆 
        heap[0]=heap[CurSize--]; //0号位置存放最后一个元素值,然后将该位置删除 
 
        //从根开始,为heap[0]寻找合适位置 
        int i=1; 
        int ci=2; 
 
        while(ci<=CurSize) 
        { 
            //ci是较大的孩子的位置 
            if(ci<CurSize && heap[ci]<heap[ci+1]) 
                ci++; 
 
            //判断是否可以放入heap[i]位置 
            if(heap[0]>heap[ci]) 
                break; 
  

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,