Heap::PQ — A Binary Heap (Priority Queue) Implementation for Perl

So What Is A Binary Heap?

A binary heap is really just an sorted array pretending to be a tree. Each element has a parent and children, but instead of pointers you find them with simple array indexes. The trick is that every parent follows one rule relative to its children, and that rule decides what kind of heap you get:

• Min heap - every parent is less than or equal to its children. The smallest element always lives at the root/top.
• Max heap - every parent is greater than or equal to its children. The largest element always lives at the root/top.

Because the tree is complete, the parent of element at index i sits at index floor((i−1)/2), and its children sit at 2i+1 and 2i+2. No pointers, no linked lists — just arithmetic on array indices. That cache friendly layout is one reason heaps are so fast in practice.

The key operations:

Operation	Time	What it does
push	O(log n)	Insert a value, then sift it up to restore order
pop	O(log n)	Remove the root, move the last element up, sift down
peek	O(1)	Read the root without removing it
make_heap	O(n)	Turn an existing unsorted array into a valid heap (make_heap_min / make_heap_max, new('min'), new('max'))

This makes a heap the natural backbone of a priority queue — a collection where you always want the next most important item and you need insertions to stay fast.

Why Heap::PQ?

Heap::PQ brings binary heaps to Perl as a C extension. Where a pure Perl heap tops out around 300 operations per second, Heap::PQ's functional interface clocks over 11,000 when pushing a 1000 random integers — and if you are just handling plain integers then there is an optimised NV heap implementation that squeezes out 50% more performance. It ships with three interfaces (object oriented, functional custom ops or a raw array) so you can trade readability for throughput depending on what your code needs.

Installation

cpanm Heap::PQ

Getting Started

Create a heap, push values in, and they come back out in priority order:

use Heap::PQ;

my $pq = Heap::PQ::new('min');

$pq->push(5);
$pq->push(1);
$pq->push(3);

print $pq->peek, "\n";  # 1 — the smallest value is always at the root

while (!$pq->is_empty) {
    print $pq->pop, "\n";  # 1, 3, 5
}

Switch to 'max' and the largest element comes out first instead.

Three Ways to Use It

OO Interface

The object oriented API is the clearest to read if you're a traditional perl developer that likes OO. push returns the heap so calls can be chained:

my $heap = Heap::PQ::new('min');
$heap->push(10)->push(20)->push(5);
$heap->push_all(8, 2, 15);

my $top = $heap->pop;    # 2
my $size = $heap->size;  # 5

Functional Interface

Import with 'import' and Heap::PQ installs heap_push, heap_pop, heap_peek, heap_size, and heap_is_empty as custom ops. Perl compiles them down to optimised opcodes so there is no method dispatch overhead at runtime:

use Heap::PQ 'import';

my $h = Heap::PQ::new('min');

heap_push($h, 42);
heap_push($h, 7);

my $val  = heap_pop($h);      # 7
my $size = heap_size($h);     # 1
my $top  = heap_peek($h);     # 42

This is the fastest path as stated functional custom ops removes the method->dispatch overhead.

Raw Array Interface

You can also operate directly on a Perl array. Import with 'raw' to get make_heap_min, push_heap_min, pop_heap_min (and their _max counterparts). This skips the object entirely but the functional interface is still faster thanks to custom op optimisation:

use Heap::PQ 'raw';

my @data = (9, 4, 7, 1, 3);
Heap::PQ::make_heap_min(\@data);  # O(n) heapify in place

my $min = Heap::PQ::pop_heap_min(\@data);   # 1
Heap::PQ::push_heap_min(\@data, 2);

No object, no opaque struct — just an array whose layout satisfies the heap property. Useful when you already have data in an array and want to avoid copying it.

Custom Comparators

By default the heap compares values numerically. Pass a code reference as a second argument to new and you can heap order anything — hash references, objects, strings:

my $tasks = Heap::PQ::new('min', sub {
    $a->{due} <=> $b->{due}
});

$tasks->push({ name => 'Write tests',  due => 3 });
$tasks->push({ name => 'Ship release', due => 5 });
$tasks->push({ name => 'Fix bug',      due => 1 });

while (!$tasks->is_empty) {
    my $t = $tasks->pop;
    print "$t->{name}\n";
}
# Fix bug
# Write tests
# Ship release

The comparator receives two elements in $a and $b — exactly like Perl's sort — and should return a negative, zero, or positive value. String ordering works the same way:

