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; }



LinkBack URL
About LinkBacks


