Matthias Beebe > Heap-MinMax-1.03 > Heap::MinMax
Module Version: 1.03   Source   Latest Release: Heap-MinMax-1.04

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

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

# AUTHOR

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: