数据布局练手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 }
测试代码
