Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Priority queues (pairing heaps) in Erlang
% Copyright (c) 2010-2014, Lars Buitinck
% May be used, redistributed and modified under the terms of the
% GNU Lesser General Public License (LGPL), version 2.1 or later
% Heaps/priority queues in Erlang
% Heaps are data structures that return the entries inserted into them in
% sorted order. This makes them the data structure of choice for implementing
% priority queues, a central element of algorithms such as best-first/A*
% search and Kruskal's minimum-spanning-tree algorithm.
%
% This module implements min-heaps, meaning that items are retrieved in
% ascending order of key/priority.
%
% The current version implements pairing heaps. All operations except
% from_list/1, sort/1 and to_list/1 can be performed in at most O(lg n)
% amortized time.
%
% (The actual time complexity of pairing heaps is complicated and not yet
% determined conclusively; see, e.g. S. Pettie (2005), Towards a final
% analysis of pairing heaps, Proc. FOCS'05.)
%
% Ported from an earlier Prolog version, now available as part of SWI-Prolog,
% http://www.swi-prolog.org/pldoc/doc/swi/library/heaps.pl
-module(heaps).
-export([add/2, delete_min/1, from_list/1, empty/1, merge/2, new/0, min/1,
size/1, sort/1, to_list/1]).
-import(lists).
% Public interface: priority queues
% Add element X to priority queue
add(X, {prioq, Heap, N}) ->
{prioq, meld(Heap, {X, []}), N + 1}.
% Return new priority queue with minimum element removed
delete_min({prioq, {_, Sub}, N}) ->
{prioq, pair(Sub), N - 1}.
% Construct priority queue from list
from_list(L) ->
lists:foldl(fun(X, Q) -> add(X, Q) end, new(), L).
% True iff argument is an empty priority queue
empty({prioq, nil, 0}) -> true;
empty(_) -> false.
% Merge two priority queues
merge({prioq, Heap0, M}, {prioq, Heap1, N}) ->
{prioq, meld(Heap0, Heap1), M + N}.
% Get minimum element
min({prioq, Heap, _}) -> heap_min(Heap).
% Returns new, empty priority queue
new() -> {prioq, nil, 0}.
% Number of elements in queue
size({prioq, _, N}) -> N.
% Heap sort a list
sort(L) -> to_list(from_list(L)).
% List elements in priority queue in sorted order
to_list({prioq, nil, _}) -> [];
to_list(Q) ->
[min(Q) | to_list(delete_min(Q))].
% Guts: pairing heaps
% A pairing heap is either nil or a term {Item, SubHeaps}
% where SubHeaps is a list of heaps.
heap_min({X, _}) -> X.
meld(nil, Q) -> Q;
meld(Q, nil) -> Q;
meld(L = {X, SubL}, R = {Y, SubR}) ->
if
X < Y ->
{X, [R|SubL]};
true ->
{Y, [L|SubR]}
end.
% "Pair up" (recursively meld) a list of pairing heaps.
pair([]) -> nil;
pair([Q]) -> Q;
pair([Q0, Q1 | Qs]) ->
Q2 = meld(Q0, Q1),
meld(Q2, pair(Qs)).
@xmhbbovru

Using this I noticed delete_min runtime about linear in the size of the heap on randomly generated data. Comparing with http://www.cs.cmu.edu/afs/cs.cmu.edu/user/sleator/www/papers/pairing-heaps.pdf and http://en.wikipedia.org/wiki/Pairing_heap, I think the last line of pair should be meld(Q2, pair(Qs)) in order to get the (conjectured) amortized logarithmic runtime, and timings of the revised version supported this. It made a big difference for size 1000.

@larsmans
Owner

@xmhbbovru You're right, fixed it. I'll have to fix the version in SWI-Prolog as well.

@mxm

The -import(lists) compiler declarative is not necessary and also not a part of the language anymore since R16. Great job!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.