my $alpha = Heap::PQ::new('min', sub { $a cmp $b });
$alpha->push_all('banana', 'apple', 'cherry');
print $alpha->pop, "\n";  # apple

Key Path Comparators

When your heap contains hash references and you just want to compare by a numeric field, pass the field name as a string instead of a code reference. The comparison happens entirely in C — no Perl callback overhead at all:

my $tasks = Heap::PQ::new('min', 'priority');

$tasks->push({ name => 'Write tests',  priority => 3 });
$tasks->push({ name => 'Ship release', priority => 5 });
$tasks->push({ name => 'Fix bug',      priority => 1 });

while (!$tasks->is_empty) {
    my $t = $tasks->pop;
    print "$t->{name}\n";
}
# Fix bug
# Write tests
# Ship release

Dot separated paths reach into nested hashes:

my $heap = Heap::PQ::new('min', 'meta.score');
$heap->push({ id => 'a', meta => { score => 42 } });
$heap->push({ id => 'b', meta => { score => 17 } });
print $heap->pop->{id};  # 'b'

The key is extracted once when you push, so sift operations run at the same speed as a plain numeric heap. In benchmarks, key path heaps match the no-comparator path (~6,400/s) while custom Perl comparators top out around ~1,200/s — a 5× difference.

NV Heaps — Native Doubles, No SV Overhead

When every value is a number, new_nv stores them as raw C doubles instead of Perl scalars. That eliminates SV allocation and reference counting entirely:

my $h = Heap::PQ::new_nv('min');
$h->push_all(3.14, 2.71, 1.41, 1.73);
print $h->pop, "\n";  # 1.41

In benchmarks the NV heap runs roughly 1.5× faster than the functional interface for push heavy workloads, and nearly 57× faster than pure Perl.

Searching and Deleting

Both search and delete accept a callback that receives each element in $_. search returns matching elements; delete removes them and returns how many were dropped:

my $pq = Heap::PQ::new('min');
$pq->push_all(1, 5, 10, 15, 20, 25);

# Find all elements greater than 12
my @big = $pq->search(sub { $_ > 12 });
# @big = (15, 20, 25)

# Remove them from the heap
my $removed = $pq->delete(sub { $_ > 12 });
# $removed = 3, heap now contains (1, 5, 10)

After a delete, Heap::PQ rebuilds the heap in O(n) with Floyd's algorithm so the ordering invariant is always intact.

Peeking at the Top N

peek_n returns the top N elements in sorted order without removing them:

my $scores = Heap::PQ::new('max');
$scores->push_all(88, 95, 72, 99, 84, 91);

my @top3 = $scores->peek_n(3);  # (99, 95, 91)
# Heap is unchanged — still has all 6 elements

peek_n works with the heap's built-in numeric comparison, so it is best suited to plain numeric heaps. For heaps that use a custom comparator, pop and re-push to inspect the top N.

Putting It Together: An Event Scheduler

A priority queue is a natural fit for an event loop — push events with a timestamp, pop them in chronological order:

use Heap::PQ 'import';

my $scheduler = Heap::PQ::new('min', 'time'); # compare by the 'time' key in C

heap_push($scheduler, { time => 1712500800, action => 'start_server' });
heap_push($scheduler, { time => 1712497200, action => 'load_config' });
heap_push($scheduler, { time => 1712504400, action => 'open_connections' });
heap_push($scheduler, { time => 1712502600, action => 'warm_cache' });

while (!heap_is_empty($scheduler)) {
    my $event = heap_pop($scheduler);
    printf "t=%d  %s\n", $event->{time}, $event->{action};
}

# t=1712497200  load_config
# t=1712500800  start_server
# t=1712502600  warm_cache
# t=1712504400  open_connections

Benchmarks

All numbers below are from pushing 1,000 random integers then popping them all, measured with Benchmark:

Implementation	Rate	vs Pure Perl
Pure Perl	305/s	—
Custom comparator	1,194/s	4x
Array::Heap	6,087/s	20x
Heap::PQ OO key path	6,359/s	21x
Heap::PQ OO	6,685/s	22x
Heap::PQ raw	8,665/s	28x
Heap::PQ func	11,416/s	37x
Heap::PQ NV	16,747/s	55x

The custom op overhead reduction is clearly visible in the functional row, and the NV heap's custom op implementation plus avoidance of SV allocation pushes throughput higher still.

If you have any questions please do comment.

A Side note: I'm currently on look out for a new contract or permanent opportunity. If you know of any relevant openings, I'd appreciate hearing from you - [e-mail]