# [erlang-questions] How can I implement a priority queue with Erlang?

Jeffrey Chen bitcowboy@REDACTED
Thu Aug 30 14:33:31 CEST 2007

```I'm trying to implement a priority queue using heap struct. But I
can't do that efficient. Can anybody help me? I'll post my code below.
Thanks.

CODE:
exchange([], _, _, _, _, _) ->
[];
exchange([_ | Rest], IndexA, ValueA, IndexB, ValueB, Index) when
IndexA == Index ->
[ValueB | exchange(Rest, IndexA, ValueA, IndexB, ValueB, Index + 1)];
exchange([_ | Rest], IndexA, ValueA, IndexB, ValueB, Index) when
IndexB == Index ->
[ValueA | exchange(Rest, IndexA, ValueA, IndexB, ValueB, Index + 1)];
exchange([Head | Rest], IndexA, ValueA, IndexB, ValueB, Index) ->
[Head | exchange(Rest, IndexA, ValueA, IndexB, ValueB, Index + 1)].

%%% Heap %%%

max_heapify(Heap, Index) when Index * 2 > length(Heap) ->
Heap;
max_heapify(Heap, Index) ->
IndexValue = lists:nth(Index, Heap),

LeftIndex  = 2 * Index,
LeftValue  = lists:nth(LeftIndex, Heap),

if
2 * Index + 1 > length(Heap) ->
RightIndex = LeftIndex,
RightValue = LeftValue;
true ->
RightIndex = 2 * Index + 1,
RightValue = lists:nth(RightIndex, Heap)
end,

if
LeftValue > IndexValue, LeftValue >= RightValue ->
LargestIndex = LeftIndex,
LargestValue = LeftValue;
RightValue > IndexValue, RightValue >= LeftValue ->
LargestIndex = RightIndex,
LargestValue = RightValue;
true ->
LargestIndex = Index,
LargestValue = IndexValue
end,

if
LargestIndex /= Index ->
NewHeap = exchange(Heap, Index, IndexValue, LargestIndex,
LargestValue, 1),
max_heapify(NewHeap, LargestIndex);
true ->
Heap
end.

build_heap(L, 0) ->
L;
build_heap(L, Index) ->
NewL = max_heapify(L, Index),
build_heap(NewL, Index - 1).

make_heap([]) ->
[];
make_heap(L) ->
build_heap(L, trunc(length(L) / 2)).

heap_pop([Head | Rest]) when  length(Rest) == 0 ->
{Head, []};
heap_pop([Head | Rest]) ->
{RestBody, RestTail} = lists:split(length(Rest) - 1, Rest),
{Head, max_heapify(RestTail ++ RestBody, 1)}.

test_heap_pop([]) ->
done;
test_heap_pop(Heap) ->
{P, H} = heap_pop(Heap),
io:format("~w, ~w~n", [P, H]),
test_heap_pop(H).

adjust_heap_node(Heap, Index) when trunc(Index / 2) == 0 ->
Heap;
adjust_heap_node(Heap, Index) ->
IndexValue = lists:nth(Index, Heap),
ParentIndex = trunc(Index / 2),
ParentValue = lists:nth(ParentIndex, Heap),

if
IndexValue > ParentValue ->
NewHeap = exchange(Heap, Index, IndexValue, ParentIndex,
ParentValue, 1),
adjust_heap_node(NewHeap, ParentIndex);
true ->
Heap
end.

heap_push(Heap, Push) ->
adjust_heap_node(Heap ++ [Push], length(Heap) + 1).

--
Victory won't come to me, unless I go to it.

```

More information about the erlang-questions mailing list