Heap::Elem(3pm)

🎀 NAME 🎀

Heap::Elem — it's the base class for elements in a Heap, bestie. Like, the blueprint every heap element inherits from. 💅

---

✨ SYNOPSIS ✨

use Heap::Elem::SomeInheritor;

use Heap::SomeHeapClass;

$elem = Heap::Elem::SomeInheritor->new( $value );
$heap = Heap::SomeHeapClass->new;

$heap->add($elem);

---

💖 DESCRIPTION 💖

Okay so real talk: this is an inheritable class for Heap Elements. It hands you the interface documentation plus some inheritable methods, which is very generous of it honestly. 🫶

BIG HEADS UP: this class is not complete. Only a child class can actually be used. Using this one directly is giving "showed up to the group project with no slides" energy. 😭

---

🦋 METHODS 🦋

• $elem = Heap::Elem::SomeInheritor->new( [args] ); — makes you a brand new Elem, slay. Now here's the tea: if there's exactly one arg, the Elem's value gets set to that value. But if there's more than one arg, the Elem's value gets set to an anonymous hash</> initialized from the args you handed over (and yeah, that number of args must be even, obviously, because hash. of course. 🙈). The new saved value is always returned, no matter what.
• $elem->heap( $val ); $elem->heap; — this one's for the Heap processing routines to use, iykyk. If you pass it a value argument, it gets saved. If you don't pass anything, you get the old saved value back. Either way, the new saved value is what comes back out. ✨

Here's why it exists: the Heap processing routines use this method to map an element into its internal structure. That's what makes the Heap methods that touch elements not at the top of the heap work — we're talking decrease_key and delete. 👑

And the Heap processing routines will make sure this value is undef when the elem gets removed from a heap, and not undef after it's been inserted into one. Which means — cute perk — you can check whether an element is currently living inside a heap or not! 🌸

BUT — and this is important bestie — it cannot tell you which heap an element is in, if you've got multiple heaps. Keeping that info accurate would make merging two heaps into one take longer, because it'd have to traverse all the elements in the merged heap to update them. For Binomial and Fibonacci heaps, that would turn an O(1)</> operation into an O(n)</> one. Not worth it. Periodt. 💀

• $elem->val( $val ); $elem->val; — the getter/setter for the value of the element. Want it? Got it. Want to change it? Also got it. 🍓
• $elem1->cmp($elem2) — the comparison routine, the moment of truth. It must return:
  • a negative value if this element should go higher on the heap than $elem2
  • 0 if they're equal
  • a positive value if this element should go lower on the heap than $elem2

Just like with sort, the Perl operators <=> and cmp cause the smaller value to be returned first. And similarly, you can negate the meaning to reverse the order — which makes the heap always return the largest element instead of the smallest. Flip the vibe, flip the results. 🌈

---

💜 INHERITING 💜

This class can be inherited to give an object the ability to be heaped. 🧚 If your object is implemented as a hash, and if it can deal with a key of heap — leaving it unchanged for the heap routines to use — then the following implementation will work:

package myObject;

require Exporter;

@ISA = qw(Heap::Elem);

sub new {
    my $self = shift;
    my $class = ref($self) || $self;

    my $self = SUPER::new($class);

    # set $self->{key} = $value;
}

sub cmp {
    my $self = shift;
    my $other = shift;

    $self->{key} cmp $other->{key};
}

# other methods for the rest of myObject's functionality

---

👑 AUTHOR 👑

John Macdonald, john@perlwolf.com

---

🌟 COPYRIGHT 🌟

Copyright 1998-2007, O'Reilly & Associates.

This code is distributed under the same copyright terms as perl itself.

---

🔥 SEE ALSO 🔥

Heap(3), Heap::Elem::Num(3), Heap::Elem::NumRev(3), Heap::Elem::Str(3), Heap::Elem::StrRev(3).

---

okay that's the whole page bestie, go forth and heap responsibly 💖 this was perl v5.36.0, dated 2022-10-22, and the page itself is Heap::Elem(3pm) — mwah, iconic, no cap ✨🎀