最小(大)堆是比较常用的数据结构,是实现优先队列和堆排序的基础,也可以实现例如霍夫曼编码,贪心算法等,具有很好的时间复杂性.
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;
}
分享到:
相关推荐
"2008cssplay实用css代码精选-实用二级导航条"是针对CSS技术的一个主题集合,特别关注于创建高效、响应式的二级导航条。下面我们将深入探讨这个主题,了解如何利用CSS实现功能强大且视觉吸引人的二级导航条。 一、...
堆可以分为最大堆和最小堆,最大堆中每个父节点的值都大于或等于其子节点的值,而最小堆则相反,每个父节点的值小于或等于子节点的值。 首先,我们需要理解堆的基本操作。建堆通常从最后一个非叶子节点开始,按照从...
### 类模板案例——数组类封装 #### 概述 本篇文档主要介绍了一个基于 C++ 的...同时,通过提供的测试函数,验证了 `MyArray` 类的功能正确性和实用性。这对于学习 C++ 面向对象编程和模板应用具有很好的参考价值。
通过反编译,开发者可以深入理解APK的内部机制,查找潜在的bug,或者研究其他应用的设计模式和实现细节。对于教学和学习Android开发来说,jadx-gui也是一个强大的资源,因为它提供了一种直观的方式来查看和理解已...
在布局方面,Qt-Advanced-Docking-System允许你创建复杂的停靠布局,包括水平和垂直堆叠、网格布局,甚至可以创建多层嵌套的停靠区域。通过`DockLayout`类,你可以精确控制各个DockWidget的位置和尺寸。 对于...
在深度学习领域,循环神经网络(Recurrent Neural ...总的来说,这个项目提供了一个实用的起点,让Matlab用户能够深入了解和应用RNN-LSTM网络,对于学习深度学习特别是序列数据处理的人员来说,是一份宝贵的资源。
column.addColumnValue(new ColumnValue(20).setLabel("第二类")); column.addColumnValue(new ColumnValue(30).setLabel("第三类")); // 设置列的颜色 column.setColor(Color.BLUE); // 将Column添加到...
### Java工作实用篇知识点概述 #### 1. Java生成带Logo及名称的二维码 - **技术背景**: 在当前数字化时代,二维码被广泛应用于各种场景,包括但不限于产品追踪、广告推广等。利用Java来生成带有公司Logo及商品名称...
在计算机科学领域,路径搜索是图论中的一个关键问题,特别是在网络...这个实现可能包括了类设计、路径表示、搜索策略以及性能优化等多个方面的技巧,对于任何有兴趣于网络分析或算法实现的人来说都是宝贵的学习资源。
2. **commons-collections-3.2.1.jar**: 包含了对 Java 内置集合框架的扩展和增强,如多维数组、堆、双向队列、优先级队列、图结构等,以及各种实用的集合操作方法,如排序、查找、过滤等。 3. **commons-lang3-...
8. **实现细节**:在`利用堆实现带有文件操作的huffman编码.cpp`源文件中,应包含适当的头文件,定义数据结构(如节点类),实现堆操作(如插入、删除最小元素),以及哈夫曼编码和解码的算法。同时,文件操作的代码...
3D印刷技术的应用不仅提升了家电面板的视觉吸引力,还增强了产品的实用性和耐用性。下面是对3D印刷装饰家电面板制作方法的详细说明和分析。 1. **3D印刷技术简介** 3D印刷,也称为增材制造,是一种通过逐层堆积...
Apache Commons Collections库包含了多种类型的集合实现,例如双向列表、多值映射、堆和优先级队列、堆栈、队列、属性类以及各种实用工具类。这些类和接口为开发人员提供了处理集合的高级功能,比如过滤、转换、比较...
### C++编程思想_第二卷_实用编程技术 #### 一、面向对象编程(OOP) C++是一种支持面向对象编程的语言。这一章节可能会详细介绍如何在C++中实现面向对象的概念,包括但不限于: - **类与对象**:介绍如何定义类...
7. **队列和堆**:实现了优先队列和最小/最大堆,用于高效地处理数据。 8. **Bag接口**:提供了计数集合,其中元素可以有多个副本,支持按元素计数的操作。 9. **多值映射**:允许一个键对应多个值,如`...
- 它还包括了各种集合操作,如列表和映射的过滤、转换、合并、排序等功能,以及一些实用的集合算法,如集合的查找、比较、堆排序等。 这三个库在Java开发中经常一起使用,因为它们各自解决了不同领域的问题,共同...
实际上我比较喜欢java(少接触Ruby 罢了)但是jquery的简单的实用的确有相当大的吸引力啊!在项目里我把jquery作为自己唯一的框架类包。使用其间也有一点点心得,其实这些心得,在jquery的文档上面也可能有讲,不过...
在Excel中创建多列堆积柱状图是一种常见且实用的数据可视化方法,特别是在比较不同类别间的数值差异时。本文将详细讲解如何使用Excel的散点图功能来实现这一目标,并着重介绍如何让X轴标签居中显示,提升图表的美观...
数据结构是计算机科学中的核心课程之一,它研究如何在计算机中组织和管理数据,以便高效地进行存储、检索和操作。清华大学出版的《数据结构实用教程》第二版是一本广泛使用的教材,它深入浅出地介绍了各种数据结构...
"易语言堆内存操作类"是基于易语言开发的一个库或组件,用于实现对Windows系统的堆内存进行操作。在计算机编程中,堆内存是一种动态内存分配方式,通常用于存储大小不确定或者在程序运行时才能确定大小的数据。 堆...