heapsort.cc

int parent(int i)
{
  return i/2;
}

int left(int i)
{
  return i*2;
}
int right(int i)
{
  return 2*i+1;
}

int heap_size = 0;

template <class T,int N>
void max_heapfy(T array[N], int i)
{
  T l = left(i);
  T r = right(i);
  int largest;
  if (l<heap_size && array[l] > array [r]) {
    largest = l;
  }
  else {
    largest = i;
  }
  if (r<heap_size && array[r]>array[largest]) {
    largest = r;
  }
  if (largest != i) {
    T tmp = array[i];
    array[i] = array[largest];
    array[largest] = tmp;
    max_heapfy(array,largest);
  }
}

template <class T,int N>
void min_heapfy(T array[N], int i)
{
  T l = left(i);
  T r = right(i);
  int least;
  if (l<heap_size && array[l] < array [r]) {
    least = l;
  }
  else {
    least = i;
  }
  if (r<heap_size && array[r]<array[least]) {
    least = r;
  }
  if (least != i) {
    T tmp = array[i];
    array[i] = array[least];
    array[least] = tmp;
    max_heapfy(array,least);
  }
}



template <class T,int N>
void build_max_heap(T array[N])
{
  heap_size = N;
  for (int i = N / 2;i>0;i--) {
    max_heapfy(array,i);
  }
}


template <class T,int N>
void build_min_heap(T array[N])
{
  heap_size = N;
  for (int i= N / 2;i>0;i--) {
    min_heapfy(array,i);
  }
}

template <class T,int N>
void heap_maximum(T array[N])
{
  return array[0];
}


template <class T,int N>
T heap_extract_max(T array[N])
{
  if (heap_size<0) {
    throw "error";
  }
  int max = array[0];
  array[0] = array[heap_size];
  heap_size = heap_size-1;
  max_heapfy(array,0);
  
  return max;
}




template <class T,int N>
T heap_extract_min(T array[N])
{
  if (heap_size<0) {
    throw "error";
  }
  int min = array[0];
  array[0] = array[heap_size];
  heap_size = heap_size-1;
  min_heapfy(array,0);
  
  return min;
}


template<class T,int N>
void heap_increase_key(T array[N],int i, T key)
{
  if (key<array[i]) {
    throw "error";
  }
  array[i] = key;
  while (i>1 && array[parent(i)]<array[i]) {
    array[i] = array[parent(i)];
    i = parent(i);
  }
}

template<class T, int N>
void heap_decrase_key(T array[N], int i, T key)
{
  if (key<array[i]) {
    throw "error";
  }
  array[i] = key;
}

template<class T, int N>
void max_heap_insert(T array[N], T key)
{
  heap_size = heap_size+1;
  array[heap_size] = -1;
  heap_increase_key(array,heap_size,key);
}

template<class T, int N>
void min_heap_insert(T array[N], T key)
{
  heap_size = heap_size+1;
  array[heap_size] = -1;
  heap_decrase_key(array,heap_size,key);
}