Algorithm-Heapify-XS
view release on metacpan or search on metacpan
use Algorithm::Heapify::XS qw(max_heapify max_heap_shift);
my @array= (1..10);
max_heapify(@array);
while (defined(my $top= max_heap_shift(@array))) {
print $top;
}
DESCRIPTION
A heap is an array based data structure where the array is treated as a
balanced tree of items where each item obeys a given inequality
constraint with its parent and children, but not with its siblings. This
allows it to be put into "nearly" sorted order more efficiently than an
actual sort would.
This data structure has a number of nice properties:
a) the tree does not require "child" pointers, but instead infers
parent/child relationships from their position in the array. The parent
of a node i is defined to reside in position int((i-1)/2), and the left
and right children of a node i reside in position (i*2+1) and (i*2+2)
respectively.
b) "heapifying" an array is O(N) as compared to N * log2(N) for a
typical sort.
c) Accessing the top item is O(1), and removing it from the array is
O(log(N)).
$max= max_heap_adjust_item(@array,$idx)
$min= min_heap_adjust_item(@array,$idx)
$maxstr= maxstr_heap_adjust_item(@array,$idx)
$minstr= minstr_heap_adjust_item(@array,$idx)
If the weight of a specific item in a heapified array has changed,
this function will adjust its position in the tree, and return the
resulting new "top" (min/max) value. If $idx is outside the array
does nothing.
$idx= heap_parent_idx($idx)
Returns the defined location for the node residing at index $idx in
a heap, or undef if the $idx is 0.
$idx= heap_left_child_idx($idx)
$idx= heap_right_child_idx($idx)
Returns the defined location for the children of a node residing at
index $idx in a heap.
VERSION
This is version 0.04
#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"
#include "ppport.h"
#define iParent(i) (((i)-1) / 2)
#define iLeftChild(i) ((2*(i)) + 1)
#define iRightChild(i) ((2*(i)) + 2)
#define OUT_OF_ORDER(a,tmpsv,child_is_magic,parent_is_magic,child,parent,is_min) \
( ( ( (child_is_magic) || (parent_is_magic) ) \
? (((tmpsv) = amagic_call((a)[(child)], (a)[(parent)], is_min & 2 ? sgt_amg : gt_amg, 0)) && SvTRUE((tmpsv))) \
: ( ((is_min & 2) ? Perl_sv_cmp(aTHX_ (a)[(child)], a[(parent)]) \
: Perl_do_ncmp(aTHX_ (a)[(child)], a[(parent)])) > 0) )\
? !(is_min & 1) : (is_min & 1) )
I32 sift_up(pTHX_ SV **a, ssize_t start, ssize_t end, I32 is_min) {
/*start represents the limit of how far up the heap to sift.
end is the node to sift up. */
ssize_t child = end;
SV *tmpsv = NULL;
I32 child_is_magic;
I32 swapped = 0;
SvGETMAGIC(a[child]);
child_is_magic= SvAMAGIC(a[child]);
while (child > start) {
ssize_t parent = iParent(child);
I32 parent_is_magic;
SvGETMAGIC(a[parent]);
parent_is_magic= SvAMAGIC(a[parent]);
if ( OUT_OF_ORDER(a,tmpsv,child_is_magic,parent_is_magic,child,parent,is_min) ) {
SV *swap_tmp= a[parent];
a[parent]= a[child];
a[child]= swap_tmp;
child = parent; /* repeat to continue sifting up the parent now */
child_is_magic= parent_is_magic;
swapped++;
}
else {
return swapped;
}
}
return swapped;
}
/*Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid*/
/*sift up the node at index end to the proper place such that all nodes above
the end index are in heap order */
(void)sift_up(aTHX_ a, 0, end, is_min);
end++;
}
/* after sifting up the last node all nodes are in heap order */
}
/* this is O(N) */
void heapify_with_sift_down(pTHX_ SV **a, ssize_t count, I32 is_min) {
/*start is assigned the index in 'a' of the last parent node
the last element in a 0-based array is at index count-1; find the parent of that element */
ssize_t start = iParent(count-1);
while (start >= 0) {
/* sift down the node at index 'start' to the proper place such that all nodes below
the start index are in heap order */
(void)sift_down(aTHX_ a, start, count - 1, is_min);
/* go to the next parent node */
start--;
}
/* after sifting down the root all nodes/elements are in heap order */
}
#define FORCE_SCALAR(fakeop) \
STMT_START { \
SAVEOP(); \
Copy(PL_op, &fakeop, 1, OP); \
fakeop.op_flags = OPf_WANT_SCALAR; \
lib/Algorithm/Heapify/XS.pm view on Meta::CPAN
require Exporter;
our @ISA = qw(Exporter);
# This allows declaration:
# use Algorithm::Heapify::XS ':all';
our %EXPORT_TAGS = (
'all' => [
'heap_parent_idx',
'heap_left_child_idx',
'heap_right_child_idx',
map { ("min_$_", "max_$_","minstr_$_","maxstr_$_") }
(
'heapify',
'heap_shift',
'heap_push',
'heap_adjust_top',
'heap_adjust_item',
)
lib/Algorithm/Heapify/XS.pm view on Meta::CPAN
}
$EXPORT_TAGS{idx}= [ grep { /_idx\z/ } @EXPORT_OK ];
our @EXPORT = qw();
our $VERSION = '0.04';
require XSLoader;
XSLoader::load('Algorithm::Heapify::XS', $VERSION);
sub heap_parent_idx($) {
die "index must be non-negative" if $_[0] < 0;
return $_[0] ? int(($_[0] - 1) / 2) : undef;
}
sub heap_left_child_idx($) {
die "index must be non-negative" if $_[0] < 0;
return 2*$_[0]+1;
}
sub heap_right_child_idx($) {
lib/Algorithm/Heapify/XS.pm view on Meta::CPAN
my @array= (1..10);
max_heapify(@array);
while (defined(my $top= max_heap_shift(@array))) {
print $top;
}
=head1 DESCRIPTION
A heap is an array based data structure where the array is treated as a balanced tree
of items where each item obeys a given inequality constraint with its parent and children,
but not with its siblings. This allows it to be put into "nearly" sorted order more
efficiently than an actual sort would.
This data structure has a number of nice properties:
a) the tree does not require "child" pointers, but instead infers parent/child
relationships from their position in the array. The parent of a node i is defined to
reside in position int((i-1)/2), and the left and right children of a node i reside in
position (i*2+1) and (i*2+2) respectively.
b) "heapifying" an array is O(N) as compared to N * log2(N) for a typical sort.
c) Accessing the top item is O(1), and removing it from the array is O(log(N)).
d) Inserting a new item into the heap is O(log(N))
This means that for applications that need find only the top K of an array can do it faster
lib/Algorithm/Heapify/XS.pm view on Meta::CPAN
=item $min= min_heap_adjust_item(@array,$idx)
=item $maxstr= maxstr_heap_adjust_item(@array,$idx)
=item $minstr= minstr_heap_adjust_item(@array,$idx)
If the weight of a specific item in a heapified array has changed, this function will
adjust its position in the tree, and return the resulting new "top" (min/max) value.
If $idx is outside the array does nothing.
=item $idx= heap_parent_idx($idx)
Returns the defined location for the node residing at index $idx in a heap, or undef if the $idx is 0.
=item $idx= heap_left_child_idx($idx)
=item $idx= heap_right_child_idx($idx)
Returns the defined location for the children of a node residing at index $idx in a heap.
=back
( run in 0.239 second using v1.01-cache-2.11-cpan-4d50c553e7e )