жаль, попробовал встроить s в T, как-то вроде еще кривее получилось:
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
#include <vector>
using std::vector;
template<class T> void swap(T& a,T& b){
T t=a;
a=b;
b=t;
}
template<class T> void heapify(T& v,size_t i) {
// if(!s) s=v.size()-1;
if(i*2>v.s) return;
if(i*2==v.s) {
if (v[i]<v[i*2]) swap(v[i],v[i*2]);
return;
}
size_t max=i*2;
if(v[max]<v[max+1]) max++;
if(v[i]<v[max]) {
swap(v[i],v[max]);
heapify(v,max);
}
}
template<class T> void make_heap(T& v){
v.s=v.size()-1;
for(size_t i=v.s/2;i>0;i--) heapify(v,i);
}
template<class T> void heap_sort(T& v) {
//T& n=*(new T);
//while(v.size()>0);
// v.s=v.size()-1;
make_heap(v);
while(v.s>1) {
swap(v[1],v[v.s--]);
heapify(v,1);
}
return ;
}
template<class T> class heap_vector: public vector<T> {
public:
size_t s;
heap_vector(size_t ss=0):s(ss){
this->push_back(0);
}
};
int main(){
while(cin) {
//vector<int> vi;
heap_vector<int> vi;
int i=0;
while(cin>>i && i) vi.push_back(i);
// make_heap(vi);
heap_sort(vi);
for(size_t i=0;i<vi.size();i++) cout<<vi[i]<<"\t";
cout<<endl;
vi.clear();
}
}
может как-то можно избежать вставления в vector еще 1й переменной?
такой синтаксис подойдет для возвращения ссылки на итератор?
T& n=*(new T);
