NAME

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

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\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.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.  

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

A comparison of worst-case time complexities with regular Min 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)
-----------------------------------------------------------------------------

METHODS

 new()

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

 array()

Access the array that is used by the heap.

 build_heap()

Builds a heap from heap object's array.

 insert($)

Add a value/object to the heap.

 remove($)

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()

Returns the minimum value/object stored in the heap.

 max()

Returns the maximum value/object stored in the heap.

 pop_min()

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

 pop_max()

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

 get_size()

Returns the number of elements currently in the heap.

 print()

Dumps the contents of the heap to STDOUT.

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