Heap data structure for Elixir.
Go to file
Renovate Bot bd89d21d25
continuous-integration/drone/pr Build is passing Details
continuous-integration/drone/push Build is passing Details
chore(deps): update dependency erlang to v26.2.2
2024-02-09 10:36:18 +13:00
config chore: Update forgejo hostname. 2024-02-05 15:51:08 +13:00
lib chore: migrate to local. (#23) 2023-07-28 18:18:36 +12:00
test Modernise Elixir usage and replace espec with exunit. 2017-09-20 14:12:36 +12:00
.drone.yml chore: Update forgejo hostname. 2024-02-05 15:51:08 +13:00
.formatter.exs Update dependencies and CI config. 2018-09-04 16:52:19 +12:00
.gitignore Modernise Elixir usage and replace espec with exunit. 2017-09-20 14:12:36 +12:00
.tool-versions chore(deps): update dependency erlang to v26.2.2 2024-02-09 10:36:18 +13:00
.travis.yml Update Inch config and add to inchci. 2017-09-26 13:39:49 +13:00
CHANGELOG.md chore: Update forgejo hostname. 2024-02-05 15:51:08 +13:00
LICENSE.md chore!: Relicense to HL3-FULL. 2023-01-17 10:53:03 +13:00
README.md chore: Update forgejo hostname. 2024-02-05 15:51:08 +13:00
mix.exs chore: Update forgejo hostname. 2024-02-05 15:51:08 +13:00
mix.lock chore: migrate to local. (#23) 2023-07-28 18:18:36 +12:00
renovate.json chore(deps): add renovate.json 2023-07-28 18:22:54 +12:00

README.md

Heap

Build Status Hex.pm Hippocratic License HL3-FULL

A Heap is a very useful data structure, because it sorts, quickly, at insert time.

See also: https://en.wikipedia.org/wiki/Heap_(data_structure)

You can use it for things like:

  • Help with scientific computing
  • Quickly sorting
  • Priority queues

Installation

This package is available in Hex:

  1. Add heap to your list of dependencies in mix.exs:

    def deps do
      [{:heap, "~> 2.0"}]
    end
    
  2. Run mix deps.get

Deprecation warning

If you're upgrading from heap < 2.0 be aware that the direction of the :< and :> atoms passed into Heap.new/1 has changed to make more sense.

Examples

Create a min heap and use it to find the smallest element in a collection:

1..500 |> Enum.shuffle |> Enum.into(Heap.min) |> Heap.root
# => 1

Likewise, for max heaps:

1..500 |> Enum.shuffle |> Enum.into(Heap.max) |> Heap.root
# => 500

A priority queue:

Tuples are compared by their elements in order, so you can push tuples of {priority, term} into a Heap for sorting by priority:

Heap.new
|> Heap.push({4, :jam})
|> Heap.push({1, :milk})
|> Heap.push({2, :eggs})
|> Heap.push({1, :bread})
|> Heap.push({3, :butter})
|> Heap.push({2, :coffee})
|> Enum.map(fn {_, what} -> what end)
# => [:bread, :milk, :coffee, :eggs, :butter, :jam]

The heap can also be constructed with a custom comparator:

Heap.new(&(Date.compare(elem(&1, 0), elem(&2, 0)) == :gt))
|> Heap.push({~D[2017-11-20], :jam})
|> Heap.push({~D[2017-11-21], :milk})
|> Heap.push({~D[2017-10-21], :bread})
|> Heap.push({~D[2017-10-20], :eggs})
|> Enum.map(fn {_, what} -> what end)
# => [:milk, :jam, :bread, :eggs]

To access the root and the rest of the heap in one line use Heap.split/1:

{root, rest} = Heap.split(heap)
{root, rest} == {Heap.root(heap), Heap.pop(heap)}
# => true

Documentation

Full API documentation is available on (hexdocs.pm)[https://hexdocs.pm/heap]

Contributing

  1. Fork it ( https://harton.dev/repo/fork/50 )
  2. Create your feature branch (git checkout -b my-new-feature)
  3. Commit your changes (git commit -am 'Add some feature')
  4. Push to the branch (git push origin my-new-feature)
  5. Create a new Pull Request

License

This software is licensed under the terms of the HL3-FULL, see the LICENSE.md file included with this package for the terms.

This license actively proscribes this software being used by and for some industries, countries and activities. If your usage of this software doesn't comply with the terms of this license, then contact me with the details of your use-case to organise the purchase of a license - the cost of which may include a donation to a suitable charity or NGO.