Initial commit of OpenSPARC T2 design and verification files.

[OpenSPARC-T2-DV] / tools / perl-5.8.0 / man / man3 / Heap.3

.\" Automatically generated by Pod::Man v1.34, Pod::Parser v1.13
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sh \" Subsection heading
.br
.if t .Sp
.ne 5
.PP
\fB\\$1\fR
.PP
..
.de Sp \" Vertical space (when we can't use .PP)
.if t .sp .5v
.if n .sp
..
.de Vb \" Begin verbatim text
.ft CW
.nf
.ne \\$1
..
.de Ve \" End verbatim text
.ft R
.fi
..
.\" Set up some character translations and predefined strings.  \*(-- will
.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
.\" double quote, and \*(R" will give a right double quote.  | will give a
.\" real vertical bar.  \*(C+ will give a nicer C++.  Capital omega is used to
.\" do unbreakable dashes and therefore won't be available.  \*(C` and \*(C'
.\" expand to `' in nroff, nothing in troff, for use with C<>.
.tr \(*W-|\(bv\*(Tr
.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
.ie n \{\
.    ds -- \(*W-
.    ds PI pi
.    if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
.    if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\"  diablo 12 pitch
.    ds L" ""
.    ds R" ""
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    ds -- \|\(em\|
.    ds PI \(*p
.    ds L" ``
.    ds R" ''
'br\}
.\"
.\" If the F register is turned on, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.Sh), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.if \nF \{\
.    de IX
.    tm Index:\\$1\t\\n%\t"\\$2"
..
.    nr % 0
.    rr F
.\}
.\"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.hy 0
.if n .na
.\"
.\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
.\" Fear.  Run.  Save yourself.  No user-serviceable parts.
.    \" fudge factors for nroff and troff
.if n \{\
.    ds #H 0
.    ds #V .8m
.    ds #F .3m
.    ds #[ \f1
.    ds #] \fP
.\}
.if t \{\
.    ds #H ((1u-(\\\\n(.fu%2u))*.13m)
.    ds #V .6m
.    ds #F 0
.    ds #[ \&
.    ds #] \&
.\}
.    \" simple accents for nroff and troff
.if n \{\
.    ds ' \&
.    ds ` \&
.    ds ^ \&
.    ds , \&
.    ds ~ ~
.    ds /
.\}
.if t \{\
.    ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
.    ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
.    ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
.    ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
.    ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
.    ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
.\}
.    \" troff and (daisy-wheel) nroff accents
.ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
.ds 8 \h'\*(#H'\(*b\h'-\*(#H'
.ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
.ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
.ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
.ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
.ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
.ds ae a\h'-(\w'a'u*4/10)'e
.ds Ae A\h'-(\w'A'u*4/10)'E
.    \" corrections for vroff
.if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
.if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
.    \" for low resolution devices (crt and lpr)
.if \n(.H>23 .if \n(.V>19 \
\{\
.    ds : e
.    ds 8 ss
.    ds o a
.    ds d- d\h'-1'\(ga
.    ds D- D\h'-1'\(hy
.    ds th \o'bp'
.    ds Th \o'LP'
.    ds ae ae
.    ds Ae AE
.\}
.rm #[ #] #H #V #F C
.\" ========================================================================
.\"
.IX Title "Heap 3"
.TH Heap 3 "2003-12-04" "perl v5.8.0" "User Contributed Perl Documentation"
.SH "NAME"
Heap \- Perl extensions for keeping data partially sorted
.SH "SYNOPSIS"
.IX Header "SYNOPSIS"
.Vb 1
\&  use Heap;
.Ve
.PP
.Vb 2
\&  my $heap = Heap->new;
\&  my $elem;
.Ve
.PP
.Vb 1
\&  use Heap::Elem::Num(NumElem);
.Ve
.PP
.Vb 4
\&  foreach $i ( 1..100 ) {
\&      $elem = NumElem( $i );
\&      $heap->add( $elem );
\&  }
.Ve
.PP
.Vb 3
\&  while( defined( $elem = $heap->extract_maximum ) ) {
\&      print "Smallest is ", $elem->val, "\en";
\&  }
.Ve
.SH "DESCRIPTION"
.IX Header "DESCRIPTION"
The Heap collection of modules provide routines that manage
a heap of elements.  A heap is a partially sorted structure
that is always able to easily extract the smallest of the
elements in the structure (or the largest if a reversed compare
routine is provided).
.PP
If the collection of elements is changing dynamically, the
heap has less overhead than keeping the collection fully
sorted.
.PP
The elements must be objects as described in \*(L"Heap::Elem\*(R"
and all elements inserted into one heap must be mutually
compatible \- either the same class exactly or else classes that
differ only in ways unrelated to the \fBHeap::Elem\fR interface.
.SH "METHODS"
.IX Header "METHODS"
.ie n .IP "$heap = \fIHeapClass::new()\fR; $heap2\fR = \f(CW$heap1\fR\->\fInew();" 4
.el .IP "$heap = \fIHeapClass::new()\fR; \f(CW$heap2\fR = \f(CW$heap1\fR\->\fInew()\fR;" 4
.IX Item "$heap = HeapClass::new(); $heap2 = $heap1->new();"
Returns a new heap object of the specified (sub\-)class.
This is often used as a subroutine instead of a method,
of course.
.IP "$heap\->\s-1DESTROY\s0" 4
.IX Item "$heap->DESTROY"
Ensures that no internal circular data references remain.
Some variants of Heap ignore this (they have no such references).
Heap users normally need not worry about it, \s-1DESTROY\s0 is automatically
invoked when the heap reference goes out of scope.
.IP "$heap\->add($elem)" 4
.IX Item "$heap->add($elem)"
Add an element to the heap.
.ie n .IP "$elem = $heap\->top" 4
.el .IP "$elem = \f(CW$heap\fR\->top" 4
.IX Item "$elem = $heap->top"
Return the top element on the heap.  It is \fBnot\fR removed from
the heap but will remain at the top.  It will be the smallest
element on the heap (unless a reversed cmp function is being
used, in which case it will be the largest).  Returns \fIundef\fR
if the heap is empty.
.Sp
This method used to be called \*(L"minimum\*(R" instead of \*(L"top\*(R".  The
old name is still supported but is deprecated.  (It was confusing
to use the method \*(L"minimum\*(R" to get the maximum value on the heap
when a reversed cmp function was used for ordering elements.)
.ie n .IP "$elem = $heap\->extract_top" 4
.el .IP "$elem = \f(CW$heap\fR\->extract_top" 4
.IX Item "$elem = $heap->extract_top"
Delete the top element from the heap and return it.  Returns
\&\fIundef\fR if the heap was empty.
.Sp
This method used to be called \*(L"extract_minimum\*(R" instead of
\&\*(L"extract_top\*(R".  The old name is still supported but is deprecated.
(It was confusing to use the method \*(L"extract_minimum\*(R" to get the
maximum value on the heap when a reversed cmp function was used
for ordering elements.)
.IP "$heap1\->absorb($heap2)" 4
.IX Item "$heap1->absorb($heap2)"
Merge all of the elements from \fI$heap2\fR into \fI$heap1\fR.
This will leave \fI$heap2\fR empty.
.IP "$heap1\->decrease_key($elem)" 4
.IX Item "$heap1->decrease_key($elem)"
The element will be moved closed to the top of the
heap if it is now smaller than any higher parent elements.
The user must have changed the value of \fI$elem\fR before
\&\fIdecrease_key\fR is called.  Only a decrease is permitted.
(This is a decrease according to the \fIcmp\fR function \- if it
is a reversed order comparison, then you are only permitted
to increase the value of the element.  To be pedantic, you
may only use \fIdecrease_key\fR if
\&\fI$elem\-\fRcmp($elem_original) <= 0> if \fI$elem_original\fR were
an elem with the value that \fI$elem\fR had before it was
\&\fIdecreased\fR.)
.ie n .IP "$elem = $heap\->delete($elem)" 4
.el .IP "$elem = \f(CW$heap\fR\->delete($elem)" 4
.IX Item "$elem = $heap->delete($elem)"
The element is removed from the heap (whether it is at
the top or not).
.SH "AUTHOR"
.IX Header "AUTHOR"
John Macdonald, jmm@perlwolf.com
.SH "COPYRIGHT"
.IX Header "COPYRIGHT"
Copyright 1998\-2003, O'Reilly & Associates.
.PP
This code is distributed under the same copyright terms as perl itself.
.SH "SEE ALSO"
.IX Header "SEE ALSO"
\&\fIHeap::Elem\fR\|(3), \fIHeap::Binary\fR\|(3), \fIHeap::Binomial\fR\|(3), \fIHeap::Fibonacci\fR\|(3).