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