Heap-MinMax version 1.02
========================

This is an implementation of a Min-Max Binary Heap, based on 1986 article
"Min-Max Heaps and Generalized Priority Queues" by Atkinson, Sack, 
Santoro, and Strothotte, published in Communications of the ACM.

In a Min-Max heap, objects are stored in partial order such that both the
minimum element and maximum element are available in constant time.  This 
is accomplished through a modification of the standard heap algorithm that
introduces the notion of 'min' (even) levels and 'max' (odd) levels in the
binary tree structure of the heap.  

With a Min-Max heap you get all this, plus insertion into a Min-Max heap is 
actually *faster* than with a normal heap (by a constant factor of 0.5).

For further information about the algorithm, please see the article "Min-Max 
Heaps and Generalized Priority Queues" by Atkinson, Sack,  Santoro, and 
Strothotte, published in Communications of the ACM in 1986.

  ################################################################
  #
  # Example 1
  #
  # shows basic (default constructor) behavior of heap.
  # the default comparison function is numeric.
  #  
  ################################################################

  use Heap::MinMax;

  my $mm_heap = Heap::MinMax->new();
  my @vals = (2, 1, 3, 7, 9, 5, 8);
  foreach my $val (@vals){    
    $mm_heap->insert($val);
  }
  $mm_heap->print_heap();
  my $min = $mm_heap->pop_min(); # returns 1
  print "min was: $min\n\n";
  my $max = $mm_heap->pop_max(); # returns 9
  print "max was: $max\n\n";
  $mm_heap->print_heap(); # outputs:
                          # 2
			  # 7
			  # 8
			  # 5
			  # 3
			  



  my $mm_heap2 = Heap::MinMax->new();
  my @vals2 = (19.1111111, 19.111112, 15, 17);
  $mm_heap2->insert(@vals2);
  $mm_heap2->insert(19.11110);
  $mm_heap2->print_heap();
  print $mm_heap2->max() . "\n"; # output 19.111112
  print $mm_heap2->min() . "\n"; # output 15

  exit

  ################################################################
  #
  # Example 2
  #
  # shows how you can store any set of comparable objects in heap.
  #
  #
  #  Note: in this example, anonymous subroutines are
  #  passed in to the constructor, but you can just as well supply
  #  your own object's comparison methods by name-   i.e.,
  #
  #  $avltree = Heap::MinMax->new(
  #          fcompare => \&MyObj::compare,
  #           
  #          . . . 
  #           
  #          etc...
  #
  ################################################################

  use Heap::MinMax;

  my $elt1 = { _name => "Bob",
  	     _phone => "444-4444",};
  my $elt2 = { _name => "Amy",
	     _phone => "555-5555",};
  my $elt3 = { _name => "Sara",
	     _phone => "666-6666",}; 

  my $mm_heap3 = Heap::MinMax->new(

      fcompare => sub{ my ($o1, $o2) = @_;
  		     if($o1->{_name} gt $o2->{_name}){ return 1}
  		     elsif($o1->{_name} lt $o2->{_name}){ return -1}
  		     return 0;},

      feval     => sub{ my($obj) = @_;
  		       return $obj->{_name} . ", " . $obj->{_phone};},   
      );


  $mm_heap3->insert($elt1);
  $mm_heap3->insert($elt2);
  $mm_heap3->insert($elt3);

  $mm_heap3->print();



  exit;



INSTALLATION

To install this module type the following:

   perl Makefile.PL
   make
   make test
   make install

DEPENDENCIES

This module requires these other modules and libraries:

   none.

COPYRIGHT AND LICENCE

Copyright (C) 2009 by Matthias Beebe

This library is free software; you can redistribute it and/or modify
it under the same terms as Perl itself, either Perl version 5.8.8 or,
at your option, any later version of Perl 5 you may have available.