Heap-MinMax version 0.04
========================
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.