NAME

Heap::MinMax - Perl implementation of a Min-Max Heap.

SYNOPSIS

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();
  print "min was: $min\n\n";
  my $max = $mm_heap->pop_max();
  print "max was: $max\n\n";
  $mm_heap->print_heap();



  my $mm_heap2 = Heap::MinMax->new();
  my @vals2 = (19, 14, 15, 17);
  $mm_heap2->insert(@vals2);
  $mm_heap2->insert(20);
  $mm_heap2->print_heap();
  print $mm_heap2->max() . "\n\n";

  exit

EXAMPLE 2

  # shows how you can store any set of comparable objects in heap.  

  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;

DESCRIPTION

An implementation of a Min-Max Heap as described in "Min-Max Heaps and Generalized Priority Queues", Atkinson, Sack, Santoro, Strothotte, 1986.

Min-Max heaps allow objects to be stored in a partially-sorted manner such that the time it takes to find either the minimum OR maximum element in the set takes constant time.

A comparison of worst-case time complexities with regular Min Heaps or Max Heaps is as follows:

                       Min Heap                     MinMax Heap
-----------------------------------------------------------------------------
Create                2*n                            (7/3)*n
Insert                log(n+1)                       0.5*log(n+1)
DeleteMin             2*log(n)                       2.5*log(n)
DeleteMax             0.5*n+log(n)                   2.5*log(n)
-----------------------------------------------------------------------------

EXPORT

None.

SEE ALSO

"Min-Max Heaps and Generalized Priority Queues", Atkinson, Sack, Santoro, Strothotte, 1986.

AUTHOR

Matthias Beebe, <matthiasbeebe@gmail.com>

COPYRIGHT AND LICENSE

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.