当前位置:   article > 正文

用C++写二叉堆(优先队列)代码,详细注释_c++ 二叉堆

c++ 二叉堆

 什么是二叉堆

简单来说,二叉堆就是一颗完全二叉树,它具有特殊性质:

  • 小顶堆:父节点的值小于两个孩子节点的值,处于堆顶的就是最小值

  • 大顶堆:父节点的值大于两个孩子节点的值,处于堆顶的就是最大值

如下面两图就举出了小顶堆和大顶堆的例子

插入元素

插入元素会插入到最后一个元素的后面,不断地和父节点作比较,就拿小顶堆举例,如果当前节点的值小于父节点的值,就意味着当前节点要上浮,也就是交换当前节点和父节点的位置,下面就展示了插入1的上浮操作

 

 

 

 

 

 

 

删除堆顶元素

删除堆顶元素后,将最后一个节点放在根节点,再进行下滤操作,即找到合适的位置而满足二叉堆性质:

  • 对于小顶堆,首先比较两个子节点的值,找出值较小的子节点,再进行判断:

    • 如果该较小的子节点比当前节点的值还要大,则找到了合适的位置,或者当前节点的右节点大于堆的大小,下滤结束

    • 否则,将该较小的子节点与当前节点交换,重复之前操作

  • 对于大顶堆,首先比较两个子节点的值,找出值较大的子节点,再进行判断:

    • 如果该较大的子节点比当前节点的值还要小,则找到了合适的位置,或者当前节点的右节点大于堆的大小,下滤结束

    • 否则,将该较大的子节点与当前节点交换,重复之前操作

下面展示了删除堆顶元素2的过程

 

 

 

 

 

 

编写代码

使用的数组来表示二叉堆,第一个元素下标为1,左子树坐标为当前节点下标乘2,父节点下标为当前节点除2

  1. #define ll(x) ((x)<<1) //获得左子树下标
  2. #define p(x) ((x)>>1) //获得父节点下标

二叉堆用cnt表示下一个待插入元素的下标,等于当前元素个数加一,定义了compare函数,a<b表示大顶堆,a>b表示小顶堆

  1. private:
  2. int cnt = 1, val[MAX];
  3. //数组下标从1开始,cnt表示下一个元素将要插入的位置,当前元素个数为cnt-1
  4. bool compare(int a, int b){return a<b;} //<:大顶堆,>:小顶堆

上浮代码如下,首先向val数组插入一个元素,cnt加一,并将新加入的元素不断上浮到合适位置

  1. void push(int n){
  2.    int idx = cnt;
  3.    val[cnt++] = n;
  4.    while(idx > 1){ //从最后一个元素cnt的位置插入,不断上浮到合适位置
  5.        if(compare(val[p(idx)], val[idx])) swap(val[idx], val[p(idx)]);
  6.        idx = p(idx);
  7.   }
  8. }

下滤代码如下,如果当前堆为空,则返回-1,先将堆顶元素和最后一个元素交换位置,然后将第一个元素不断下滤

  1. int pop(){ //弹出堆顶元素
  2.    if(cnt == 1) return -1;
  3.    int idx = 1, top = val[1]; //记录当前堆顶为top
  4.    swap(val[1], val[--cnt]); //将堆顶元素和最后一个元素交换位置,相当于删除了堆顶,cnt-1
  5.    while(idx <= cnt){
  6.        int child = ll(idx);
  7.        //注意是child+1,大顶堆:和孩子节点较大者交换,小顶堆:和孩子节点较小者交换
  8.        if((child+1 < cnt) && (compare(val[child], val[child+1]))) child++;
  9.        //这个条件很重要,不能删除
  10.        if(child < cnt && compare(val[idx], val[child])) swap(val[child], val[idx]);
  11.        idx = child;
  12.   }
  13.    return top;
  14. }

完整代码如下:

  1. #include<iostream>
  2. #include<algorithm>
  3. #define MAX 10000
  4. #define ll(x) ((x)<<1) //获得左子树下标
  5. #define p(x) ((x)>>1) //获得父节点下标
  6. using namespace std;
  7. class Heap{
  8. private:
  9. int cnt = 1, val[MAX]; //数组下标从1开始,cnt表示下一个元素将要插入的位置,当前元素个数为cnt-1
  10. bool compare(int a, int b){return a<b;} //<:大顶堆,>:小顶堆
  11. public:
  12. Heap(){};
  13. Heap(int array[], int n){for(int i=0; i<n; i++) push(array[i]);}
  14. void push(int n){
  15. int idx = cnt;
  16. val[cnt++] = n;
  17. while(idx > 1){ //从最后一个元素cnt的位置插入,不断上浮到合适位置
  18. if(compare(val[p(idx)], val[idx])) swap(val[idx], val[p(idx)]);
  19. idx = p(idx);
  20. }
  21. }
  22. int pop(){ //弹出堆顶元素
  23. if(cnt == 1) return -1;
  24. int idx = 1, top = val[1]; //记录当前堆顶为top
  25. swap(val[1], val[--cnt]); //将堆顶元素和最后一个元素交换位置,相当于删除了堆顶,cnt-1
  26. while(idx <= cnt){
  27. int child = ll(idx);
  28. if((child+1 < cnt) && (compare(val[child], val[child+1]))) child++; //注意是child+1,大顶堆:和孩子节点较大者交换,小顶堆:和孩子节点较小者交换
  29. if(child < cnt && compare(val[idx], val[child])) swap(val[child], val[idx]); //这个条件很重要,不能删除
  30. idx = child;
  31. }
  32. return top;
  33. }
  34. int top() {return val[1];} //返回堆顶元素,但不弹出
  35. int size() {return cnt-1;}
  36. void show() {for(int i=1;i<cnt;i++) cout<<val[i]<<' ';cout<<endl;}
  37. bool empty(){return cnt==1;}
  38. };
  39. int main(){
  40. int n=9, array[MAX]={-1,-4,-2,-3,4,1,5,5,3};
  41. class Heap h(array, n);
  42. h.push(0); //压入元素0
  43. // h.show();
  44. while(!h.empty()) cout<<h.pop()<<' ';
  45. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/正经夜光杯/article/detail/943721?site
推荐阅读
相关标签
  

闽ICP备14008679号