All pastes #53289 Raw Edit

Heap Template Class

public cpp v1 · immutable
#53289 ·published 2006-05-03 19:50 UTC
rendered paste body
#include <vector>#include <math.h>using namespace std;#ifndef HEAP_H#define HEAP_Htemplate<class T>class minHeap {                  public:void push(T);T pop();T top(){return Heap.front();};minHeap()    { size = 0;}minHeap(T ar[],int sz)    {     size = 0;     for (int i = 0 ; i < sz ; i++)       push(ar[i]);      buildminheap();    }void print(){    for (int i = 0 ; i < size ; i++)    cout<<Heap[i]<<endl;    }protected:private:vector<T> Heap; size_t size;int giveleft(int  i) {  return  2*i + 1; }int giveright(int  i) {  return  2*i + 2; }void Heapsort();void minHeapify(T);size_t giveparent(size_t);void buildminheap();};	template <class T>void swap(vector<T> A, int i, int j){  T temp = A[i];  A[i] = A[j];  A[j] = temp;}template<class T>void minHeap<T>::buildminheap(){for (int i = (size/2)-1; i >=0 ; i --)	minHeapify(i);}template <class T>size_t minHeap<T>::giveparent(size_t index){  return (size_t(floor((index-1) / 2)));}template<class T>void minHeap<T>::minHeapify(T i){T l = giveleft(i);T r = giveright(i);T largest;if (l <=size-1 && Heap[l]<Heap[i])       largest = l;   else       largest = i;if (r <=size-1 && Heap[r]<Heap[largest])   largest = r;if (largest != i){   T temp = Heap[i];   Heap[i] = Heap[largest];   Heap[largest] = temp;   minHeapify(largest);}}template<class T>void minHeap<T>::push(T item){Heap.push_back(item); for(size_t i=size; i>0 && (Heap[giveparent(i)] > Heap[i]); i = giveparent(i))    swap(Heap[giveparent(i)], Heap[i]);size++;}template<class T>T minHeap<T>::pop(){T temp = Heap[0];Heap[0] = Heap[size-1];size--;minHeapify(0);return(temp);}                      template<class T>void minHeap<T>::Heapsort(){buildminheap(); for (int i = size-1; i >= 1; i--)  {    T temp = Heap[0];    Heap[0] = Heap[i];    Heap[i] = temp;    minHeapify(i-1);  }} #endif