NAME
Heap::PQ - Binary heap (priority queue)
SYNOPSIS
use Heap::PQ 'import';
# Create a min-heap (smallest element at top)
my $min_heap = Heap::PQ::new('min');
# Create a max-heap (largest element at top)
my $max_heap = Heap::PQ::new('max');
# Push values - O(log n)
heap_push($min_heap, 5);
heap_push($min_heap, 3);
heap_push($min_heap, 7);
heap_push($min_heap, 1);
# Pop returns smallest (for min-heap) - O(log n)
print heap_pop($min_heap); # 1
print heap_pop($min_heap); # 3
print heap_pop($min_heap); # 5
print heap_pop($min_heap); # 7
# Peek without removing - O(1)
heap_push($min_heap, 10);
print heap_peek($min_heap); # 10
# Peek top N elements in order
my @top3 = heap_peek_n($min_heap, 3);
# Search for elements matching a condition
my @found = heap_search($min_heap, sub { $_ > 5 });
# Delete elements matching a condition
my $deleted = heap_delete($min_heap, sub { $_ > 8 });
# Utility methods - O(1)
my $size = heap_size($min_heap);
my $empty = heap_is_empty($min_heap);
my $type = heap_type($min_heap); # 'min' or 'max'
heap_clear($min_heap);
# Custom comparator for complex objects
my $heap = Heap::PQ::new('min', sub {
my ($a, $b) = @_;
return $a->{priority} <=> $b->{priority};
});
heap_push($heap, { name => 'low', priority => 10 });
heap_push($heap, { name => 'high', priority => 1 });
heap_push($heap, { name => 'medium', priority => 5 });
print heap_pop($heap)->{name}; # 'high'DESCRIPTION
Heap::PQ provides a binary heap implementation in C. A heap is a tree-based data structure that satisfies the heap property: in a min-heap, the parent is always smaller than its children; in a max-heap, the parent is always larger.
This makes heaps ideal for priority queues where you need efficient access to the minimum or maximum element.
Heap::PQ provides both a functional interface (with heap_push, heap_pop, etc.), an OO interface (with methods like push, pop, etc.) and a raw array interface (with push_heap_min, pop_heap_min, etc.). The functional and array interfaces uses custom ops for compile-time optimisation, while the OO interface provides a more traditional API using XSUBs. The decision was made with the OO interface to not optimise into Ops as you cannot identify the class at compile time so if I did it could lead to hijacking calls to other classes that have the same method names (Slowing those down).
METHODS
Heap::PQ::new($type, [$comparator])
Create a new heap.
my $min_heap = Heap::PQ->new('min'); # Min-heap
my $max_heap = Heap::PQ->new('max'); # Max-heap
my $custom = Heap::PQ->new('min', sub { ... }); # With comparatorParameters:
$type- Either'min'or'max'. Determines whether the smallest or largest element is at the top.$comparator- Optional. A code reference that takes two values and returns -1, 0, or 1 (like<=>). When provided, this is used instead of numeric comparison.
$heap->push($value)
Add an element to the heap. Returns the heap for method chaining.
$heap->push(42);
$heap->push($obj)->push($another); # Chaining$heap->push_all(@values)
Add multiple elements to the heap. Returns the heap for method chaining.
$heap->push_all(1, 2, 3, 4, 5);$heap->pop
Remove and return the top element (minimum for min-heap, maximum for max-heap). Returns undef if the heap is empty.
my $min = $min_heap->pop;$heap->peek
Return the top element without removing it. Returns undef if empty.
my $min = $min_heap->peek;$heap->peek_n($n)
Return the top $n elements in sorted order without removing them. Returns an empty list if the heap is empty or $n <= 0. If $n is greater than the heap size, returns all elements sorted.
my @top3 = $heap->peek_n(3);
my @top5 = $nv_heap->peek_n(5);$heap->size
Returns the number of elements in the heap.
$heap->is_empty
Returns true if the heap has no elements.
$heap->clear
Remove all elements from the heap.
$heap->type
Returns the heap type as a string: 'min' or 'max'.
$heap->search(sub { ... })
Search the heap for elements matching a condition. Sets $_ and passes the element as the first argument to the callback. Returns a list of matching elements. Does not modify the heap.
my @big = $heap->search(sub { $_ > 100 });
my @urgent = $task_heap->search(sub { $_->{priority} < 3 });$heap->delete(sub { ... })
Remove all elements matching a condition from the heap. Sets $_ and passes the element as the first argument to the callback. Rebuilds the heap after deletion using Floyd's algorithm. Returns the number of deleted elements.
my $count = $heap->delete(sub { $_ > 100 });
my $removed = $task_heap->delete(sub { $_->{done} });CUSTOM COMPARATORS
For objects or complex sorting, provide a comparator function:
# Sort by 'score' field, highest first (max-heap behavior)
my $leaderboard = Heap::PQ::new('max', sub {
my ($a, $b) = @_;
return $a->{score} <=> $b->{score};
});
# Sort by string field
my $alpha_heap = Heap::PQ::new('min', sub {
my ($a, $b) = @_;
return $a->{name} cmp $b->{name};
});The comparator should return:
-1if$ashould come before$b0if they are equal1if$bshould come before$a
FUNCTIONAL INTERFACE
Import functional ops with use Heap::PQ 'import':
use Heap::PQ 'import';
my $h = Heap::PQ::new('min');
heap_push($h, 5);
heap_push($h, 3);
heap_push($h, 1);
my $size = heap_size($h); # 3
my $top = heap_peek($h); # 1
my $val = heap_pop($h); # 1These functions use custom ops for compile time optimisation.
heap_push($heap, $value)
Push a value onto the heap. Same as $heap->push($value).
heap_pop($heap)
Pop and return the top value. Same as $heap->pop.
heap_peek($heap)
Return the top value without removing. Same as $heap->peek.
heap_size($heap)
Return the heap size. Same as $heap->size.
heap_peek_n($heap, $n)
Return the top $n elements in sorted order without removing. Same as $heap->peek_n($n).
heap_search($heap, sub { ... })
Search the heap for matching elements. Same as $heap->search(sub { ... }).
heap_delete($heap, sub { ... })
Delete matching elements from the heap. Same as $heap->delete(sub { ... }).
heap_is_empty($heap)
Return true if the heap has no elements. Same as $heap->is_empty.
heap_clear($heap)
Remove all elements from the heap. Same as $heap->clear.
heap_type($heap)
Return the heap type as 'min' or 'max'. Same as $heap->type.
NUMERIC HEAP
For numeric-only data, new_nv creates a heap that stores native doubles directly, avoiding SV overhead:
my $h = Heap::PQ::new_nv('min');
$h->push(3.14);
$h->push(2.71);
$h->push(1.41);
print $h->pop; # 1.41
print $h->pop; # 2.71Methods: push, push_all, pop, peek, peek_n, search, delete, size, is_empty, clear.
RAW ARRAY API
For maximum performance, operate directly on Perl arrays. Import with use Heap::PQ 'raw':
use Heap::PQ 'raw';
my @arr = (5, 3, 7, 1, 4);
# Convert array to heap in O(n)
Heap::PQ::make_heap_min(\@arr);
Heap::PQ::make_heap_max(\@arr);
# Push/pop operations
Heap::PQ::push_heap_min(\@arr, 2);
my $min = Heap::PQ::pop_heap_min(\@arr);
Heap::PQ::push_heap_max(\@arr, 8);
my $max = Heap::PQ::pop_heap_max(\@arr);Heap::PQ::make_heap_min(\@array)
Convert an array into a min-heap in O(n) time.
Heap::PQ::make_heap_max(\@array)
Convert an array into a max-heap in O(n) time.
Heap::PQ::push_heap_min(\@array, $value)
Push a value onto a min-heap array.
Heap::PQ::pop_heap_min(\@array)
Pop and return the minimum from a min-heap array.
Heap::PQ::push_heap_max(\@array, $value)
Push a value onto a max-heap array.
Heap::PQ::pop_heap_max(\@array)
Pop and return the maximum from a max-heap array.
EXAMPLES
Simple Priority Queue
use Heap::PQ;
my $pq = Heap::PQ::new('min');
$pq->push(5);
$pq->push(1);
$pq->push(3);
while (!$pq->is_empty) {
print $pq->pop, "\n"; # Prints: 1, 3, 5
}Task Scheduler
use Heap::PQ 'import';
my $tasks = Heap::PQ::new('min', sub {
$_[0]->{due} <=> $_[1]->{due}
});
heap_push($tasks, { name => 'Report', due => 1706745600 });
heap_push($tasks, { name => 'Meeting', due => 1706659200 });
heap_push($tasks, { name => 'Review', due => 1706832000 });
# Process tasks in order of due date
while (!heap_is_empty($tasks)) {
my $task = heap_pop($tasks);
print "Do: $task->{name}\n";
}Finding K Largest Elements
use Heap::PQ 'raw';
my @numbers = (3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5);
my $k = 3;
# Use min-heap of size k
my @heap;
for my $n (@numbers) {
push_heap_min(\@heap, $n);
if (@heap > $k) {
pop_heap_min(\@heap); # Remove smallest
}
}
# Heap now contains k largest
my @largest;
while (@heap) {
push @largest, pop_heap_min(\@heap);
}
print "@largest\n"; # 5 6 9BENCHMARK
Test: Push 1000 random integers
----------------------------------------
Rate Pure Perl Array::Heap Heap::PQ OO Heap::PQ raw Heap::PQ func Heap::PQ NV
Pure Perl 1580/s -- -88% -90% -91% -93% -96%
Array::Heap 13273/s 740% -- -14% -28% -44% -70%
Heap::PQ OO 15386/s 874% 16% -- -16% -35% -66%
Heap::PQ raw 18352/s 1062% 38% 19% -- -22% -59%
Heap::PQ func 23640/s 1396% 78% 54% 29% -- -47%
Heap::PQ NV 44671/s 2728% 237% 190% 143% 89% --
Test: Push 1000 then pop all (heapsort)
----------------------------------------
Rate Pure Perl Array::Heap Heap::PQ OO Heap::PQ raw Heap::PQ func Heap::PQ NV
Pure Perl 288/s -- -95% -96% -97% -97% -98%
Array::Heap 6217/s 2060% -- -5% -29% -46% -64%
Heap::PQ OO 6543/s 2173% 5% -- -25% -43% -62%
Heap::PQ raw 8715/s 2928% 40% 33% -- -24% -49%
Heap::PQ func 11441/s 3875% 84% 75% 31% -- -33%
Heap::PQ NV 17148/s 5858% 176% 162% 97% 50% --
Test: Bulk insert 1000 items (push_all / make_heap)
----------------------------------------
Rate Pure Perl Array::Heap make Heap::PQ push_all Heap::PQ make_min
Pure Perl 1584/s -- -96% -97% -97%
Array::Heap make 41296/s 2506% -- -9% -33%
Heap::PQ push_all 45347/s 2762% 10% -- -27%
Heap::PQ make_min 61836/s 3803% 50% 36% --
Test: Peek 10000 times on pre-built heap of 1000
----------------------------------------
Rate Pure Perl Heap::PQ OO Array::Heap Heap::PQ func
Pure Perl 2103/s -- -37% -65% -77%
Heap::PQ OO 3330/s 58% -- -45% -64%
Array::Heap 6019/s 186% 81% -- -34%
Heap::PQ func 9130/s 334% 174% 52% --
Test: Mixed push/pop (priority queue simulation, 500 rounds)
----------------------------------------
Rate Pure Perl Array::Heap Heap::PQ OO Heap::PQ func
Pure Perl 428/s -- -95% -96% -97%
Array::Heap 8184/s 1813% -- -17% -46%
Heap::PQ OO 9817/s 2194% 20% -- -36%
Heap::PQ func 15244/s 3463% 86% 55% --AUTHOR
LNATION <email@lnation.org>
LICENSE
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.