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

                     

上次用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

---

程序运行结果如下

---

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

           

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