#ifndef HEAP
#define HEAP
template<class T>
class Heap
{
private:
T *data;
int size;
int maxSize;
void Sink(int start,int m); //从start到m下滑调整成最小堆
void Raise(int start); //从start到0上滑调整成最小堆
public:
Heap(){data=new T[100]; maxSize=100; size=0;}
Heap(int _maxSize);
Heap(T arr[],int length);
~Heap(){delete []data;}
void Push(T x);
T PopMin();
bool IsEmpty(){return size==0?true:false;}
int Size(){return size;}
void Clear(){size=0;}
void Out();
};
#endif
template<class T>
void Heap<T>::Sink(int start, int m)
{
int i,j;
T temp=data[start];
for(i=start,j=2*i+1; j<=m; i=j,j=2*j+1)
{
if(j<m&&data[j]>data[j+1]) j++;
if(temp<data[j])
break;
else
data[i]=data[j];
}
data[i]=temp;
}
template<class T>
void Heap<T>::Raise(int start)
{
int i,j;
T temp=data[start];
for(j=start,i=(j-1)/2; j>0; j=i,i=(i-1)/2)
if(data[i]<temp)
break;
else
data[j]=data[i];
data[j]=temp;
}
template<class T>
Heap<T>::Heap(int _maxSize)
{
maxSize=_maxSiz>=100?_maxSiz:100;
data=new T[maxSize];
size=0;
if(data==NULL)
Error("堆建立失败");
}
template<class T>
Heap<T>::Heap(T arr[], int length)
{
maxSize=length;
data=new T[mmaxSize];
for(int i=0;i<n;i+)
{
data[i]=arr[i];
size++;
}
int current=size/2-1;
while(current>=0)
{
Sink(current,size-1);
current--;
}
}
template<class T>
void Heap<T>::Push(T x)
{
if(size>=maxSize)
return;
data[size]=x;
Raise(size);
size++;
}
template<class T>
T Heap<T>::PopMin()
{
if(size==0)
Error("弹出数据错误!");
T x;
x=data[0];
data[0]=data[size-1];
size--;
Sink(0,size-1);
return x;
}
template<class T>
void Heap<T>::Out()
{
for(int i=0;i<size;i++)
{
cout<<data[i]<<",";
}
}
分享到:
相关推荐
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一...
B 堆- 最大和最小堆版本 B 优先队列 A 特里树 A 树 A 二叉搜索树 A AVL树 A 红黑树 A 线段树- 带有最小/最大/总和范围查询示例 A Fenwick 树(二元索引树) A 图(有向图和无向图) A 不相交集- 联合查找数据结构或...
4.3 数据输入输出的概念及在 C 语言中的实现 54 4.4 字符数据的输入输出 54 4.4.1 putchar 函数(字符输出函数) 54 4.4.2 getchar函数(键盘输入函数) 55 4.5 格式输入与输出 55 4.5.1 printf 函数(格式输出函数...
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
《数据结构》(C语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参考教材。本书的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其应用;后半部分主要讨论查找和排序的...
在计算机科学发展过程中,早期数据结构教材大都采用PASCAL语言为描述工具,后来出现了采用C语言为描述工具的教材版本、至今又出现了采用C++语言为描述工具的多种教材版本。本教实验指导书是为已经学习过C++语言的...
数据结构算法的实现(其中有flash播放),对学习数据结构,学习常用算法以及对其进行实现很有帮助。包括各种排序算法(插入排序,快速排序,选择排序,归并排序,基数排序,计数排序,桶排序、冒泡排序,堆排序等等...
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
Java数据结构和算法中文第二版(1) Java数据结构和算法中文第二版(2) 【内容简介】 本书可帮助读者: 通过由基于JAVA的演示所组成的可视专题讨论来掌握数据结构和算法 学会如何为常见和不太常见的编程条件选择...
《数据结构》(c语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参数教材。学了数据结构后,许多以前写起来很繁杂的代码现在写起来很清晰明了. 本书的前半部分从抽象数据类型的...
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
《数据结构》(C语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参数教材。学了数据结构后,许多以前写起来很繁杂的代码现在写起来很清晰明了. 本书的前半部分从抽象数据类型的...