/ 
SkewHeap-PP-0.01
River stage zero No dependents
/ SkewHeap::PP

NAME

SkewHeap::PP - a fast and flexible heap structure

VERSION

version 0.01

SYNOPSIS

use SkewHeap::PP;

my $s = skew{ $_[0] <=> $_[1] };

# Add items one at a time
for (@items) {
  skew_put($s, $_);
}

# Or as a batch
skew_put($s, @items);

# Take individual items
my @taken;
until (skew_is_empty($s)) {
  say "Taking: " . skew_peek($s);

  push @taken, skew_take($s);

  say "Left in queue: " . skew_count($s);
}

# Or take a batch
my @take_ten = skew_take($s, 10);

# Destructively merge two heaps
skew_merge($s, $another_skew_heap);

# Non-destructively merge heaps
my $new_heap = skew_merge($a, $b, $c);

DESCRIPTION

A skew heap is a memory efficient, self-adjusting heap with an amortized performance of O(log n) or better. SkewHeap:PP is implemented in pure perl, yet performs comparably to SkewHeap.

The key feature of a skew heap is the ability to quickly and efficiently merge two heaps together.

skew

Creates a new skew heap. Requires a single argument, a code block that knows how to prioritize the values to be stored in the heap.

my $heap = skew{ $_[0] <=> $_[1] };

skew_count

Returns the number of elements in the heap.

skew_is_empty

Returns true if the heap is empty.

skew_peek

Returns the top element in the heap without removing it from the heap.

skew_take

Removes and returns the top element from the heap.

my $item = skew_take($heap);

Optionally, multiple elements may be returned from the heap by passing the desired number of elements, in which case a list is returned, rather than a single, scalar element. If there are fewer elements available than requested, as many as a immediately available are returned.

# Get 10 elements
my @items = skew_take($heap, 10);

skew_put

Adds one or more items to the heap.

skew_put($s, 42);
skew_put($s, 42, 6, 8);

skew_merge

Merges any number of heaps into the first argument destructively. After merging, the first heap passed in will contain all of the items in the heaps passed in subsequent arguments. After merging, the subsequent heaps will be empty. The comparison function used for ordering is that of the first heap passed in. The return value is the first heap into which the other heaps were merged.

skew_merge($x, $y, $z); # $x contains all elements of $x, $y, and $z;
                        # $y and $z are now empty.

skew_merge_safe

Non-destructively merges any number of heaps into a new heap whose comparison function will be that of the first heap in the list to merge. Returns a new heap containing all of the items in each of the other heaps. The other heaps' contents will remain intact.

skew_explain

Prints out a representation of the internal tree structure for debugging.

OBJECT INTERFACE

An object interface is provided that maps directly to the similarly named skew_* routines.

new - SEE "skew"
count - SEE "skew_count"
is_empty - SEE "skew_is_empty"
peek - SEE "skew_peek"
take - SEE "skew_take"
put - SEE "skew_put"
merge - SEE "skew_merge"
merge_safe - SEE "skew_merge_safe"
explain = SEE "skew_explain"

SEE ALSO

SkewHeap

Built with XS, SkewHeap is between 50-100% faster than SkewHeap::PP for heaps with 100,000 or fewer elements. For large heaps, that drops down to roughly 50% slower that the pure perl solution.

https://en.wikipedia.org/wiki/Skew_heap

AUTHOR

Jeff Ober <sysread@fastmail.fm>

COPYRIGHT AND LICENSE

This software is copyright (c) 2020 by Jeff Ober.

This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.