Hello..
Below is my implementation of a max heap ..
I'd be grateful if any one can suggest any improvements .. or any better ways to implement
Thanks a lot !
Code:
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
template <class T>
class max_heap
{
private:
vector< T >heap;
inline int LEFT(const int &i) { return (i<<1)+1; }
inline int RIGHT(const int &i) { return (i<<1)+2; }
inline int PARENT(const int &i) { return (i&1)?i>>1:(i>>1)-1; }
void max_heapify(int i)
{
int left=LEFT(i);
int right=RIGHT(i);
int largest=i;
if(left < heap.size() && heap[left] > heap[largest]) largest=left;
if(right < heap.size() && heap[right]> heap[largest]) largest=right;
if(largest!=i)
{
swap(heap[largest],heap[i]);
max_heapify(largest);
}
}
void make_heap(const int &size)
{
for(int i=size/2;i>=0;i--)
max_heapify(i);
}
public:
max_heap(){}
max_heap(T *start,T *end)
{
for(int *it=start;it<end;it++)heap.push_back(*it);
make_heap(end-start);
}
void push(const T &key)
{
heap.push_back(key);
int i=heap.size()-1,p;
while(i)
{
p=PARENT(i);
if(heap[p]>=heap[i]) break;
swap(heap[p],heap[i]);
i=p;
}
}
inline T top()
{
return heap[0];
}
void pop()
{
heap[0]=heap[heap.size()-1];
heap.erase(heap.end()-1);
max_heapify(0);
}
void print_heap()
{
for(int i=0;i<heap.size();i++)
printf("%d ",heap[i]);
puts("");
}
};
int main()
{
return 0;
}