数据布局练手05 关于堆的up策略和down策略实现
添加时间:2013-5-28 点击量:
堆,是一个相当首要的数据布局,它是优先队列,堆排序,Dijkstra等算法的实现包管!
堆的首要特点是:
1、根结点是最大/小,而这个首要的差别,就是实现斗劲操纵时是less or greater, 是以可以应用纯虚化 斗劲接口,把实现放到子类。 附: STL中采取的是模板默认参数的办法实现。
2、须要两个默示大小的变量来标定堆or数组的大小。因为pop操纵因让堆的有效长度变小,而数组的长度不变。
3、堆的插入操纵一般是插入到数组的末尾,这里好用vector, 因为它可以在常数时候内尾插入数据且可以或许动态发展。
1 #include <vector>
2 #include <ostream>
3 using namespace std;
4 template<class T>
5 class HEAP{
6 protected:
7 vector<T> elements;
8 int totalSize;
9 public:
10 HEAP() : totalSize(0),elements(){}
11 virtual ~HEAP(){}
12 int left(int index){return 2index+1;}
13 int right(int index){return 2index+2;}
14 int parent(int index){return (index-1)/2;}
15
16 void upHeapity(int index);
17 void downheapity(int index);
18
19 void makeHeap_up();
20 void makeHeap_down();
21
22 T& pop_up();
23 T& pop_down();
24
25 void _up(const T& x);
26 void _down(const T& x);
27 void swap(T& a, T& b){int tmp=a; a=b; b=tmp;}
28 void show(ostream& os) const;
29 void sort();
30
31 virtual bool comp(int a, int b)=0;
32 };
类定义
1 template<class T>
2 class maxHeap : public HEAP<T>{
3 public:
4 maxHeap() : HEAP<T>(){}
5 ~maxHeap(){};
6 bool comp(int a, int b) { return elements[a]>elements[b]? true:false;}
7 };
8
9 template<class T>
10 class minHeap : public HEAP<T>{
11 public:
12 minHeap() : HEAP<T>(){}
13 ~minHeap(){};
14 bool comp(int a, int b) { return elements[a]<elements[b]? true: false;}
15 };
子类定义
要包管这个heapity特点,(假定是评论辩论最大堆)一般有两种体式格式:从根到叶(down) 和 从叶到根(up),这两种实现各有优毛病。我们先说下各类操纵的文字表述:
<<算法导论>>中采取了down的策略,即斗劲本结点,阁下结点,获得最大值的下标索引,若不是最大索引不是本结点,则互换本结点和最大索引,接着用最大索引实现递归操纵。downHeapity包管了该子树满足堆的特点。
1 template<class T>
2 void HEAP<T>::downheapity(int index)
3 {
4 int l = left (index);
5 int r = right(index);
6 int large = index;
7 if(l<totalSize)
8 if(comp(l,index))
9 large = l;
10 else
11 large = index;
12 if(r<totalSize)
13 if(comp(r,large))
14 large = r;
15 if(index != large){
16 swap(elements[index], elements[large]);
17 downheapity(large);
18 }
19 }
downheapity策略
StL中采取了是up的策略,即新增长结点时,仅需层层斗劲和父节点的大小,最多到根节点。up策略满足了从该叶到根的路径满足了堆的特点。
1 template<typename T>
2 void HEAP<T>::upHeapity(int index)
3 {
4 while((index!=0) && (comp(index, parent(index)))){
5 swap(elements[index], elements[parent(index)]);
6 index = parent(index);
7 }
8 }
upheapity策略
别的,在建堆操纵中,若采取down策略,则可以从index= lenArray/2 的地位进行downHeapity(index)一向递减到根结点就行。
1 template<class T>
2 void HEAP<T>::makeHeap_down()
3 {
4 totalSize = elements.size(); // 很首要,从头调剂堆大小
5 for(int i=totalSize>>1; i>=0; --i){ // 从一半到零
6 downheapity(i);
7 }
8 }
建堆的down策略
而采取up策略,则从index = lenArray-1的地位递减到 lenArray/2的地位,中心一向调用upHeapity(index)就行。
1 template<class T>
2 void HEAP<T>::makeHeap_up()
3 {
4 totalSize = elements.size();
5 for (int i=elements.size()-1; i>elements.size()/2; --i) {
6 upHeapity(i);
7 }
8 }
建堆的up策略
我们对堆进行pop操纵时,一般来说要保存根结点的值用于最后的返回。实现中我们还须要将根结点和尾结点的值进行互换。这里持续说下down策略和up策略的做法。
down策略时,因为前一步已经互换了根结点和尾结点,且调剂了堆大小的长度,如许,我们就可以从索引为堆大小一半的地位开端,递减到根,一向调用 downheapity(index)就行。
1 template<class T>
2 T& HEAP<T>::pop_down()
3 {
4 T rval = elements[0];
5 swap(elements[0],elements[totalSize-1]);
6 totalSize--;
7 for(int i=totalSize/2; i>=0; i--){
8 downheapity(i);
9 }
10 return rval;
11 }
pop操纵的down策略
up策略是,就斗劲麻烦点了,须要将互换后的根结点下放到某个小值的地位,然后再调用次upheapity包管堆特点的满足。这个实现起来斗劲憎恶,要断定一些鸿沟前提。
1 template<class T>
2 T& HEAP<T>::pop_up()
3 {
4 T rval = elements[0];
5 swap(elements[0],elements[totalSize-1]);
6 totalSize--;
7 int i=0;
8 int tmp=i;
9 while(left(i)<totalSize){
10 if( (right(i)<totalSize) && comp(left(i),right(i)) || (right(i)>=totalSize)){
11 tmp = left(i);
12 }
13 if( (right(i)<totalSize) && (!comp(left(i),right(i)))){
14 tmp = right(i);
15 }
16 swap(elements[i],elements[tmp]);
17 i = tmp;
18 }
19 upHeapity(tmp);
20 return rval;
21 }
pop操纵的up策略
而对于堆排序,则就是遍历调用pop n-1次就行。
1 template<class T>
2 void HEAP<T>::sort()
3 {
4 int t = totalSize;
5 for(int i=0; i<t; ++i){
6 pop_up();
7 // pop_down();
8 }
9 }
堆排序
对于元素的插入来说,那必然是StL的up占优了。因为up策略就是从尾结点开端向父节点进行斗劲,最多斗劲到根节点。 而若采取down策略,则从堆大小一半的地位递减到根,此中一向调用downheapity(index)操纵。
1 template<typename T>
2 void HEAP<T>::_up(const T& x)
3 {
4 if(totalSize == elements.size())
5 elements.push_back(x);
6 else
7 elements[totalSize] = x;
8 totalSize++;
9 upHeapity(totalSize-1);
10 }
11
12 template<typename T>
13 void HEAP<T>::_down(const T& x)
14 {
15 if(totalSize == elements.size())
16 elements.push_back(x);
17 else
18 elements[totalSize] = x;
19 totalSize++;
20 for(int i=totalSize/2; i>=0; i--){
21 downheapity (i);
22 }
23 }
的down策略和up策略
是以,这里我们可以总结下应用堆时辰的策略:
除了插入操纵应用up策略外,其他所有的操纵都应用down策略。调用down策略,都从一半堆大小的地位开端递减到根。
别的,对于鸿沟前提来说,down策略一般从尾结点的父节点开端,及 parent(totalSize-1), 即 (totalSize-1)/2; 因为下标从0开端,鸿沟前提就很让人纠结,我们宁肯多操纵一次,及从total/2地位开端,如许也没啥影响。
- 之前我的总结有题目,今天反思了下,若都从一半堆大小开端递减到根,那么时候错杂度挺大的。其实所有的操纵都采取down策略更易懂得。
- 对于从(size-1)/2还是size/2开端,我感觉还是从(size-1)/2更好,如许轮回代码可以批改下,且也能避免上方所误会的处所
1 _down 和 pop_down 中的
/for(int i=totalSize/2; i>=0; i--){
2 downheapity(i);
3 }/
4 改为:
5 int p = parent (totalSize-1);
6 while( p != parent(p)){
7 downheapity (p);
8 p = parent(p);
9 }
10 downheapity(p);
应用堆的时辰,必然要重视是采取数组长度还是堆长度。我们可以总结下:仅建堆时采取数组长度,同时堆长度便是数组长度; 其余操纵应用的都是堆长度,同时要重视调剂堆长度水位
测试代码:
1 #include myHeap.h
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 maxHeap<int> mh;
8 mh._down(170);
9 mh._down(20);
10 mh._down(30);
11 mh._down(1);
12 mh._down(7);
13
14 mh._down(10);
15 mh._down(90);
16
17 cout << mh << endl;
18 cout << -------- << endl;
19 mh.sort();
20 cout << mh << endl;
21 mh.makeHeap_up();
22 cout << mh << endl;
23 }
测试代码
真正的心灵世界会告诉你根本看不见的东西,这东西需要你付出思想和灵魂的劳动去获取,然后它会照亮你的生命,永远照亮你的生命。——王安忆《小说家的十三堂课》
堆,是一个相当首要的数据布局,它是优先队列,堆排序,Dijkstra等算法的实现包管!
堆的首要特点是:
1、根结点是最大/小,而这个首要的差别,就是实现斗劲操纵时是less or greater, 是以可以应用纯虚化 斗劲接口,把实现放到子类。 附: STL中采取的是模板默认参数的办法实现。
2、须要两个默示大小的变量来标定堆or数组的大小。因为pop操纵因让堆的有效长度变小,而数组的长度不变。
3、堆的插入操纵一般是插入到数组的末尾,这里好用vector, 因为它可以在常数时候内尾插入数据且可以或许动态发展。
1 #include <vector>
2 #include <ostream>
3 using namespace std;
4 template<class T>
5 class HEAP{
6 protected:
7 vector<T> elements;
8 int totalSize;
9 public:
10 HEAP() : totalSize(0),elements(){}
11 virtual ~HEAP(){}
12 int left(int index){return 2index+1;}
13 int right(int index){return 2index+2;}
14 int parent(int index){return (index-1)/2;}
15
16 void upHeapity(int index);
17 void downheapity(int index);
18
19 void makeHeap_up();
20 void makeHeap_down();
21
22 T& pop_up();
23 T& pop_down();
24
25 void _up(const T& x);
26 void _down(const T& x);
27 void swap(T& a, T& b){int tmp=a; a=b; b=tmp;}
28 void show(ostream& os) const;
29 void sort();
30
31 virtual bool comp(int a, int b)=0;
32 };
类定义
1 template<class T>
2 class maxHeap : public HEAP<T>{
3 public:
4 maxHeap() : HEAP<T>(){}
5 ~maxHeap(){};
6 bool comp(int a, int b) { return elements[a]>elements[b]? true:false;}
7 };
8
9 template<class T>
10 class minHeap : public HEAP<T>{
11 public:
12 minHeap() : HEAP<T>(){}
13 ~minHeap(){};
14 bool comp(int a, int b) { return elements[a]<elements[b]? true: false;}
15 };
子类定义
要包管这个heapity特点,(假定是评论辩论最大堆)一般有两种体式格式:从根到叶(down) 和 从叶到根(up),这两种实现各有优毛病。我们先说下各类操纵的文字表述:
<<算法导论>>中采取了down的策略,即斗劲本结点,阁下结点,获得最大值的下标索引,若不是最大索引不是本结点,则互换本结点和最大索引,接着用最大索引实现递归操纵。downHeapity包管了该子树满足堆的特点。
1 template<class T>
2 void HEAP<T>::downheapity(int index)
3 {
4 int l = left (index);
5 int r = right(index);
6 int large = index;
7 if(l<totalSize)
8 if(comp(l,index))
9 large = l;
10 else
11 large = index;
12 if(r<totalSize)
13 if(comp(r,large))
14 large = r;
15 if(index != large){
16 swap(elements[index], elements[large]);
17 downheapity(large);
18 }
19 }
downheapity策略
StL中采取了是up的策略,即新增长结点时,仅需层层斗劲和父节点的大小,最多到根节点。up策略满足了从该叶到根的路径满足了堆的特点。
1 template<typename T>
2 void HEAP<T>::upHeapity(int index)
3 {
4 while((index!=0) && (comp(index, parent(index)))){
5 swap(elements[index], elements[parent(index)]);
6 index = parent(index);
7 }
8 }
upheapity策略
别的,在建堆操纵中,若采取down策略,则可以从index= lenArray/2 的地位进行downHeapity(index)一向递减到根结点就行。
1 template<class T>
2 void HEAP<T>::makeHeap_down()
3 {
4 totalSize = elements.size(); // 很首要,从头调剂堆大小
5 for(int i=totalSize>>1; i>=0; --i){ // 从一半到零
6 downheapity(i);
7 }
8 }
建堆的down策略
而采取up策略,则从index = lenArray-1的地位递减到 lenArray/2的地位,中心一向调用upHeapity(index)就行。
1 template<class T>
2 void HEAP<T>::makeHeap_up()
3 {
4 totalSize = elements.size();
5 for (int i=elements.size()-1; i>elements.size()/2; --i) {
6 upHeapity(i);
7 }
8 }
建堆的up策略
我们对堆进行pop操纵时,一般来说要保存根结点的值用于最后的返回。实现中我们还须要将根结点和尾结点的值进行互换。这里持续说下down策略和up策略的做法。
down策略时,因为前一步已经互换了根结点和尾结点,且调剂了堆大小的长度,如许,我们就可以从索引为堆大小一半的地位开端,递减到根,一向调用 downheapity(index)就行。
1 template<class T>
2 T& HEAP<T>::pop_down()
3 {
4 T rval = elements[0];
5 swap(elements[0],elements[totalSize-1]);
6 totalSize--;
7 for(int i=totalSize/2; i>=0; i--){
8 downheapity(i);
9 }
10 return rval;
11 }
pop操纵的down策略
up策略是,就斗劲麻烦点了,须要将互换后的根结点下放到某个小值的地位,然后再调用次upheapity包管堆特点的满足。这个实现起来斗劲憎恶,要断定一些鸿沟前提。
1 template<class T>
2 T& HEAP<T>::pop_up()
3 {
4 T rval = elements[0];
5 swap(elements[0],elements[totalSize-1]);
6 totalSize--;
7 int i=0;
8 int tmp=i;
9 while(left(i)<totalSize){
10 if( (right(i)<totalSize) && comp(left(i),right(i)) || (right(i)>=totalSize)){
11 tmp = left(i);
12 }
13 if( (right(i)<totalSize) && (!comp(left(i),right(i)))){
14 tmp = right(i);
15 }
16 swap(elements[i],elements[tmp]);
17 i = tmp;
18 }
19 upHeapity(tmp);
20 return rval;
21 }
pop操纵的up策略
而对于堆排序,则就是遍历调用pop n-1次就行。
1 template<class T>
2 void HEAP<T>::sort()
3 {
4 int t = totalSize;
5 for(int i=0; i<t; ++i){
6 pop_up();
7 // pop_down();
8 }
9 }
堆排序
对于元素的插入来说,那必然是StL的up占优了。因为up策略就是从尾结点开端向父节点进行斗劲,最多斗劲到根节点。 而若采取down策略,则从堆大小一半的地位递减到根,此中一向调用downheapity(index)操纵。
1 template<typename T>
2 void HEAP<T>::_up(const T& x)
3 {
4 if(totalSize == elements.size())
5 elements.push_back(x);
6 else
7 elements[totalSize] = x;
8 totalSize++;
9 upHeapity(totalSize-1);
10 }
11
12 template<typename T>
13 void HEAP<T>::_down(const T& x)
14 {
15 if(totalSize == elements.size())
16 elements.push_back(x);
17 else
18 elements[totalSize] = x;
19 totalSize++;
20 for(int i=totalSize/2; i>=0; i--){
21 downheapity (i);
22 }
23 }
的down策略和up策略
是以,这里我们可以总结下应用堆时辰的策略:
除了插入操纵应用up策略外,其他所有的操纵都应用down策略。调用down策略,都从一半堆大小的地位开端递减到根。
别的,对于鸿沟前提来说,down策略一般从尾结点的父节点开端,及 parent(totalSize-1), 即 (totalSize-1)/2; 因为下标从0开端,鸿沟前提就很让人纠结,我们宁肯多操纵一次,及从total/2地位开端,如许也没啥影响。
- 之前我的总结有题目,今天反思了下,若都从一半堆大小开端递减到根,那么时候错杂度挺大的。其实所有的操纵都采取down策略更易懂得。
- 对于从(size-1)/2还是size/2开端,我感觉还是从(size-1)/2更好,如许轮回代码可以批改下,且也能避免上方所误会的处所
1 _down 和 pop_down 中的
/for(int i=totalSize/2; i>=0; i--){
2 downheapity(i);
3 }/
4 改为:
5 int p = parent (totalSize-1);
6 while( p != parent(p)){
7 downheapity (p);
8 p = parent(p);
9 }
10 downheapity(p);
应用堆的时辰,必然要重视是采取数组长度还是堆长度。我们可以总结下:仅建堆时采取数组长度,同时堆长度便是数组长度; 其余操纵应用的都是堆长度,同时要重视调剂堆长度水位
测试代码:
1 #include myHeap.h
2 #include <iostream>
3 using namespace std;
4
5 int main()
6 {
7 maxHeap<int> mh;
8 mh._down(170);
9 mh._down(20);
10 mh._down(30);
11 mh._down(1);
12 mh._down(7);
13
14 mh._down(10);
15 mh._down(90);
16
17 cout << mh << endl;
18 cout << -------- << endl;
19 mh.sort();
20 cout << mh << endl;
21 mh.makeHeap_up();
22 cout << mh << endl;
23 }
测试代码
真正的心灵世界会告诉你根本看不见的东西,这东西需要你付出思想和灵魂的劳动去获取,然后它会照亮你的生命,永远照亮你的生命。——王安忆《小说家的十三堂课》