Repository: JuliaCollections/DataStructures.jl
Pull request #468 (2018-12-09 19:52:10)

Add Binary MinMax Heap 
This PR adds an implementation and tests for a [min-max heap](https://cglab.ca/~morin/teaching/5408/refs/minmax.pdf).

I tried to design the interface and organize the code similarly to how the other heaps are organized.

## New Types
Since minmax heaps support more methods than other heaps, they have their own abstract type.
- `AbstractMinMaxHeap <: AbstractHeap`
- `BinaryMinMaxHeap <: AbstractMinMaxHeap`

## Interface
The interface for the minmax heap is the same as the binary heap with the important different that there are two pop functions: `popmin!` and `popmax!`. The usual `pop!` is defined to be the same as `popmin!`. In addition, `minimum` and `maximum` are both extended from base to return the expected values in minmax heaps. `top` is defined analogously to `pop!` and returns `minimum`.
- `length`
- `isempty`
- `pop!`
- `popmin!`
- `popmax!`
- `push!`
- `top`
- `minimum`
- `maximum`
- `popall!`

codecov[bot]: # [Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468?src=pr&el=h1) Report
> Merging [#468](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468?src=pr&el=desc) into [master](https://codecov.io/gh/JuliaCollections/DataStructures.jl/commit/31044efe5130b8d1980e2b6650337da08f27274e?src=pr&el=desc) will **decrease** coverage by `31.29%`.
> The diff coverage is `73.26%`.

[![Impacted file tree graph](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468/graphs/tree.svg?width=650&token=7FHvoCSQ7k&height=150&src=pr)](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468?src=pr&el=tree)

```diff
@@            Coverage Diff            @@
##           master    #468      +/-   ##
=========================================
- Coverage    98.8%   67.5%   -31.3%     
=========================================
  Files          27      28       +1     
  Lines        1336    2065     +729     
=========================================
+ Hits         1320    1394      +74     
- Misses         16     671     +655
```


| [Impacted Files](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/heaps.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468/diff?src=pr&el=tree#diff-c3JjL2hlYXBzLmps) | `73.33% <ø> (-26.67%)` | :arrow_down: |
| [src/heaps/minmax\_heap.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468/diff?src=pr&el=tree#diff-c3JjL2hlYXBzL21pbm1heF9oZWFwLmps) | `73.26% <73.26%> (ø)` | |
| [src/container\_loops.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468/diff?src=pr&el=tree#diff-c3JjL2NvbnRhaW5lcl9sb29wcy5qbA==) | `35.1% <0%> (-64.9%)` | :arrow_down: |
| [src/balanced\_tree.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468/diff?src=pr&el=tree#diff-c3JjL2JhbGFuY2VkX3RyZWUuamw=) | `45.08% <0%> (-54.92%)` | :arrow_down: |
| [src/delegate.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468/diff?src=pr&el=tree#diff-c3JjL2RlbGVnYXRlLmps) | `50% <0%> (-50%)` | :arrow_down: |
| [src/dict\_support.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468/diff?src=pr&el=tree#diff-c3JjL2RpY3Rfc3VwcG9ydC5qbA==) | `50% <0%> (-50%)` | :arrow_down: |
| [src/heaps/mutable\_binary\_heap.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468/diff?src=pr&el=tree#diff-c3JjL2hlYXBzL211dGFibGVfYmluYXJ5X2hlYXAuamw=) | `50% <0%> (-50%)` | :arrow_down: |
| [src/deque.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468/diff?src=pr&el=tree#diff-c3JjL2RlcXVlLmps) | `57.35% <0%> (-42.65%)` | :arrow_down: |
| [src/tokens2.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468/diff?src=pr&el=tree#diff-c3JjL3Rva2VuczIuamw=) | `64.1% <0%> (-35.9%)` | :arrow_down: |
| [src/sorted\_set.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468/diff?src=pr&el=tree#diff-c3JjL3NvcnRlZF9zZXQuamw=) | `65.24% <0%> (-34.76%)` | :arrow_down: |
| ... and [17 more](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468/diff?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468?src=pr&el=footer). Last update [31044ef...4f35ef9](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/468?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

dillondaudert: Supporting other order statistics (like `median`) builds on top of the base minmax heap implementation, so I think that functionality should be added in a future PR if it's desired.
oxinabox: > Supporting other order statistics (like median) builds on top of the base minmax heap implementation, so I think that functionality should be added in a future PR if it's desired.

Reasonable
ararslan: What's currently implemented looks good to me, including in terms of naming.
dillondaudert: Some points that still need to be cleared up, I think:
- Renaming `klargest!`/`ksmallest!` (-> `popmin!(heap, k)`/`popmax!(h, k)`?)
- If `empty!` should return the (sorted) contents or just delete them
  - If `empty!` just deletes the contents, should returning the sorted contents be called `popall!`, or something else?

I'm in favor of overloading `popmin`/`popmax`, changing `empty!` to only delete contents (returning the contents doesn't seem to be in line with how `empty!` behaves on other collections), and replacing it with `popall!(heap, ordering=Forward)` or something similar.
oxinabox: > I'm in favor of overloading popmin/popmax, changing empty! to only delete contents (returning the contents doesn't seem to be in line with how empty! behaves on other collections), and replacing it with `popall!(heap, ordering=Forward)` or something similar.


yes, lets do that.
oxinabox: i like the new names.
I will try and do  a second pass of reviewing tomorrow.

Patch:
diff --git a/docs/src/heaps.md b/docs/src/heaps.md
index 53d57a8..d603a91 100644
--- a/docs/src/heaps.md
+++ b/docs/src/heaps.md
@@ -51,6 +51,39 @@ h = mutable_binary_minheap([1,4,3,2])
 h = mutable_binary_maxheap([1,4,3,2])    # create a mutable min/max heap from a vector
 ```
 
+## Min-max heaps
+Min-max heaps maintain the minimum _and_ the maximum of a set, 
+allowing both to be retrieved in constant (`O(1)`) time.
+The min-max heaps in this package are subtypes of `AbstractMinMaxHeap <: AbstractHeap`
+and have the same interface as other heaps with the following additions:
+```julia
+# Let h be a min-max heap, k an integer
+minimum(h)     # return the smallest element
+maximum(h)     # return the largest element
+
+popmin!(h)     # remove and return the smallest element
+popmin!(h, k)  # remove and return the smallest k elements
+
+popmax!(h)     # remove and return the largest element
+popmax!(h, k)  # remove and return the largest k elements
+
+popall!(h)     # remove and return all the elements, sorted smallest to largest
+popall!(h, o)  # remove and return all the elements according to ordering o
+```
+The usual `top(h)` and `pop!(h)` are defined to be `minimum(h)` and `popmin!(h)`, 
+respectively.
+
+This package includes an implementation of a binary min-max heap (`BinaryMinMaxHeap`).
+> Atkinson, M.D., Sack, J., Santoro, N., & Strothotte, T. (1986). Min-Max > Heaps and Generalized Priority Queues. Commun. ACM, 29, 996-1000.
+> doi: [10.1145/6617.6621](https://doi.org/10.1145/6617.6621)
+
+Examples:
+```julia
+h = BinaryMinMaxHeap{Int}()          # create an empty min-max heap with integer values
+
+h = BinaryMinMaxHeap([1, 2, 3, 4]) # create a min-max heap from a vector
+```
+
 # Functions using heaps
 
 Heaps can be used to extract the largest or smallest elements of an
diff --git a/src/DataStructures.jl b/src/DataStructures.jl
index ea49a4f..c3436f3 100644
--- a/src/DataStructures.jl
+++ b/src/DataStructures.jl
@@ -13,7 +13,7 @@ module DataStructures
                  isless,
                  union, intersect, symdiff, setdiff, issubset,
                  searchsortedfirst, searchsortedlast, in,
-                 eachindex, keytype, valtype
+                 eachindex, keytype, valtype, minimum, maximum
     import Base: iterate
 
     using OrderedCollections
@@ -36,6 +36,7 @@ module DataStructures
     export BinaryHeap, binary_minheap, binary_maxheap, nlargest, nsmallest
     export MutableBinaryHeap, mutable_binary_minheap, mutable_binary_maxheap
     export heapify!, heapify, heappop!, heappush!, isheap
+    export BinaryMinMaxHeap, popmin!, popmax!, popall!
 
     export OrderedDict, OrderedSet
     export DefaultDict, DefaultOrderedDict
diff --git a/src/heaps.jl b/src/heaps.jl
index 4d6ca93..a1bcec5 100644
--- a/src/heaps.jl
+++ b/src/heaps.jl
@@ -50,6 +50,8 @@ abstract type AbstractHeap{VT} end
 
 abstract type AbstractMutableHeap{VT,HT} <: AbstractHeap{VT} end
 
+abstract type AbstractMinMaxHeap{VT} <: AbstractHeap{VT} end
+
 # comparer
 
 struct LessThan
@@ -66,6 +68,7 @@ compare(c::GreaterThan, x, y) = x > y
 include("heaps/binary_heap.jl")
 include("heaps/mutable_binary_heap.jl")
 include("heaps/arrays_as_heaps.jl")
+include("heaps/minmax_heap.jl")
 
 # generic functions
 
diff --git a/src/heaps/minmax_heap.jl b/src/heaps/minmax_heap.jl
new file mode 100644
index 0000000..17b0d77
--- /dev/null
+++ b/src/heaps/minmax_heap.jl
@@ -0,0 +1,277 @@
+################################################
+#
+# minmax heap type and constructors
+#
+################################################
+
+mutable struct BinaryMinMaxHeap{T} <: AbstractMinMaxHeap{T}
+    valtree::Vector{T}
+    
+    BinaryMinMaxHeap{T}() where {T} = new{T}(Vector{T}())
+    
+    function BinaryMinMaxHeap(xs::AbstractVector{T}) where {T}
+        valtree = _make_binary_minmax_heap(xs)
+        new{T}(valtree)
+    end
+end
+
+################################################
+#
+# core implementation
+#
+################################################
+
+function _make_binary_minmax_heap(xs)
+    valtree = copy(xs)
+    for i in length(xs):-1:1
+        _minmax_heap_trickle_down!(valtree, i)
+    end
+    valtree
+end
+
+function _minmax_heap_bubble_up!(A::AbstractVector, i::Integer)
+    if on_minlevel(i)
+        if i > 1 && A[i] > A[hparent(i)]
+            # swap to parent and bubble up max
+            tmp = A[i]
+            A[i] = A[hparent(i)]
+            A[hparent(i)] = tmp
+            _minmax_heap_bubble_up!(A, hparent(i), Reverse)
+        else
+            # bubble up min
+            _minmax_heap_bubble_up!(A, i, Forward)
+        end
+        
+    else
+        # max level
+        if i > 1 && A[i] < A[hparent(i)]
+            # swap to parent and bubble up min
+            tmp = A[i]
+            A[i] = A[hparent(i)]
+            A[hparent(i)] = tmp
+            _minmax_heap_bubble_up!(A, hparent(i), Forward)
+        else
+            # bubble up max
+            _minmax_heap_bubble_up!(A, i, Reverse)
+        end
+    end
+   return 
+end
+
+function _minmax_heap_bubble_up!(A::AbstractVector, i::Integer, o::Ordering, x=A[i])
+    if hasgrandparent(i)
+        gparent = hparent(hparent(i))
+        if lt(o, x, A[gparent])
+            A[i] = A[gparent]
+            A[gparent] = x
+            _minmax_heap_bubble_up!(A, gparent, o)
+        end
+    end
+    return          
+end
+
+function _minmax_heap_trickle_down!(A::AbstractVector, i::Integer)
+    if on_minlevel(i)
+        _minmax_heap_trickle_down!(A, i, Forward)
+    else
+        _minmax_heap_trickle_down!(A, i, Reverse)
+    end
+    return
+end
+
+function _minmax_heap_trickle_down!(A::AbstractVector, i::Integer, o::Ordering, x=A[i])
+                    
+    if haschildren(i, A)
+        # get the index of the extremum (min or max) descendant
+        extremum = o === Forward ? minimum : maximum
+        _, m = extremum((A[j], j) for j in children_and_grandchildren(length(A), i))
+
+        if isgrandchild(m, i)
+            if lt(o, A[m], A[i])
+                A[i] = A[m]
+                A[m] = x
+                if lt(o, A[hparent(m)], A[m])
+                    t = A[m]
+                    A[m] = A[hparent(m)]
+                    A[hparent(m)] = t
+                end
+                _minmax_heap_trickle_down!(A, m, o)
+            end
+        else
+            if lt(o, A[m], A[i])
+                A[i] = A[m]
+                A[m] = x
+            end
+        end
+    end
+    return
+end
+                    
+################################################
+#
+# utilities
+#
+################################################
+
+@inline level(i) = floor(Int, log2(i))
+@inline lchild(i) = 2*i
+@inline rchild(i) = 2*i+1
+@inline children(i) = (lchild(i), rchild(i))
+@inline hparent(i) = i ÷ 2
+@inline on_minlevel(i) = level(i) % 2 == 0 
+@inline haschildren(i, A) = lchild(i) ≤ length(A)
+@inline isgrandchild(j, i) = j > rchild(i)
+@inline hasgrandparent(i) = i ≥ 4 
+
+"""
+    children_and_grandchildren(maxlen, i)
+
+Return the indices of all children and grandchildren of
+position `i`.
+"""
+function children_and_grandchildren(maxlen::T, i::T) where {T <: Integer}
+    _children_and_grandchildren = T[]
+    for child in children(i)
+        for desc in (child, lchild(child), rchild(child))
+            if desc ≤ maxlen
+                push!(_children_and_grandchildren, desc)
+            end
+        end
+    end
+    return _children_and_grandchildren
+end
+
+"""
+    is_minmax_heap(h::AbstractVector) -> Bool
+
+Return `true` if `A` is a min-max heap. A min-max heap is a
+heap where the minimum element is the root and the maximum
+element is a child of the root.
+"""
+function is_minmax_heap(A::AbstractVector)
+
+    for i in 1:length(A)
+        if on_minlevel(i)
+            # check that A[i] < children A[i]
+            #    and grandchildren A[i]
+            for j in children_and_grandchildren(length(A), i)
+                A[i] ≤ A[j] || return false
+            end
+        else
+            # max layer
+            for j in children_and_grandchildren(length(A), i)
+                A[i] ≥ A[j] || return false
+            end
+        end
+    end
+    return true
+end
+
+################################################
+#
+# interfaces
+#
+################################################
+
+length(h::BinaryMinMaxHeap) = length(h.valtree)
+
+isempty(h::BinaryMinMaxHeap) = isempty(h.valtree)
+
+"""
+    pop!(h::BinaryMinMaxHeap) = popmin!(h)
+"""
+@inline pop!(h::BinaryMinMaxHeap) = popmin!(h)
+
+"""
+    popmin!(h::BinaryMinMaxHeap) -> min
+                        
+Remove the minimum value from the heap.
+"""
+function popmin!(h::BinaryMinMaxHeap)
+    valtree = h.valtree
+    !isempty(valtree) || throw(ArgumentError("heap must be non-empty"))
+    x = valtree[1]
+    y = pop!(valtree)
+    if !isempty(valtree)
+        valtree[1] = y
+        _minmax_heap_trickle_down!(valtree, 1)
+    end
+    return x
+end
+
+                        
+"""
+    popmin!(h::BinaryMinMaxHeap, k::Integer) -> vals
+                        
+Remove up to the `k` smallest values from the heap.
+"""
+@inline function popmin!(h::BinaryMinMaxHeap, k::Integer) 
+    return [popmin!(h) for _ in 1:min(length(h), k)]
+end
+
+"""
+    popmax!(h::BinaryMinMaxHeap) -> max
+                        
+Remove the maximum value from the heap.
+"""
+function popmax!(h::BinaryMinMaxHeap)
+    valtree = h.valtree
+    !isempty(valtree) || throw(ArgumentError("heap must be non-empty"))
+    @inbounds x, i = maximum(((valtree[j], j) for j in 1:min(length(valtree), 3)))
+    y = pop!(valtree)
+    if !isempty(valtree) && i <= length(valtree)
+        @inbounds valtree[i] = y
+        _minmax_heap_trickle_down!(valtree, i)
+    end
+    return x    
+end
+
+"""
+    popmax!(h::BinaryMinMaxHeap, k::Integer) -> vals
+                        
+Remove up to the `k` largest values from the heap.
+"""
+@inline function popmax!(h::BinaryMinMaxHeap, k::Integer) 
+    return [popmax!(h) for _ in 1:min(length(h), k)]                    
+end
+                        
+                        
+function push!(h::BinaryMinMaxHeap, v)
+    valtree = h.valtree        
+    push!(valtree, v)
+    _minmax_heap_bubble_up!(valtree, length(valtree))
+end
+
+"""
+    top(h::BinaryMinMaxHeap)
+                        
+Get the top (minimum) of the heap.
+"""
+@inline top(h::BinaryMinMaxHeap) = minimum(h)
+
+@inline function minimum(h::BinaryMinMaxHeap) 
+    valtree = h.valtree
+    !isempty(h) || throw(ArgumentError("heap must be non-empty"))
+    return @inbounds h.valtree[1]
+end
+
+@inline function maximum(h::BinaryMinMaxHeap) 
+    valtree = h.valtree
+    !isempty(h) || throw(ArgumentError("heap must be non-empty"))
+    return @inbounds maximum(valtree[1:min(end, 3)])
+end
+                        
+empty!(h::BinaryMinMaxHeap) = (empty!(h.valtree); h)
+                        
+
+"""
+    popall!(h::BinaryMinMaxHeap, ::Ordering = Forward)
+                        
+Remove and return all the elements of `h` according to
+the given ordering. Default is `Forward` (smallest to 
+largest).
+"""
+popall!(h::BinaryMinMaxHeap) = popall!(h, Forward)
+popall!(h::BinaryMinMaxHeap, ::ForwardOrdering) = popmin!(h, length(h))
+popall!(h::BinaryMinMaxHeap, ::ReverseOrdering) = popmax!(h, length(h))
+


Test patch:
diff --git a/test/runtests.jl b/test/runtests.jl
index c18f267..daf11c8 100644
--- a/test/runtests.jl
+++ b/test/runtests.jl
@@ -18,6 +18,7 @@ tests = ["int_set",
          "disjoint_set",
          "binheap",
          "mutable_binheap",
+         "minmax_heap",
          "default_dict",
          "trie",
          "list",
diff --git a/test/test_minmax_heap.jl b/test/test_minmax_heap.jl
new file mode 100644
index 0000000..8a8bdb7
--- /dev/null
+++ b/test/test_minmax_heap.jl
@@ -0,0 +1,164 @@
+# tests for min-max heaps
+using DataStructures: _make_binary_minmax_heap, is_minmax_heap, children_and_grandchildren
+using Base.Order: Forward, Reverse
+
+@testset "Binary MinMax Heaps" begin
+    
+    @testset "is_minmax_heap tests" begin
+        mmheap = [0, 10, 9, 2, 3, 4, 5]
+        @test is_minmax_heap(mmheap)
+        @test is_minmax_heap([])
+        @test is_minmax_heap([rand()])
+    end
+    
+    @testset "make heap tests" begin
+        vs = [10, 4, 6, 1, 16, 2, 20, 17, 13, 5]
+        
+        @testset "make from array tests" begin
+            h = BinaryMinMaxHeap(vs)
+            @test length(h) == 10
+            @test !isempty(h)
+            @test top(h) == minimum(h) == 1
+            @test maximum(h) == 20
+            @test is_minmax_heap(h.valtree)
+        end
+        
+        @testset "make from random arrays tests" begin
+            for i = 1:20
+                A = rand(50)
+                vtree = _make_binary_minmax_heap(A)
+                @test is_minmax_heap(vtree)
+            end
+        end
+        
+        @testset "push! tests" begin
+            h = BinaryMinMaxHeap{Int}()
+            
+            @test length(h) == 0
+            @test isempty(h)
+            
+            push!(h, 1)
+            @test top(h) == 1
+            push!(h, 2)
+            @test is_minmax_heap(h.valtree)
+            push!(h, 10)
+            @test is_minmax_heap(h.valtree)
+            push!(h, rand(Int))
+            @test is_minmax_heap(h.valtree)
+            for i = 1:5
+                A = rand(20)
+                hs = BinaryMinMaxHeap(A)
+                for j = 1:4
+                    push!(hs, rand())
+                    @test is_minmax_heap(hs.valtree)
+                end
+            end
+        end
+    end
+    
+    @testset "pop! tests" begin
+        @testset "popmin! tests" begin
+            h = BinaryMinMaxHeap([1])
+            @test popmin!(h) == 1
+            @test length(h) == 0
+            @test isempty(h)
+            h = BinaryMinMaxHeap([1, 3, 2])
+            @test popmin!(h) == 1
+            @test length(h) == 2
+            @test is_minmax_heap(h.valtree)
+            @test minimum(h) == 2
+            for i = 1:20
+                A = rand(50)
+                h = BinaryMinMaxHeap(A)
+                minval = minimum(A)
+                @test popmin!(h) == minval
+                @test length(h) == 49
+                @test is_minmax_heap(h.valtree)
+            end
+        end
+        @testset "popmax! tests" begin
+            h = BinaryMinMaxHeap([1])
+            @test popmax!(h) == 1
+            @test length(h) == 0
+            @test isempty(h)
+            h = BinaryMinMaxHeap([1, 2, 3])
+            @test popmax!(h) == 3
+            @test length(h) == 2
+            @test is_minmax_heap(h.valtree)
+            @test maximum(h) == 2
+            h = BinaryMinMaxHeap([1, 3, 2])
+            @test popmax!(h) == 3
+            @test length(h) == 2
+            @test is_minmax_heap(h.valtree)
+            @test maximum(h) == 2
+        end
+    end
+    
+    @testset "empty!" begin
+        h = BinaryMinMaxHeap([1, 4, 3, 10, 2])
+        ret = empty!(h)
+        @test ret === h
+        @test length(ret) == 0
+        @test isempty(ret)
+    end
+
+    @testset "popall!" begin
+        @testset "popmin! tests" begin
+            A = rand(Int, 50)
+            sorted_A = sort(A)
+            h = BinaryMinMaxHeap(A)
+            @test popall!(h) == sorted_A
+            @test isempty(h)
+            @test length(h) == 0
+            
+            h = BinaryMinMaxHeap(A)
+            @test popmin!(h, 10) == sorted_A[1:10]
+            @test !isempty(h)
+            @test length(h) == 40
+        end
+        @testset "popmax! tests" begin
+            A = rand(Int, 50)
+            sorted_A = sort(A, order=Reverse)
+            h = BinaryMinMaxHeap(A)
+            @test popall!(h, Reverse) == sorted_A
+            @test length(h) == 0
+            @test isempty(h)
+            
+            h = BinaryMinMaxHeap(A)
+            @test popmax!(h, 10) == sorted_A[1:10]
+            @test length(h) == 40
+            @test !isempty(h)
+        end
+    end
+    
+    @testset "type conversion" begin
+        h = BinaryMinMaxHeap{Float64}()
+        push!(h, 3.)
+        push!(h, 5)
+        push!(h, Rational(4, 8))
+        push!(h, Complex(10.1, 0.0))
+        
+        @test h.valtree == [0.5, 10.1, 3.0, 5.0]
+    end
+    
+    @testset "children_and_grandchildren tests" begin
+        @test children_and_grandchildren(1, 1) == Int[]
+        @test children_and_grandchildren(2, 1) == [2]
+        @test children_and_grandchildren(3, 1) == [2, 3]
+        @test children_and_grandchildren(7, 1) == [2, 4, 5, 3, 6, 7]
+        @test children_and_grandchildren(10, 2) == [4, 8, 9, 5, 10]
+    end
+    
+    @testset "throw errors tests" begin
+        h = BinaryMinMaxHeap{Int}()
+        @test_throws ArgumentError pop!(h)
+        @test_throws ArgumentError popmin!(h)
+        
+        @test_throws ArgumentError popmax!(h)
+        
+        @test_throws ArgumentError top(h)
+        @test_throws ArgumentError minimum(h)
+        @test_throws ArgumentError maximum(h)
+        
+    end
+end