[ViewVC] Contents of: cvs/Array-Heap/README

NAME
    Array::Heap - treat perl arrays as binary heaps/priority queues

SYNOPSIS
     use Array::Heap;

DESCRIPTION
    There are a multitude of heap and heap-like modules on CPAN, you might
    want to search for /Heap/ and /Priority/ to find many. They implement
    more or less fancy datastructures that might well be what you are
    looking for.

    This module takes a different approach: It exports functions (i.e. no
    object orientation) that are loosely modeled after the C++ STL's binary
    heap functions. They all take an array as argument, just like perl's
    built-in functions "push", "pop" etc.

    The implementation itself is in C for maximum speed.

FUNCTIONS
    All of the following functions are being exported by default.

    make_heap @heap (\@)
        Reorders the elements in the array so they form a heap, with the
        lowest value "on top" of the heap (corresponding to the first array
        element).

    make_heap_idx @heap (\@)
        Just like "make_heap", but updates the index (see INDEXED
        OPERATIONS).

    make_heap_lex @heap (\@)
        Just like "make_heap", but in string comparison order instead of
        numerical comparison order.

    make_heap_cmp { compare } @heap (&\@)
        Just like "make_heap", but takes a custom comparison function.

    push_heap @heap, $element, ... (\@@)
        Adds the given element(s) to the heap.

    push_heap_idx @heap, $element, ... (\@@)
        Just like "push_heap", but updates the index (see INDEXED
        OPERATIONS).

    push_heap_lex @heap, $element, ... (\@@)
        Just like "push_heap", but in string comparison order instead of
        numerical comparison order.

    push_heap_cmp { compare } @heap, $element, ... (&\@@)
        Just like "push_heap", but takes a custom comparison function.

    pop_heap @heap (\@)
        Removes the topmost (lowest) heap element and repairs the heap.

    pop_heap_idx @heap (\@)
        Just like "pop_heap", but updates the index (see INDEXED
        OPERATIONS).

    pop_heap_lex @heap (\@)
        Just like "pop_heap", but in string comparison order instead of
        numerical comparison order.

    pop_heap_cmp { compare } @heap (&\@)
        Just like "pop_heap", but takes a custom comparison function.

    splice_heap @heap, $index (\@$)
        Similar to "pop_heap", but removes and returns the element at index
        $index.

    splice_heap_idx @heap, $index (\@$)
        Just like "splice_heap", but updates the index (see INDEXED
        OPERATIONS).

    splice_heap_lex @heap, $index (\@$)
        Just like "splice_heap", but in string comparison order instead of
        numerical comparison order.

    splice_heap_cmp { compare } @heap, $index (&\@$)
        Just like "splice_heap", but takes a custom comparison function.

    adjust_heap @heap, $index (\@$)
        Assuming you have only changed the element at index $index, repair
        the heap again. Can be used to remove elements, replace elements,
        adjust the priority of elements and more.

    adjust_heap_idx @heap, $index (\@$)
        Just like "adjust_heap", but updates the index (see INDEXED
        OPERATIONS).

    adjust_heap_lex @heap, $index (\@$)
        Just like "adjust_heap", but in string comparison order instead of
        numerical comparison order.

    adjust_heap_cmp { compare } @heap, $index (&\@$)
        Just like "adjust_heap", but takes a custom comparison function.

  COMPARISON FUNCTIONS
    All the functions come in two flavours: one that uses the built-in
    comparison function and one that uses a custom comparison function.

    The built-in comparison function can either compare scalar numerical
    values (string values for *_lex functions), or array refs. If the
    elements to compare are array refs, the first element of the array is
    used for comparison, i.e.

      1, 4, 6

    will be sorted according to their numerical value,

      [1 => $obj1], [2 => $obj2], [3 => $obj3]

    will sort according to the first element of the arrays, i.e. "1,2,3".

    The custom comparison functions work similar to how "sort" works: $a and
    $b are set to the elements to be compared, and the result should be
    greater than zero then $a is greater than $b, 0 otherwise. This means
    that you can use the same function as for sorting the array, but you
    could also use a simpler function that just does "$a > $b".

    The first example above corresponds to this comparison "function":

      { $a <=> $b }

    And the second example corresponds to this:

      { $a->[0] <=> $b->[0] }

    Unlike "sort", the default sort is numerical and it is not possible to
    use normal subroutines.

  INDEXED OPERATIONS
    The functions whose names end in "_idx" also "update the index". That
    means that all elements must be array refs, with the first element being
    the heap value, and the second value being the array index:

      [$value, $index, ...]

    This allows you to quickly locate an element in the array when all you
    have is the array reference.

