This class implements a priority queue data structure.


use v6;

constant $VERSION = '0.01';

# XXX can I make this parameterized?
#| A priority queue implementation. Z<Implemented as a binary heap>
class PriorityQueue:auth<github:hoelzro>:ver<0.1.0> {
    has @!elements; # XXX should be @!elements{1..*}
    has &!cmp;

    #| Constructor.  You can specify a custom comparator via
    #| C<:cmp>; it should be a code object that returns True
    #| if its first argument should appear before its second
    #| when shifting items off of the queue.  If you provide
    #| a unary function, C<&cmp($a) before &cmp($b)> will be
    #| used.
    submethod BUILD(:&!cmp = &[before]) {
        # pad the array so that our starting index is
        # 1; makes our calculations a bit easier
        @!elements.push: Any;

        if &!cmp.count == 1 {
            my $cmp = &!cmp;
            &!cmp = -> $a, $b {
                $cmp($a) before $cmp($b)
            };
        }
    }

    #| Adds an element to the queue.
    method push($element) {
        @!elements.push: $element;

        my int $index = @!elements.end;

        while $index > 1 {
            my int $parent-index = $index div 2;
            my $parent           = @!elements[$parent-index];

            last unless &!cmp($element, $parent);

            @!elements[$index]        = $parent;
            @!elements[$parent-index] = $element;

            $index = $parent-index;
        }
    }

    #| Removes the next element from the queue.
    method shift {
        return unless @!elements > 1;
        return @!elements.pop if @!elements == 2;

        my $result    = @!elements[1];
        @!elements[1] = @!elements.pop;

        my int $index   = 1;
        my int $end     = @!elements.end;
        my int $halfway = $end div 2;

        while $index <= $halfway {
            my $left-index  = $index * 2;
            my $right-index = $left-index + 1;

            my $swap-index = [$index, $left-index, $right-index].grep(* <= $end).min: {
                &!cmp(@!elements[$^a], @!elements[$^b]) ?? Order::Less !! Order::More
            };
            last if $index == $swap-index;

            @!elements[$index, $swap-index] = @!elements[$swap-index, $index];

            $index = $swap-index;
        }
        $result
    }
}



NAME

VERSION

for 1 .. 100 {
        $p.push: 100.rand.floor;
    }


# should return in increasing order
    while $p.shift -> $e {
        say $e;
    }


# if you want a max heap, or just a different ordering:
    $p = PriorityQueue.new(:cmp(&infix:«>=»));


SYNOPSIS

DESCRIPTION

AUTHOR

root

README

React

=begin React :component<HeaderCol> :id<menu> 
=para L<Documentation|/doc/introduction>
=para L<Modules| /mods>
=para L<Examples| file:../examples/index.podlite>
=para L<Download |file:../download/index.podlite>
=para L<About|file:../about/index.podlite>
=para 🔍 K<⌘K>/K<ctrl-K>
=end React


=begin React :component<HeaderCol> :id<footer>  
=begin nested :!nested
=item1 B<Language>
    =item2 L<Get started|file:../getting-started/getting-started.podlite>
    =item2 L<Why Raku?|/doc/language/faq#Why-should-I-learn-Raku-What's-so-great-about-it>
    =item2 L<Try Raku|https://glot.io/new/raku>
    =item2 L<Raku cheat sheet|https://github.com/Raku/mu/blob/master/docs/Perl6/Cheatsheet/cheatsheet.txt>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<Raku on Exercism|https://exercism.org/tracks/raku>
    =item2 L<Wikipedia|https://en.wikipedia.org/wiki/Raku_(programming_language)>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=end nested
=begin nested :!nested

=item1 B<L<Documentation|/doc>>
    =item2 L<Getting started, Migration guides from other languages, & Tutorials | file:../doc/introduction.podlite>
    =item2 L<Language References|file:../doc/reference.podlite>
    =item2 L<Type Reference| file:../doc/types.podlite>
    =item2 L<Miscellaneous| file:../doc/miscellaneous.podlite>
    =item2 L<FAQs (Frequently Asked Questions)|/doc/language/faq>
    =item2 L<Community|/doc/language/community>
    =item2 L<The list of all documents|file:../doc/index.podlite>

=item1 B<Resources>
    =item2 L<The Raku Guide|https://raku.guide/>
    =item2 L<Books |https://perl6book.com/>
    =item2 L<Rosetta Code | https://www.raku.org/community/rosettacode>

=end nested
=begin nested :!nested

=item1 B<Resoures>
    =item2 L<Download | file:../download/index.podlite>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=item1 B<Learning>
    =item2 L<The Raku Guide|https://raku.guide/>
    =item2 L<Wikibook |https://en.wikibooks.org/wiki/Raku_Programming>
    =item2 L<Books |https://perl6book.com/>
    =item2 L<Rosetta Code | https://www.raku.org/community/rosettacode>
    =item2 L<Learn Raku in Y minutes|https://learnxinyminutes.com/docs/raku/>
    =item2 L<Golfing |https://github.com/AlexDaniel/raku-golf-cheatsheet>
=end nested
=begin nested :!nested

=item1 B<Explore>
    =item2 L<Raku Blog Aggregator|https://planet.raku.org/>
    =item2 L<Rakudo Weekly|https://rakudoweekly.blog/>
    =item2 L<The Weekly Challenge |https://perlweeklychallenge.org/>
    =item2 L<Raku Advent Calendar|https://raku-advent.blog/>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=end nested
=end React


=begin React :component<CookieConsent> :id<CookieConsent> :buttonCaption("Got it!")
=para
This website uses cookies for analytics.
=end React
