最小(大)堆是比较常用的数据结构,是实现优先队列和堆排序的基础,也可以实现例如霍夫曼编码,贪心算法等,具有很好的时间复杂性.
template<class T>
class MaxHeap{
public:
MaxHeap(T a[],int n);
MaxHeap(int ms);
~MaxHeap();
bool Insert(const T &x);//插入一个元素,如果空返回false,否则返回true
bool RemoveMax(T &x);//删除最小的元素,如果空返回false,否则返回true
void MakeEmpty();//使堆为空
bool IsEmpty();
bool IsFull();
protected:
void FilterDown(const int start,const int endOfHeap);//自顶向下构造堆
void FilterUp(const int start);//自底向上构造堆
private:
T *heap;
int maxSize;
const int defaultSize;
int currentSize;
};
template<class T>
MaxHeap<T>::MaxHeap(int ms):defaultSize(100){
maxSize = ms > defaultSize ? ms : defaultSize;
heap = new T[maxSize];
currentSize = 0;
}
template<class T>
MaxHeap<T>::MaxHeap(T a[],int n):defaultSize(100){
maxSize = n > defaultSize ? n : defaultSize;
heap = new T[maxSize];
currentSize = n;
for(int i = 0; i < n; i++)
heap[i] = a[i];
int curPos = (currentSize - 2) / 2;
while(curPos >= 0){
FilterDown(curPos,currentSize - 1);
curPos--;
}
}
template<class T>
MaxHeap<T>::~MaxHeap(){
delete []heap;
}
template<class T>
void MaxHeap<T>::FilterDown(const int start,const int endOfHeap){
int i = start,j = i * 2 + 1;
T temp = heap[i];
while(j <= endOfHeap){
if(j < endOfHeap && heap[j] < heap[j+1]) j++;
if(temp > heap[j]) break;
else{
heap[i] = heap[j];
i = j;
j = 2 * i + 1;
}
}
heap[i] = temp;
}
template<class T>
void MaxHeap<T>::FilterUp(const int start){
int i = start, j = ( i - 1 ) / 2;
T temp = heap[i];
while(i > 0){
if(temp <= heap[j]) break;
else{
heap[i] = heap[j];
i = j;
j = (i - 1) / 2;
}
}
heap[i] = temp;
}
template<class T>
bool MaxHeap<T>::RemoveMax(T &x){
if(IsEmpty()){
cerr<<"Heap empty!"<<endl;
return false;
}
x = heap[0];
heap[0] = heap[currentSize - 1];
currentSize--;
FilterDown(0,currentSize-1);
return true;
}
template<class T>
bool MaxHeap<T>::Insert(const T& x){
if(IsFull()) {
cerr<<"Heap Full!"<<endl;
return false;
}
heap[currentSize] = x;
FilterUp(currentSize);
currentSize++;
return true;
}
template<class T>
bool MaxHeap<T>::IsEmpty(){
return currentSize == 0;
}
template<class T>
bool MaxHeap<T>::IsFull(){
return currentSize == maxSize;
}
template<class T>
void MaxHeap<T>::MakeEmpty(){
currentSize = 0
}
MainApp.cpp测试文件:
#include<iostream>
#include"MaxHeap.h"
using namespace std;
void main(){
int a[5] = {3,2,1,4,5};
MaxHeap<int> m_heap(a,5);
int x,i;
for(i = 0; i < 5; i++){
m_heap.RemoveMax(x);
cout << x << " ";
}
cout << endl;
for(i = 0; i < 5; i++){
m_heap.Insert(a[i]);
}
for(i = 0; i < 5; i++){
m_heap.RemoveMax(x);
cout << x << " ";
}
cout << endl;
}
分享到:
相关推荐
实际上我比较喜欢java(少接触Ruby 罢了)但是jquery的简单的实用的确有相当大的吸引力啊!在项目里我把jquery作为自己唯一的框架类包。使用其间也有一点点心得,其实这些心得,在jquery的文档上面也可能有讲,不过...
-为TreeNode增加AutoPostBack属性,增加事件数据类TreeCheckEventArgs,为Tree增加事件NodeCheck。 -示例在:http://extasp.net/data/tree_run.aspx -Grid增加GetNoSelectionAlertInParentReference函数,用来...
2012-06-12 11:51 103,936 最大堆实现排序(从大到小输出).doc 2012-06-12 11:51 240,128 最小生成树(prim算法)贪心算法.doc 2012-06-12 12:26 772,419 最简单的c++静态链接.zip 2012-06-12 11:45 202,240 最长...
实际上我比较喜欢java(少接触Ruby 罢了)但是jquery的简单的实用的确有相当大的吸引力啊!在项目里我把jquery作为自己唯一的框架类包。使用其间也有一点点心得,其实这些心得,在jquery的文档上面也可能有讲,不过...
/usr/lib之类的目录下,c源程序里直接写#include 时,能直接去找到它们,在VC里,同样的,最简单的方法就是将oSIP2源码包中的Include目录下的 osipparser2目录直接拷到我们的Windows下默认...
实际上我比较喜欢java(少接触Ruby 罢了)但是jquery的简单的实用的确有相当大的吸引力啊!在项目里我把jquery作为自己唯一的框架类包。使用其间也有一点点心得,其实这些心得,在jquery的文档上面也可能有讲,不过...
-为TreeNode增加AutoPostBack属性,增加事件数据类TreeCheckEventArgs,为Tree增加事件NodeCheck。 -示例在:http://extasp.net/data/tree_run.aspx -Grid增加GetNoSelectionAlertInParentReference函数,用来...
声明方法的存在而不去实现它的类被叫做抽象类(abstract class),它用于要创建一个体现某些基本行为的类,并为该类声明方法,但不能在该类中实现该类的情况。不能创建abstract 类的实例。然而可以创建一个变量,其...
根据 TIOBE 编程社区索引,Java 编程语言是软件开发人员的最佳选择之一,他们力争在基于 C 和 C-based 语言中占据上风。从 PC,移动终端或媒体播放器到更复杂的医疗设备,全球大多数电子设备都使用其功能。 Java SE...
实际上我比较喜欢java(少接触Ruby 罢了)但是jquery的简单的实用的确有相当大的吸引力啊!在项目里我把jquery作为自己唯一的框架类包。使用其间也有一点点心得,其实这些心得,在jquery的文档上面也可能有讲,不过...
声明方法的存在而不去实现它的类被叫做抽象类(abstract class),它用于要创建一个体现某些基本行为的类,并为该类声明方法,但不能在该类中实现该类的情况。不能创建abstract 类的实例。然而可以创建一个变量,...
1:外文原文 Struts——an open-source MVC implementation This article introduces Struts, a Model-View-Controller implementation that uses servlets and JavaServer Pages (JSP) technology....
根据 TIOBE 编程社区索引,Java 编程语言是软件开发人员的最佳选择之一,他们力争在基于 C 和 C-based 语言中占据上风。从 PC,移动终端或媒体播放器到更复杂的医疗设备,全球大多数电子设备都使用其功能。 Java SE...
了解如何使用机器学习算法来解决回归和分类问题实现集成技术,例如平均,加权平均和最大投票掌握高级合奏方法,例如自举,装袋和堆叠使用随机森林执行诸如分类和回归之类的任务实现同类和异构机器学习算法的集成...
2.3 设计实现的主要功能 本软件在设计方面本着方便、实用及娱乐性高的宗旨,在对界面进行设计的过程中, 始终坚持清晰明了,在性能方面能够实现效率高,不易出错等优点。 (1)游戏主界面模块: 主要包括游戏图形...
要实现单片机与电脑的连接,最简单的方式就是采用串口通讯,但需要加一颗RS-232芯片。 17. 在ARM编程中又应当如何? 答:就以嵌入式系统观念为例,一般嵌入式处理器可以分为三类:嵌入式微处理器、嵌入式微...
本节将向您展示 malloc 和 free 的一个最简化实现的代码,来帮助说明管理内存时都涉及到了哪些事情。 要试着运行这些示例,需要先 复制本代码清单,并将其粘贴到一个名为 malloc.c 的文件中。接下来,我将一次一个...
许多财务软件,在启用之前,有一大堆初始化设置,而且术语很专业,如果其中有一点设置不成功,就无法进入软件操作。智点财务软件系统在设计之初,就彻底杜绝了这种不人性化的操作,从一个不懂电脑操作的财务人员的...