File Coverage

blib/lib/SkewHeap.pm
Criterion Covered Total %
statement 9 9 100.0
branch n/a
condition n/a
subroutine 3 3 100.0
pod n/a
total 12 12 100.0


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