BUGS
    *   Numerical comparison is always done using floatingpoint, which
        usually has less precision than a 64 bit integer that perl might use
        for integers internally, resulting in precision loss on the built-in
        comparison.

    *   This module does not work with tied or magical arrays or array
        elements, and, in fact, will even crash when you use those.

    *   This module can leak memory (or worse) when your comparison function
        exits unexpectedly (e.g. "last") or throws an exception, so do not
        do that.

SEE ALSO
    This module has a rather low-level interface. If it seems daunting, you
    should have a look at Array::Heap::ModifiablePriorityQueue, which is
    based on this module but provides more and higher-level operations with
    an object-oriented API which makes it harder to make mistakes.

    A slightly less flexible (only numeric weights), but also slightly
    faster variant of that module can be found as
    Array::Heap::PriorityQueue::Numeric on CPAN.

AUTHOR AND CONTACT INFORMATION
     Marc Lehmann <schmorp@schmorp.de>
     http://software.schmorp.de/pkg/Array-Heap

Revision:	1.6
Committed:	Tue Jul 14 23:45:10 2015 UTC (11 years, 2 months ago) by root
Branch:	MAIN
CVS Tags:	rel-3_22, rel-3_21, HEAD
Changes since 1.5:	+10 -0 lines
Log Message:	3.21
#	Content
1	NAME
2	Array::Heap - treat perl arrays as binary heaps/priority queues
3
4	SYNOPSIS
5	use Array::Heap;
6
7	DESCRIPTION
8	There are a multitude of heap and heap-like modules on CPAN, you might
9	want to search for /Heap/ and /Priority/ to find many. They implement
10	more or less fancy datastructures that might well be what you are
11	looking for.
12
13	This module takes a different approach: It exports functions (i.e. no
14	object orientation) that are loosely modeled after the C++ STL's binary
15	heap functions. They all take an array as argument, just like perl's
16	built-in functions "push", "pop" etc.
17
18	The implementation itself is in C for maximum speed.
19
20	FUNCTIONS
21	All of the following functions are being exported by default.
22
23	make_heap @heap (\@)
24	Reorders the elements in the array so they form a heap, with the
25	lowest value "on top" of the heap (corresponding to the first array
26	element).
27
28	make_heap_idx @heap (\@)
29	Just like "make_heap", but updates the index (see INDEXED
30	OPERATIONS).
31
32	make_heap_lex @heap (\@)
33	Just like "make_heap", but in string comparison order instead of
34	numerical comparison order.
35
36	make_heap_cmp { compare } @heap (&\@)
37	Just like "make_heap", but takes a custom comparison function.
38
39	push_heap @heap, $element, ... (\@@)
40	Adds the given element(s) to the heap.
41
42	push_heap_idx @heap, $element, ... (\@@)
43	Just like "push_heap", but updates the index (see INDEXED
44	OPERATIONS).
45
46	push_heap_lex @heap, $element, ... (\@@)
47	Just like "push_heap", but in string comparison order instead of
48	numerical comparison order.
49
50	push_heap_cmp { compare } @heap, $element, ... (&\@@)
51	Just like "push_heap", but takes a custom comparison function.
52
53	pop_heap @heap (\@)
54	Removes the topmost (lowest) heap element and repairs the heap.
55
56	pop_heap_idx @heap (\@)
57	Just like "pop_heap", but updates the index (see INDEXED
58	OPERATIONS).
59
60	pop_heap_lex @heap (\@)
61	Just like "pop_heap", but in string comparison order instead of
62	numerical comparison order.
63
64	pop_heap_cmp { compare } @heap (&\@)
65	Just like "pop_heap", but takes a custom comparison function.
66
67	splice_heap @heap, $index (\@$)
68	Similar to "pop_heap", but removes and returns the element at index
69	$index.
70
71	splice_heap_idx @heap, $index (\@$)
72	Just like "splice_heap", but updates the index (see INDEXED
73	OPERATIONS).
74
75	splice_heap_lex @heap, $index (\@$)
76	Just like "splice_heap", but in string comparison order instead of
77	numerical comparison order.
78
79	splice_heap_cmp { compare } @heap, $index (&\@$)
80	Just like "splice_heap", but takes a custom comparison function.
81
82	adjust_heap @heap, $index (\@$)
83	Assuming you have only changed the element at index $index, repair
84	the heap again. Can be used to remove elements, replace elements,
85	adjust the priority of elements and more.
86
87	adjust_heap_idx @heap, $index (\@$)
88	Just like "adjust_heap", but updates the index (see INDEXED
89	OPERATIONS).
90
91	adjust_heap_lex @heap, $index (\@$)
92	Just like "adjust_heap", but in string comparison order instead of
93	numerical comparison order.
94
95	adjust_heap_cmp { compare } @heap, $index (&\@$)
96	Just like "adjust_heap", but takes a custom comparison function.
97
98	COMPARISON FUNCTIONS
99	All the functions come in two flavours: one that uses the built-in
100	comparison function and one that uses a custom comparison function.
101
102	The built-in comparison function can either compare scalar numerical
103	values (string values for *_lex functions), or array refs. If the
104	elements to compare are array refs, the first element of the array is
105	used for comparison, i.e.
106
107	1, 4, 6
108
109	will be sorted according to their numerical value,
110
111	[1 => $obj1], [2 => $obj2], [3 => $obj3]
112
113	will sort according to the first element of the arrays, i.e. "1,2,3".
114
115	The custom comparison functions work similar to how "sort" works: $a and
116	$b are set to the elements to be compared, and the result should be
117	greater than zero then $a is greater than $b, 0 otherwise. This means
118	that you can use the same function as for sorting the array, but you
119	could also use a simpler function that just does "$a > $b".
120
121	The first example above corresponds to this comparison "function":
122
123	{ $a <=> $b }
124
125	And the second example corresponds to this:
126
127	{ $a->[0] <=> $b->[0] }
128
129	Unlike "sort", the default sort is numerical and it is not possible to
130	use normal subroutines.
131
132	INDEXED OPERATIONS
133	The functions whose names end in "_idx" also "update the index". That
134	means that all elements must be array refs, with the first element being
135	the heap value, and the second value being the array index:
136
137	[$value, $index, ...]
138
139	This allows you to quickly locate an element in the array when all you
140	have is the array reference.
141
142	BUGS
143	* Numerical comparison is always done using floatingpoint, which
144	usually has less precision than a 64 bit integer that perl might use
145	for integers internally, resulting in precision loss on the built-in
146	comparison.
147
148	* This module does not work with tied or magical arrays or array
149	elements, and, in fact, will even crash when you use those.
150
151	* This module can leak memory (or worse) when your comparison function
152	exits unexpectedly (e.g. "last") or throws an exception, so do not
153	do that.
154
155	SEE ALSO
156	This module has a rather low-level interface. If it seems daunting, you
157	should have a look at Array::Heap::ModifiablePriorityQueue, which is
158	based on this module but provides more and higher-level operations with
159	an object-oriented API which makes it harder to make mistakes.
160
161	A slightly less flexible (only numeric weights), but also slightly
162	faster variant of that module can be found as
163	Array::Heap::PriorityQueue::Numeric on CPAN.
164
165	AUTHOR AND CONTACT INFORMATION
166	Marc Lehmann <schmorp@schmorp.de>
167	http://software.schmorp.de/pkg/Array-Heap
168