最小(大)堆是比较常用的数据结构,是实现优先队列和堆排序的基础,也可以实现例如霍夫曼编码,贪心算法等,具有很好的时间复杂性.
MinHeap.h文件
template<class T>
class MinHeap{
public:
MinHeap(T a[],int n);
MinHeap(int ms);
~MinHeap();
bool Insert(const T &x);//插入一个元素,如果空返回false,否则返回true
bool RemoveMin(T &x);//删除最小的元素,如果空返回false,否则返回true
void MakeEmpty();//使堆为空
bool IsEmpty();
bool IsFull();
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>
MinHeap<T>::MinHeap(int ms):defaultSize(100){
maxSize = ms > defaultSize ? ms : defaultSize;
heap = new T[maxSize];
currentSize = 0;
}
template<class T>
MinHeap<T>::MinHeap(T a[],int n):defaultSize(100){
maxSize = n > defaultSize ? n : defaultSize;
heap = new T[maxSize];
currentSize = n;
heap = a;
int curPos = (currentSize - 2) / 2;
while(curPos >= 0){
FilterDown(curPos,currentSize - 1);
curPos--;
}
}
template<class T>
MinHeap<T>::~MinHeap(){
delete []heap;
}
template<class T>
void MinHeap<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 MinHeap<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 MinHeap<T>::RemoveMin(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 MinHeap<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 MinHeap<T>::IsEmpty(){
return currentSize == 0;
}
template<class T>
bool MinHeap<T>::IsFull(){
return currentSize == maxSize;
}
template<class T>
void MinHeap<T>::MakeEmpty(){
currentSize = 0
}
main.cpp测试文件:
#include<iostream>
#include"MinHeap.h"
using namespace std;
void main(){
int a[5] = {3,2,1,4,5};
MinHeap<int> m_heap(a,5);
int x,i;
for(i = 0; i < 5; i++){
m_heap.RemoveMin(x);
cout << x << " ";
}
cout << endl;
for(i = 0; i < 5; i++){
m_heap.Insert(a[i]);
}
for(i = 0; i < 5; i++){
m_heap.RemoveMin(x);
cout << x << " ";
}
cout << endl;
}
分享到:
相关推荐
文件读写 文件夹读写 各种加密解密 XML操作 NET实用类集-DotNet.Utilities.7z\C#实用类集-DotNet.Utilities
实用代码 09 Inception-v3图片分类实用代码 09 Inception-v3图片分类实用代码 09 Inception-v3图片分类实用代码 09 Inception-v3图片分类实用代码 09 Inception-v3图片分类实用代码 09 Inception-v3图片分类实用代码...
关机代理--最小的实用关机绿色软件关机代理--最小的实用关机绿色软件关机代理--最小的实用关机绿色软件关机代理--最小的实用关机绿色软件
全国通用版2018高考语文大一轮复习专题七实用类文本阅读-传记专题集训1中国人物传记.doc
网络实用技术阅读手册-V1.0.pdf网络实用技术阅读手册-V1.0.pdf网络实用技术阅读手册-V1.0.pdf网络实用技术阅读手册-V1.0.pdf网络实用技术阅读手册-V1.0.pdf网络实用技术阅读手册-V1.0.pdf网络实用技术阅读手册-V1.0....
合适研究底层研发员,但,一般程序员也必须掌握的要点 JDK研究系列--》util实用类util实用类(java.util part2)
2009word教程--实用--简单--高效--速成--免费 2009 word教程 -- 免费 支持 2009word教程--免费支持--技术就在你身边--看你是否能够掌握住!
C#实用类集-DotNet.Utilities-整理完整版,欢迎下载
2009word教程--实用--简单--高效--速成--免费 2009 word教程 -- 免费 支持 2009word教程--免费支持--技术就在你身边--看你是否能够掌握住!
2009word教程--实用--简单--高效--速成--免费 2009 word教程 -- 免费 支持 2009word教程--免费支持--技术就在你身边--看你是否能够掌握住!
2009word教程--实用--简单--高效--速成--免费 2009 word教程 -- 免费 支持 2009word教程--免费支持--技术就在你身边--看你是否能够掌握住!
2009word教程--实用--简单--高效--速成--免费 2009 word教程 -- 免费 支持 2009word教程--免费支持--技术就在你身边--看你是否能够掌握住!
AUTOCAD实用技巧-----定义属性块[归纳].pdf
巧用笔记本电脑实用技巧案例---1 并附有图文,操作简单
《实用化工计算机模拟-Matlab在化学工程中的应用》提供大量化工实例及MATLAB源程序。
《嵌入式系统实用教程》主 编:张同光;电子工业出版社;ISBN:978-7-121-09312-8;资源为该书实验用到的所有工具软件 及其 课件 。 清单 如下: 1. 嵌入式系统实用教程--课件 2. BusyBox配置菜单的详细选项 3. 第2...
C# 实用类集 DotNet.Utilities 整理完整版,集合的比较全。 C#实用类集-DotNet.Utilities-整理完整版,欢迎下载 C# 工具类 集合 完整版
路由跟踪器---绿色---简单实用----绿色---简单实用----绿色---简单实用----绿色---简单实用-
【实用方法】--制作CAD空心字,用于激光线切割【实用方法】--制作CAD空心字,用于激光线切割【实用方法】--制作CAD空心字,用于激光线切割【实用方法】--制作CAD空心字,用于激光线切割【实用方法】--制作CAD空心字...