Matthias Beebe >
Heap-MinMax >
Heap::MinMax

Module Version: 1.04
Heap::MinMax - Min-Max Heap for Priority Queues etc.

use Heap::MinMax;

# 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

# 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;

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

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

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

Access the array that is used by the heap.

$mm_heap->build_heap();

Builds a heap from heap object's array.

$mm_heap->insert($thing);

or

$mm_heap->insert(@things);

Add a value/object to the heap.

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.

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

Returns the minimum value/object stored in the heap.

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

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

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

Returns the maximum value/object stored in the heap.

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

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

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

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

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

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

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

Returns the number of elements currently in the heap.

$mm_heap->print();

Dumps the contents of the heap to STDOUT.

Test::More (for installation and testing).

None.

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

Matthias Beebe, <matthiasbeebe@gmail.com>

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.

syntax highlighting: