欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C++实现最小堆及插入,调整顺序,删除堆顶元素的操作

程序员文章站 2024-02-13 16:13:10
...
                     

上次用Java实现了最大堆的封装,这次就来写一下最小堆的实现吧


插入函数的思路:
向堆中插入元素有两种情况,一种是堆为空,那么就让插入值作为根节点即可;另一种是堆不为空,那么此时就要进行判断当前节点与其父节点的大小关系比较。此时仍有两种情况,一种是当前节点大于父节点,这样正是我们所希望的;另一种是当前节点的值小于父节点,那么就要将二者的值进行调换,然后记得更新当前节点为原来父节点的位置,而父节点的位置同样需要更新(循环正常终止的时候说明已经到了根节点,此时最小值必定为根节点)

 bool Insert(T data){        if(currentPos==MaxSize){            cout<<"Sorry , this heap is full!"<<endl;            return false;        }        currentPos++;        int targetPos=currentPos-1;        heap[targetPos]=data;        while(targetPos>0){            int parentPos=(targetPos-1)/2;            if(heap[parentPos]<heap[targetPos]){                break;            }else{                heap[targetPos]=heap[parentPos];                targetPos=parentPos;            }        }        return true;    }    //存在的bug是对根节点的大小比较,因为有可能targetPos=0而退出,此时就缺少了一次比较
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

siftDown调整过程思路:
给定要进行调整的节点的下标,我们只需要让它和它的两个子节点中最小的那个比较即可(前提是当前节点不是叶子节点),需要注意的是要先保存当前节点的值,比较之后按大小调整顺序即可。

 void siftDown(int siftPos){        int siftPosition=siftPos;        T temp=heap[siftPosition];        int minChildPos=2*siftPosition+1;        while(minChildPos<currentPos){          //保证比较的条件成立            if((minChildPos<currentPos-1)&&(heap[minChildPos]>heap[minChildPos+1])){                minChildPos++;            }            if(temp<heap[minChildPos]){                break;            }else{                heap[siftPosition]=heap[minChildPos];                siftPosition=minChildPos;                minChildPos=2*siftPosition+1;            }        }        //作用:当要进行调换的位置不满足循环要求时,说明要进行调换的位置是叶子节点,那就不需要变换咯(这里也包括正常比较情况,可正常使用)        heap[siftPosition]=temp; }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

删除对顶元素
需要注意的是currentPos的大小要实时的进行更新,然后返回所删除的堆顶元素即可

 T& deleteTop(){        if(currentPos<0){            cout<<"Sorry ,this heap is empty!"<<endl;        }        T target=heap[0];        heap[0]=heap[currentPos-1];        currentPos--;        siftDown(0);        return target;    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

下面是完整的C++关于最小堆的实现的代码

#include <iostream>using namespace std;template<class T>class MinHeap{    T *heap;    int MaxSize;    int currentPos;public:    MinHeap(int MS){        heap=new T[MS];        currentPos=0;        MaxSize=MS;    }    bool Insert(T data){        if(currentPos==MaxSize){            cout<<"Sorry , this heap is full!"<<endl;            return false;        }        currentPos++;        int targetPos=currentPos-1;        heap[targetPos]=data;        while(targetPos>0){            int parentPos=(targetPos-1)/2;            if(heap[parentPos]<heap[targetPos]){                break;            }else{                heap[targetPos]=heap[parentPos];                targetPos=parentPos;            }        }        return true;    }    void siftDown(int siftPos){        int siftPosition=siftPos;        T temp=heap[siftPosition];        int minChildPos=2*siftPosition+1;        while(minChildPos<currentPos){          //保证比较的条件成立            if((minChildPos<currentPos-1)&&(heap[minChildPos]>heap[minChildPos+1])){                minChildPos++;            }            if(temp<heap[minChildPos]){                break;            }else{                heap[siftPosition]=heap[minChildPos];                siftPosition=minChildPos;                minChildPos=2*siftPosition+1;            }        }        //作用:当要进行调换的位置不满足循环要求时,说明要进行调换的位置是叶子节点,那就不需要变换咯        heap[siftPosition]=temp;        ////////////////////////////////////////////    }    T& deleteTop(){        if(currentPos<0){            cout<<"Sorry ,this heap is empty!"<<endl;        }        T target=heap[0];        heap[0]=heap[currentPos-1];        currentPos--;        siftDown(0);        return target;    }};int main(){    cout << "Hello world!" << endl;    MinHeap<int> minHeap(7);    minHeap.Insert(1);    minHeap.Insert(2);    minHeap.Insert(4);    minHeap.Insert(3);    minHeap.Insert(6);    minHeap.Insert(7);    minHeap.Insert(5);    for(int i=1;i<=7;i++){        cout<<minHeap.deleteTop()<<endl;    }    return 0;}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90

程序运行结果如下
C++实现最小堆及插入,调整顺序,删除堆顶元素的操作


总结:
代码中存在一定得错误,出在 Insert函数中。个人认为需要对targetPos为0的特殊情况再加一层判断,估计就能解决。但是对正常添加元素还是能得到比较正常的结果的。

           

再分享一下我老师大神的人工智能教程吧。零基础!通俗易懂!风趣幽默!还带黄段子!希望你也加入到我们人工智能的队伍中来!https://blog.csdn.net/jiangjunshow