Packages

inplace

0.2.2
0.7.12 0.7.11 0.7.10 0.7.9 0.7.8 0.7.7 0.7.6 0.7.5 0.7.4 0.7.3 0.7.2 0.7.1 0.7.0 0.6.8 0.6.7 0.6.6 0.6.5 0.6.4 0.6.3 0.6.2 0.6.1 0.6.0 0.5.4 0.5.3 0.5.2 0.5.1 0.5.0 0.4.4 0.4.3 0.4.2 0.4.1 0.4.0 0.3.3 0.3.2 0.3.1 0.3.0 0.2.3 0.2.2 0.2.1 0.2.0 0.1.9 0.1.8 0.1.7 0.1.6 0.1.5 0.1.4 0.1.3 0.1.2 0.1.1 0.1.0

Mutable data structures

HexDocs

Current section

Files

Jump to
Readme
50 Versions
0 Dependencies
Dependants
Files
Activity
inplace test adt heap_test.exs
Raw

test/adt/heap_test.exs 

defmodule InPlace.HeapTest do

  use ExUnit.Case



  alias InPlace.{Heap, Array}



  describe "Binary heap" do

    test "creation" do

      ## Create heap

      heap = Heap.new(100)

      assert Heap.empty?(heap)

      assert Heap.size(heap) == 0

      refute Heap.get_min(heap)

      assert Heap.valid?(heap)

    end



    test "insert" do

      heap = Heap.new(100)

      values = Enum.take_random(1..1000, 50)

      Enum.each(values, fn val -> Heap.insert(heap, val) end)

      assert Heap.get_min(heap) == Enum.min(values)

      assert Heap.size(heap) == 50

    end



    test "extract_min" do

      heap = Heap.new(100)

      refute Heap.extract_min(heap)

      values = Enum.take_random(1..1000, 50)

      Enum.each(values, fn val -> Heap.insert(heap, val) end)

      assert Heap.extract_min(heap) == Enum.min(values)

      assert Heap.size(heap) == 49

    end



    test "heapify" do

      heap_size = 100_000

      heap = Heap.new(heap_size)

      ## We will now construct an invalid heap

      ## Set heap size

      Array.put(heap.array, heap_size + 1, heap_size)

      ## Fill out the array with random values

      values = Enum.shuffle(1..heap_size)

      Enum.each(Enum.with_index(values, 1), fn {val, idx} -> Array.put(heap.array, idx, val) end)

      refute Heap.valid?(heap)

      ## Heapify will force the heap property

      Heap.heapify(heap)

      assert Heap.valid?(heap)

    end

  end

end