用数组实现的最大堆(C++)

1 #include <iostream>
 2 #include <assert.h>
 3 
 4 using namespace std;
 5 void swap(int* a,int pos,int j){
 6     int temp=a[pos];
 7     a[pos]=a[j];
 8     a[j]=temp;
 9 }
10 class heap{
11 private:
12     int* Heap;
13     int maxsize;  //堆的大小
14     int n;        //当前堆中的元素个数
15 
16     //把一个元素移动到合适的位置
17     void shiftdown(int pos){
18       while(!isLeaf(pos)){     //如果是叶子结点就停止
19         int j=leftchild(pos);
20         int rc=rightchild(pos);
21         if((rc<n)&&Heap[rc]>Heap[j])
22             j=rc;               //把j设置为最大孩子的下标
23         if(Heap[pos]>Heap[j])
24             return;           //当前结点数值比两个孩子最大值还大就结束了
25         swap(Heap,pos,j);
26         pos=j;
27       }
28     }
29 
30 public:
31     heap(int* h,int num,int maxi){  //构造函数
32         Heap=h;
33         n=num;
34         maxsize=maxi;
35         buildHeap();
36     }
37     int size()const{         //返回当前个数
38         return n;
39     }
40     bool isLeaf(int pos) const{  //判断是否是叶子
41         return (pos>=n/2)&&(pos<n);
42     }
43     int leftchild(int pos) const{  //返回结点左孩子
44         return 2*pos+1;
45     }
46     int rightchild(int pos) const{  //返回结点右孩子
47         return 2*pos+2;
48     }
49     int parent(int pos) const{       //返回父亲结点
50         return (pos-1)/2;
51     }
52     void buildHeap(){            //把堆进行堆化
53         for(int i=n/2-1;i>=0;i--)
54             shiftdown(i);
55     }
56     //把一个元素插入堆
57     void insert(const int& it){
58         assert(n<maxsize);
59         int curr=n++;
60         Heap[curr]=it;  //把元素插入到堆的最后
61         //把这个元素向上移动
62         while((curr!=0)&&(Heap[curr]>Heap[parent(curr)])){
63             swap(Heap,curr,parent(curr));
64             curr=parent(curr);
65         }
66     }
67     int remove(int pos){     //移除一个结点
68         assert((pos>=0)&&(pos<n));
69         if(pos==(n-1))  //如果是最后一个元素
70             n--;
71         else{
72             swap(Heap,pos,--n);
73             while((pos!=0)&&(Heap[pos]>Heap[parent(pos)])){
74                 swap(Heap,pos,parent(pos));
75                 pos=parent(pos);
76             }
77             if(n!=0)
78                 shiftdown(pos);
79         }
80         return Heap[n];
81     }
82 };

原文链接: https://www.cnblogs.com/duanqiong/p/4989691.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