`

实用类之二-----最大堆的实现

 
阅读更多
最小(大)堆是比较常用的数据结构,是实现优先队列和堆排序的基础,也可以实现例如霍夫曼编码,贪心算法等,具有很好的时间复杂性.
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代码精选-实用二级导航条

    "2008cssplay实用css代码精选-实用二级导航条"是针对CSS技术的一个主题集合,特别关注于创建高效、响应式的二级导航条。下面我们将深入探讨这个主题,了解如何利用CSS实现功能强大且视觉吸引人的二级导航条。 一、...

    用C++写的堆排序(最大堆和最小堆)

    堆可以分为最大堆和最小堆,最大堆中每个父节点的值都大于或等于其子节点的值,而最小堆则相反,每个父节点的值小于或等于子节点的值。 首先,我们需要理解堆的基本操作。建堆通常从最后一个非叶子节点开始,按照从...

    算法实现-algorithm-master.zip

    排序算法作为算法中最早被广泛研究的领域之一,在这个代码库中可能会包含冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等经典排序算法的实现。这些排序算法在实际应用中根据数据量的大小和数据特性来...

    类模板案例--数组类封装

    ### 类模板案例——数组类封装 #### 概述 本篇文档主要介绍了一个基于 C++ 的...同时,通过提供的测试函数,验证了 `MyArray` 类的功能正确性和实用性。这对于学习 C++ 面向对象编程和模板应用具有很好的参考价值。

    datastructures-堆排序

    堆排序是一种基于比较的排序算法,它是选择排序的一种。...堆排序是一种高效且实用的排序算法,它利用堆这种数据结构的特点,实现了高效的元素比较和交换,是学习算法和数据结构时不可忽视的重要内容。

    Python实现堆排序算法代码

    具体操作为将堆顶元素(最大堆中是最大值,最小堆中是最小值)与堆的最后一个元素交换,然后将新的堆顶元素下沉到合适的位置,保证除了最后一个元素外,前面的数组元素继续保持堆的性质。重复这个过程,直到所有元素...

    jadx-gui-1.1.0-with-jre-windows.zip

    通过反编译,开发者可以深入理解APK的内部机制,查找潜在的bug,或者研究其他应用的设计模式和实现细节。对于教学和学习Android开发来说,jadx-gui也是一个强大的资源,因为它提供了一种直观的方式来查看和理解已...

    qt Qt-Advanced-Docking-System 使用教程 示例代码

    在布局方面,Qt-Advanced-Docking-System允许你创建复杂的停靠布局,包括水平和垂直堆叠、网格布局,甚至可以创建多层嵌套的停靠区域。通过`DockLayout`类,你可以精确控制各个DockWidget的位置和尺寸。 对于...

    RNN-LSTM卷积神经网络Matlab实现.zip

    在深度学习领域,循环神经网络(Recurrent Neural ...总的来说,这个项目提供了一个实用的起点,让Matlab用户能够深入了解和应用RNN-LSTM网络,对于学习深度学习特别是序列数据处理的人员来说,是一份宝贵的资源。

    Android 实用HelloCharts实现 线性图、柱状图

    column.addColumnValue(new ColumnValue(20).setLabel("第二类")); column.addColumnValue(new ColumnValue(30).setLabel("第三类")); // 设置列的颜色 column.setColor(Color.BLUE); // 将Column添加到...

    【JCR2区】Matlab实现雪融优化算法SAO-LSSVM实现数据分类算法研究.rar

    该算法将问题的潜在解视为雪崩过程中雪块的位置,通过模拟雪崩的物理过程来寻求全局最优解。SAO算法在很多工程优化问题中显示出良好的搜索效率和求解质量。 最小二乘支持向量机(LSSVM)是一种改进的支持向量机...

    Java工作实用篇.pdf

    ### Java工作实用篇知识点概述 #### 1. Java生成带Logo及名称的二维码 - **技术背景**: 在当前数字化时代,二维码被广泛应用于各种场景,包括但不限于产品追踪、广告推广等。利用Java来生成带有公司Logo及商品名称...

    基于Java的最短路径算法实现 k-shortest-paths.zip

    在计算机科学领域,路径搜索是图论中的一个关键问题,特别是在网络...这个实现可能包括了类设计、路径表示、搜索策略以及性能优化等多个方面的技巧,对于任何有兴趣于网络分析或算法实现的人来说都是宝贵的学习资源。

    apache-common最全的jar包

    2. **commons-collections-3.2.1.jar**: 包含了对 Java 内置集合框架的扩展和增强,如多维数组、堆、双向队列、优先级队列、图结构等,以及各种实用的集合操作方法,如排序、查找、过滤等。 3. **commons-lang3-...

    利用堆实现带有文件操作的huffman编译码

    8. **实现细节**:在`利用堆实现带有文件操作的huffman编码.cpp`源文件中,应包含适当的头文件,定义数据结构(如节点类),实现堆操作(如插入、删除最小元素),以及哈夫曼编码和解码的算法。同时,文件操作的代码...

    行业分类-电子-3D印刷装饰家电面板的制作方法的说明分析.rar

    3D印刷技术的应用不仅提升了家电面板的视觉吸引力,还增强了产品的实用性和耐用性。下面是对3D印刷装饰家电面板制作方法的详细说明和分析。 1. **3D印刷技术简介** 3D印刷,也称为增材制造,是一种通过逐层堆积...

    commons-collections4-4.4-bin.zip

    Apache Commons Collections库包含了多种类型的集合实现,例如双向列表、多值映射、堆和优先级队列、堆栈、队列、属性类以及各种实用工具类。这些类和接口为开发人员提供了处理集合的高级功能,比如过滤、转换、比较...

    【JCR一区级】Matlab实现雪融优化算法SAO-DBN实现轴承故障分类算法研究.rar

    深度信念网络是一种深度学习模型,它由多层受限玻尔兹曼机(Restricted Boltzmann Machine, RBM)堆叠而成,具有强大的特征提取和数据表示能力。通过逐层贪婪预训练和微调,DBN能够在保持网络结构的复杂性的同时,提取...

    commons-collections-3.2.1.jar

    7. **队列和堆**:实现了优先队列和最小/最大堆,用于高效地处理数据。 8. **Bag接口**:提供了计数集合,其中元素可以有多个副本,支持按元素计数的操作。 9. **多值映射**:允许一个键对应多个值,如`...

    commons-beanutils-1.8.3.jar commons-codec-1.7.jar commons-collections-3.2.1.jar

    - 它还包括了各种集合操作,如列表和映射的过滤、转换、合并、排序等功能,以及一些实用的集合算法,如集合的查找、比较、堆排序等。 这三个库在Java开发中经常一起使用,因为它们各自解决了不同领域的问题,共同...

Global site tag (gtag.js) - Google Analytics