NAME

Heap::MinMax - Min-Max Heap for Priority Queues etc.

SYNOPSIS

 use Heap::MinMax;

EXAMPLE 1

  # shows basic (default constructor) behavior of heap.
  # the default comparison function is floating-point numeric.

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


  my $mm_heap2 = Heap::MinMax->new();
  my @vals2 = (19.111111, 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);
  # ...  etc.

  $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 'dual' partially-sorted manner, such that finding both the minimum and the maximum element in the set takes constant time. This is accomplished through a modification of R.W. Floyd's original heap algorithm that introduces the notion of 'min' (even) levels and 'max' (odd) levels in the binary structure of the heap.

A comparison of the time complexities of Min-Max Heaps vs. regular Min Heaps is as follows:

                       Min Heap                     Min-Max 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)
 -----------------------------------------------------------------------------

METHODS

new()

 my $mm_heap = Heap::MinMax->new();

MinMax Heap constructor. Without any arguments, returns a heap that works with floating-point values. You can also supply a comparision function and an evaluation function (useful for printing).

array()

 my $heaps_array = $mm_heap->array();

Access the array that is used by the heap.

build_heap()

 $mm_heap->build_heap();

Builds a heap from heap object's array.

insert()

 $mm_heap->insert($thing);

or

 $mm_heap->insert(@things);

Add a value/object to the heap.

remove()

 my $found_thing = $mm_heap->remove($thing);

Really expensive arbitrary remove function. Looks through the array for value/object specified and removes it, then trickles heap-property down from that location. If you are using this function, you are not taking advantage of the power of Heaps. However, sometimes you gotta do what you gotta do.

min()

 my $min_thing = $mm_heap->min();

Returns the minimum value/object stored in the heap.

min_non_zero()

 my $min_non_zero_thing = $mm_heap->min_non_zero();

Returns the minimum non-zero value/object stored in the heap.

max()

 my $max_thing = $mm_heap->max();

Returns the maximum value/object stored in the heap.

pop_min()

 my $min_thing = $mm_heap->pop_min();

Removes and returns the minimum value/object stored in the heap.

pop_min_non_zero()

 my $min_non_zero_thing = $mm_heap->pop_min_non_zero();

Removes and returns the minimum non-zero value/object stored in the heap.

pop_max()

 my $min_thing = $mm_heap->pop_max();

Removes and returns the maximum value/object stored in the heap.

get_size()

 my $size = $mm_heap->get_size();

Returns the number of elements currently in the heap.

print()

 $mm_heap->print();

Dumps the contents of the heap to STDOUT.

DEPENDENCIES

Test::More (for installation and testing).

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.

cpanm Heap::MinMax

perl -MCPAN -e shell
install Heap::MinMax