priority_queue v1.0.0 PairingHeap

Pairing Heap implementation see:

http://en.wikipedia.org/wiki/Pairing_heap

A Pairing Heap is a type of heap structure with relatively simple implementation and excellent practical amortised performance.

Determining the precise asymptotic running time of pairing heaps has proved difficult, see the Wikipedia page referenced above for a more complete discussion. In particular practical performance of decrease-key is excellent (and initially conjectured to be O(1)), but at present it’s known to be “no worse” then O(log n). However, no tight bound is known.

Operation find-min: Θ(1) delete-min: Θ(log n) insert: Θ(1) decrease-key: Θ(log n) - however, tight bound not known merge: Θ(1)

Guts: pairing heaps A pairing heap is either nil or a term {key, value, [sub_heaps]} where sub_heaps is a list of heaps.

TODO: Allow the comparison function to be specified

  Implement decrease_key

Summary

Types

element()

key()

t()

value()

Functions

delete_min(arg1)

return the heap with the min item removed

empty?(arg1)

True iff argument is an empty priority queue

meld(heap, heap)

Merge (meld) two heaps

merge(h1, h2)

Merge (meld) two heaps

min(heap, default \\ {nil, nil})

min item in the heap

new()

Create new empty heap. Optionally pass in initial key, value

new(key, value)

pop(heap, default \\ {nil, nil})

Returns the min item, as well as the heap without the min item Equivalent to: {min(heap), delete_min(heap)}

put(heap, key, value)

Add element X to priority queue

Types

element :: {key, value}

key :: any

t :: {key, value, list} | nil

value :: any

Functions

delete_min(arg1)

Specs

delete_min(t) :: t

return the heap with the min item removed

iex> PairingHeap.new(1, "first") |> PairingHeap.delete_min |> PairingHeap.empty?
true

iex> PairingHeap.new(1, "first") |> PairingHeap.delete_min |> PairingHeap.delete_min |> PairingHeap.empty?
true

empty?(arg1)

Specs

empty?(t) :: boolean

True iff argument is an empty priority queue

iex> PairingHeap.new |> PairingHeap.empty?
true

iex> PairingHeap.new(1, "first") |> PairingHeap.empty?
false

iex> PairingHeap.new(1, "first") |> PairingHeap.delete_min |> PairingHeap.empty?
true

meld(heap, heap)

Specs

meld(t, t) :: t

Merge (meld) two heaps

merge(h1, h2)

Specs

merge(t, t) :: t

Merge (meld) two heaps

min(heap, default \\ {nil, nil})

Specs

min(t, element) :: element

min item in the heap

new()

Specs

new :: t

Create new empty heap. Optionally pass in initial key, value

new(key, value)

Specs

new(key, value) :: t

pop(heap, default \\ {nil, nil})

Specs

pop(t, element) :: {element, t}

Returns the min item, as well as the heap without the min item Equivalent to: {min(heap), delete_min(heap)}

iex> PairingHeap.new(1, "first") |> PairingHeap.pop |> elem(0)
{1, "first"}

put(heap, key, value)

Specs

put(t, key, value) :: t

Add element X to priority queue

iex> PairingHeap.new |> PairingHeap.put(1, "first") |> PairingHeap.pop |> elem(0)
{1, "first"}