注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

G G I C C I

 
 
 

日志

 
 

最大堆、最小堆模板 (C++ STL实现)  

2012-08-11 21:58:03|  分类: 数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Title :

  • 用C++的STL实现最大堆和最小堆数据结构

Q :

用C++如何快速实现堆数据结构,比如说最大堆和最小堆?

A :

使用STL库 <algorithm> 里面的堆函数 make_heap 可以把 vector 容器转换为堆结构存储。


Code :
   1: /*
   2:     MyHeap.h
   3:     Author : Ggicci
   4:     Time:    2012.07.07
   5: */
   6: #pragma once
   7:  
   8: #include <vector>
   9: #include <algorithm>
  10: using namespace std;
  11:  
  12: template <class T>
  13: class MyHeap
  14: {
  15: private:
  16:     //声明了一个函数指针用于指向比较堆里面元素大小的函数
  17:     typedef    bool (*COMP_FUNC)(const T&, const T&);
  18:     COMP_FUNC _comp;
  19:     vector<T> _data;
  20:  
  21: public:
  22:     MyHeap(COMP_FUNC compare_function = NULL)
  23:         :_comp(compare_function)
  24:     //如果不指定这个函数指针变量的值,那么会自动调用类实现的 operator < 函数
  25:     {
  26:         if(NULL == _comp)
  27:             make_heap(_data.begin(), _data.end());
  28:         else
  29:             make_heap(_data.begin(), _data.end(), _comp);
  30:     }
  31:  
  32:     void add(const T& item)
  33:     {
  34:         //往堆里面添加元素,顺序为先添加(push_back)再重整堆结构(push_heap)
  35:         _data.push_back(item);
  36:         if(NULL == _comp)
  37:             push_heap(_data.begin(), _data.end());
  38:         else
  39:             push_heap(_data.begin(), _data.end(), _comp);
  40:     }
  41:  
  42:     T remove()
  43:     {
  44:         //往堆里面移除元素,顺序为先重整堆结构(pop_heap)再移除元素(pop_back)
  45:         if(NULL == _comp)
  46:             pop_heap(_data.begin(), _data.end());
  47:         else
  48:             pop_heap(_data.begin(), _data.end(), _comp);
  49:         T removed = _data.back();
  50:         _data.pop_back();
  51:         return removed;
  52:     }
  53:  
  54:     bool isEmpty() const
  55:     {
  56:         return _data.empty();
  57:     }
  58:  
  59:     void clear()
  60:     {
  61:         _data.clear();
  62:     }
  63: };

Test :

   1: #include <iostream>
   2: #include "MyHeap.h"
   3: #include "animal.h"
   4: using namespace std;
   5:  
   6: int main()
   7: {
   8:     MyHeap<int> iMaxHeap;
   9:     iMaxHeap.add(34);
  10:     iMaxHeap.add(3);
  11:     iMaxHeap.add(13);
  12:     iMaxHeap.add(9);
  13:     iMaxHeap.add(27);    
  14:     while(!iMaxHeap.isEmpty())
  15:     {
  16:         cout << "removed >> " << iMaxHeap.remove() << endl;
  17:     }
  18:  
  19:     cout << endl << endl;
  20:     
  21:     //使用其它的函数而非 operator < 
  22:     MyHeap<Animal> animalMinHeap(Animal::compare_larger);
  23:     Animal animals[] = {
  24:         Animal("A", 2),
  25:         Animal("B", 8),
  26:         Animal("C", 3),
  27:         Animal("D", 9),
  28:         Animal("E", 1)
  29:     };
  30:     for (int i = 0; i < 5; i++)
  31:     {
  32:         animalMinHeap.add(animals[i]);
  33:     }
  34:     while(!animalMinHeap.isEmpty())
  35:     {
  36:         cout << "removed >> " << animalMinHeap.remove() << endl;
  37:     }
  38:  
  39:     return 0;
  40: }
  41:  
  42:  
  43: class Animal
  44: {
  45: public:
  46:     static bool compare_larger(const Animal& lhs, const Animal& rhs)
  47:     {
  48:         return lhs.age > rhs.age ? true : false;
  49:     }
  50:     //...
  51: }
结果:
removed >> 34
removed >> 27
removed >> 13
removed >> 9
removed >> 3
removed >> [E, 1]
removed >> [A, 2]
removed >> [C, 3]
removed >> [B, 8]
removed >> [D, 9]

这个类是一个不完善的类,比如说你这样调用 MyHeap<Animal*>就不行了,因为后面的比较用的函数格式与里面声明的函数指针的格式不匹配,所以以后要用到这个最小堆最大堆的数据结构的时候一般根据需要重新封装一个类,可能你只需要最小堆,而且考虑到内存开销使vector容器里面装指针而不是拷贝,那么你在传递函数指针的时候可以传递一个参数列表也是指针格式的函数的地址,那么这个类虽然使用单一,但是实用就好,没必要花了好多心思写一个万全的这样的类,到最后用的时候反倒看着嫌麻烦。


End :

Author : Ggicci

谢谢阅读,有误希望指正!

  评论这张
 
阅读(2584)| 评论(0)
推荐

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017