Subversion Repositories heap_sorter

#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include "wz_hsort.h"
 
sort_data sort_mem[SORT_LEN];
sort_data heap_sort (sort_data val)
{
  sort_data res;
  sort_data cur = val;
  int lev, offs, top, left, right;
  cur = sort_mem[1];
  if (val.key <= cur.key)
    return val;			//No need to update the heap
  else
    {
      res = cur;
      cur = val;
      offs = 0;
      for (lev = 1; lev <= NM; lev++)
	{
	  top = (1 << (lev - 1)) + offs;
	  left = (2 << (lev - 1)) + offs;
	  right = (3 << (lev - 1)) + offs;
	  if ((lev == NM) ||
	      ((cur.key <= sort_mem[left].key) &&
	       (cur.key <= sort_mem[right].key)))
	    {
	      sort_mem[top] = cur;
	      break;
	    }
	  else if ((sort_mem[left].key < cur.key) &&
		   (sort_mem[left].key <= sort_mem[right].key))
	    {
	      sort_mem[top] = sort_mem[left];
	    }
	  else if (sort_mem[right].key < cur.key)
	    {
	      sort_mem[top] = sort_mem[right];
	      offs += (1 << (lev - 1));
	    }
	  else
	    {
	      printf ("impossible!!!\n");
	    }
	}
    }
  return res;
}