File Coverage

blib/lib/SkewHeap.pm
Criterion Covered Total %
statement 15 15 100.0
branch n/a
condition n/a
subroutine 5 5 100.0
pod n/a
total 20 20 100.0


line stmt bran cond sub pod time code
1             package SkewHeap;
2              
3             our $XS_VERSION = our $VERSION = '0.05';
4             $VERSION =~ tr/_//;
5              
6 3     3   583766 use strict;
  3         13  
  3         61  
7 3     3   11 use warnings;
  3         3  
  3         101  
8              
9             require XSLoader;
10             XSLoader::load('SkewHeap', $XS_VERSION);
11              
12 3     3   12 use Carp;
  3         4  
  3         109  
13 3     3   12 use Exporter;
  3         4  
  3         84  
14              
15 3     3   962 use parent 'Exporter';
  3         659  
  3         13  
16              
17             our @EXPORT = qw(skewheap);
18              
19             =head1 NAME
20              
21             SkewHeap - A fast and flexible heap structure
22              
23             =head1 SYNOPSIS
24              
25             use SkewHeap;
26              
27             my $heap = skewheap{ $a <=> $b };
28             $heap->put(42);
29             $heap->put(35);
30             $heap->put(200, 62);
31              
32             $heap->top; # 35
33             $heap->size; # 4
34              
35             $heap->take; # 35
36             $heap->take; # 42
37             $heap->take; # 62
38             $heap->take; # 200
39              
40             my $merged_heap = $heap->merge($other_skewheap);
41              
42             =head1 DESCRIPTION
43              
44             A skew heap is a memory efficient, self-adjusting heap (or priority queue) with
45             an amortized performance of O(log n) (or better). C is implemented in
46             C/C.
47              
48             The key feature of a skew heap is the ability to quickly and efficiently merge
49             two heaps together.
50              
51             =head1 METHODS
52              
53             =head2 skewheap
54              
55             Creates a new C which will be sorted in ascending order using the
56             comparison subroutine passed in. This sub has the same semantics as Perl's
57             C, returning -1 if C<$a E $b>, 1 if C<$a E $b>, or 0 if
58             C<$a == $b>.
59              
60             =head2 size
61              
62             Returns the number of elements in the heap.
63              
64             =head2 top
65              
66             Returns the next element which would be returned by L without removing
67             it from the heap.
68              
69             =head2 put
70              
71             Inserts one or more new elements into the heap.
72              
73             =head2 take
74              
75             Removes and returns the next element from the heap.
76              
77             =head2 merge
78              
79             Non-destructively merges two heaps into a new heap. Returns the new heap.
80              
81             =head1 AUTHOR
82              
83             Jeff Ober
84              
85             =head1 COPYRIGHT AND LICENSE
86              
87             This software is copyright (c) 2018 by Jeff Ober. This is free software; you
88             can redistribute it and/or modify it under the same terms as the Perl 5
89             programming language system itself.
90              
91             =cut
92              
93             1;