heap.hh
#ifndef HEAP_HH
#define HEAP_HH #include <iostream>
#include <stdexcept>
#include <cassert> using namespace std; template <typename T, int maxsize>class heap//模板类heap，类型T，常量maxsize
{
private:
int num_values;//当前存储的元素的数量
T values[maxsize];//存储元素的数组 int parent(int index)
{
return (index - ) / ;
} int left_child(int index)
{
return * index + ;
} int right_child(int index)
{
return * index + ;
} void sift_down(int index)
{
assert(index < num_values);
int left = left_child(index);
int right = right_child(index); if(left >= num_values)
{
return;
}
if(right >= num_values)
{
if(values[left] < values[index])
{
swap_values(index, left);
}
}
else
{
T left_value = values[left];
T right_value = values[right];
int swap_child; if(left_value < values[index] || right_value < values[index])
{
if(left_value < right_value)
{
swap_child = left;
}
else
swap_child = right;
swap_values(index, swap_child);
sift_down(swap_child);
}
}
} void sift_up(int index)
{
int parent_index = parent(index);
if(index == )
{
return;
}
assert(parent_index >= );
assert(parent_index != index);
if(values[index] < values[parent_index])
{
swap_values(index, parent_index);
if(parent_index != )
{
sift_up(parent_index);
}
}
} void swap_values(int i, int j)
{
T tmp; assert(i >= && i < num_values);
assert(j >= && j < num_values);
assert(i != j); tmp = values[i];
values[i] = values[j];
values[j] = tmp;
} public:
heap<T, maxsize>():num_values(){cout<<"初始化啦"<<endl;}//初始化,在模板中的内容就无需再初始化了，只要初始化非模板内容就可以了。 T get_first_value()
{
T result;
try
{
if(num_values == )
{
throw std::underflow_error("抛出异常：堆为空");
result = values[];
--num_values;
if(num_values != )
{
values[] = values[num_values];
sift_down();
}
return result;
}
}
catch (std::underflow_error &e)
{
cout << "捕捉异常：堆为空" << endl;
}
} void add_value(T value)
{
try
{
if(num_values >= maxsize)
{
throw std::overflow_error("抛出异常：堆为满");
}
values[num_values] = value;
++num_values;
}
catch (std::overflow_error &e)
{
cout << "捕捉异常：堆为满" << endl;
} if((num_values - )> )
sift_up(num_values - );
} T get_value(int index)
{
try
{ if(index >= maxsize)
{
throw std::overflow_error("抛出异常：访问越界");
}
return values[index];
}
catch (std::overflow_error &e)
{
cout << "捕捉异常：访问越界" << endl;
}
}
}; #endif
xyz.cc
#include <iostream>
#include <string>
#include "heap.hh"
#include <stdlib.h>
using namespace std; int main()
{
heap<int, >heapone; for(int i = ; i < ; i++)
{
heapone.add_value(i);
} // int lastval = heapone.get_first_value();
// cout<<"value0 = "<<lastval<<endl;; for(int i = ; i < ; i++)
{
cout<<"value"<<i<<" = "<<heapone.get_value(i)<<endl; // cout<<"value"<<i<<" = "<<heapone.get_first_value()<<endl; } cout<<heapone.get_first_value()<<endl;
for(int i = ; i < ; i++)
{
cout<<"value"<<i<<" = "<<heapone.get_value(i)<<endl; cout<<heapone.get_first_value()<<endl;
for(int i = ; i < ; i++)
{
cout<<"value"<<i<<" = "<<heapone.get_value(i)<<endl; // cout<<"value"<<i<<" = "<<heapone.get_first_value()<<endl; }
cout<<"value"<<i<<" = "<<heapone.get_first_value()<<endl; } }