Module pqueue2

Skew Heap Priority Queue.

Ulf Wiger suggested pursuing a skew heap as an optimal Erlang priority queue implementation.

Copyright © 2011-2020 Michael Truog

Version: 2.0.1 Nov 26 2020 14:55:32 ------------------------------------------------------------------------

Authors: Michael Truog (mjtruog at protonmail dot com).

Description

Skew Heap Priority Queue.

Ulf Wiger suggested pursuing a skew heap as an optimal Erlang priority queue implementation. Unfortunately, testing has shown this solution to be more than 2 times slower than pqueue.

Data Types

pqueue2()

pqueue2() = empty | {integer(), pqueue2(), pqueue2(), element, term()} | {integer(), pqueue2(), pqueue2(), queue, queue:queue()}

Function Index

in/2

Append an item to the tail of the 0 priority queue.

.
in/3

Append an item to the tail of a specific priority queue.

.
is_empty/1

Check if the priority queue is empty.

.
is_queue/1

Check if the priority queue type is as expected.

.
len/1

Determine the length of a priority queue.

.
new/0

Create a new priority queue.

.
out/1

Take an item from the head of the priority queue.

.
out/2

Take an item of a specific priority from the head of the queue.

.
pout/1

Take an item from the head of the priority queue.

Includes the priority in the return value.
test/0

Regression test.

.
to_list/1

Convert the priority queue to a list.

.

Function Details

in/2

in(Value::term(), H::pqueue2()) -> pqueue2()

Append an item to the tail of the 0 priority queue.

in/3

in(Value::term(), P::integer(), H::pqueue2()) -> pqueue2()

Append an item to the tail of a specific priority queue.

is_empty/1

is_empty(X1::pqueue2()) -> true | false

Check if the priority queue is empty.

is_queue/1

is_queue(X1::pqueue2()) -> true | false

Check if the priority queue type is as expected.

len/1

len(H::pqueue2()) -> non_neg_integer()

Determine the length of a priority queue.

new/0

new() -> pqueue2()

Create a new priority queue.

out/1

out(X1::pqueue2()) -> {{value, term()}, pqueue2()} | {empty, pqueue2()}

Take an item from the head of the priority queue.

out/2

out(P::integer(), H::pqueue2()) -> {{value, term()}, pqueue2()} | {empty, pqueue2()}

Take an item of a specific priority from the head of the queue.

pout/1

pout(X1::pqueue2()) -> {{value, term(), integer()}, pqueue2()} | {empty, pqueue2()}

Take an item from the head of the priority queue.

Includes the priority in the return value.

test/0

test() -> any()

Regression test.

to_list/1

to_list(H::pqueue2()) -> [term()]

Convert the priority queue to a list.


Generated by EDoc