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.