/*
 *  Heap - Heap-Sort with Peak Window-Size
 *  Copyright (c) 2004 Jonathan A. Zdziarski
 *
 *  This sorting algorithm is designed to return the top N elements of a
 *  collection. N is commonly referred to as "peak window-size". The algorithm
 *  performs particularly well when there is a small window-size, such as 15 to 
 *  accomodate a typical Grahmian-Bayes calculation.
 *
 *  The algorithm performs the sort at insertion time and, when complete, 
 *  provides the most significant N items in order of least to greatest. 
 *
 *  A heap is first created with zero elements, and is allowed to grow to the
 *  desired window-size. Each element inserted into the sort is then compared
 *  with the existing heap, and inserted into the correct position. If the
 *  heap then exceeds window-size, the least significant element is tossed.
 *  If the presented insertion is the least significant element, it is
 *  discarded. Because the heap is sorted from smallest to largest values,
 *  elements presented need to fail only one comparison to be discarded once
 *  the heap is full, making it very fast.
 *
 *  This algorithm is also fast because, unlike other sorts whose
 *  output is a permutation of the input, this sort only outputs N elements,
 *  where N is the peak window size, and discards the rest. Therefore, the 
 *  running time of the algorithm depends more on the window-size, rather than
 *  number of inputs.
 * 
 *  This particular implementation is geared toward Bayesian p-value sorting
 *  and uses a floating point value to accomodate a delta-based value. An
 *  unsigned long long (64-bit integer) is also used to accomodate a token's
 *  hash key (for example, CRC64). Either of these datatypes should be 
 *  relatively painless to alter.
 *
 *  LICENSE
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License
 *  as published by the Free Software Foundation; either version 2
 *  of the License, or (at your option) any later version.
 * 
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 * 
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 */

#ifndef _HEAP_H
#define _HEAP_H

/* The heap-sort structure itself */

struct heap
{
  unsigned int items;
  unsigned int size;
  struct heap_node *root;
};


/* A single element in heap of top N elements */

struct heap_node
{
  double delta;
  unsigned long long key;
  struct heap_node *next;
};

struct heap *	heap_create	(int window_size);
int		heap_destroy	(struct heap *);

struct heap_node *heap_node_create (double delta, unsigned long long key);
int heap_insert (struct heap *heap, double delta, unsigned long long key);

#endif /* _HEAP_H */