Repository: JuliaCollections/DataStructures.jl (julia)

Issue:
Add empty! for all Heaps
I would like an `empty!` method for all heap types. It is currently only defined for `BinaryMinMaxHeap`. 

Compared to using `extract_all!`, an `empty!` method would not allocate a vector, which might be important for performance oriented applications. 

Maybe an implementation could look like this:

```jl
function Base.empty!(h::AbstractHeap)
    while !isempty(h)
        pop!(h)
    end
    h
end
```

Pull request description:
The PR adds definitions of `empty!(::BinaryHeap)` and `empty!(::MutableBinaryHeap)`.

Fixes https://github.com/JuliaCollections/DataStructures.jl/issues/866.

Patch:
diff --git a/docs/src/heaps.md b/docs/src/heaps.md
index 66e5124b5..9b220cfd4 100644
--- a/docs/src/heaps.md
+++ b/docs/src/heaps.md
@@ -13,6 +13,8 @@ length(h)            # returns the number of elements
 
 isempty(h)           # returns whether the heap is empty
 
+empty!(h)            # reset the heap
+
 push!(h, v)          # add a value to the heap
 
 first(h)             # return the first (top) value of a heap
diff --git a/src/heaps.jl b/src/heaps.jl
index 3ab8e7570..ca6052f42 100644
--- a/src/heaps.jl
+++ b/src/heaps.jl
@@ -20,6 +20,8 @@
 #   - isempty(h)          returns whether the heap is
 #                         empty
 #
+#   - empty!(h)           reset the heap
+#
 #   - push!(h, v)         add a value to the heap
 #
 #   - sizehint!(h, s)     set size hint to a heap
diff --git a/src/heaps/binary_heap.jl b/src/heaps/binary_heap.jl
index f3850d5d6..d39b5f584 100644
--- a/src/heaps/binary_heap.jl
+++ b/src/heaps/binary_heap.jl
@@ -106,6 +106,11 @@ Removes and returns the element at the top of the heap `h`.
 """
 Base.pop!(h::BinaryHeap) = heappop!(h.valtree, h.ordering)
 
+function Base.empty!(h::BinaryHeap)
+    empty!(h.valtree)
+    return h
+end
+
 # Suggest that heap `h` reserve capacity for at least `n` elements. This can improve performance.
 function Base.sizehint!(h::BinaryHeap, n::Integer)
     sizehint!(h.valtree, n)
diff --git a/src/heaps/mutable_binary_heap.jl b/src/heaps/mutable_binary_heap.jl
index 699aa538c..509e7f6a0 100644
--- a/src/heaps/mutable_binary_heap.jl
+++ b/src/heaps/mutable_binary_heap.jl
@@ -226,6 +226,12 @@ function Base.push!(h::MutableBinaryHeap{T}, v) where T
     return i
 end
 
+function Base.empty!(h::MutableBinaryHeap)
+    empty!(h.nodes)
+    empty!(h.node_map)
+    return h
+end
+
 function Base.sizehint!(h::MutableBinaryHeap, s::Integer)
     sizehint!(h.nodes, s)
     sizehint!(h.node_map, s)


Test patch:
diff --git a/test/test_binheap.jl b/test/test_binheap.jl
index 69ee76ead..26f261669 100644
--- a/test/test_binheap.jl
+++ b/test/test_binheap.jl
@@ -237,4 +237,19 @@
 
         @test isequal(h.valtree, [0.5, 5.0, 3.0, 10.1])
     end
+
+    @testset "empty!" begin
+        vs = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
+        vs2 = collect(enumerate(vs))
+        ordering = Base.Order.By(last)
+
+        for h in (BinaryMinHeap(vs), BinaryMaxHeap(vs), BinaryHeap(ordering, vs2))
+            @test length(h) == length(vs)
+            @test !isempty(h)
+            ret = empty!(h)
+            @test ret === h
+            @test length(ret) == 0
+            @test isempty(ret)
+        end
+    end
 end # @testset BinaryHeap
diff --git a/test/test_mutable_binheap.jl b/test/test_mutable_binheap.jl
index e12c12313..e07335660 100644
--- a/test/test_mutable_binheap.jl
+++ b/test/test_mutable_binheap.jl
@@ -342,4 +342,20 @@ end
         update!(h, 2, 20)
         @test isequal(heap_values(h), [0.5, 10.1, 3.0, 20.0])
     end
+
+    @testset "empty!" begin
+        vs = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
+        vs2 = collect(enumerate(vs))
+        ordering = Base.Order.By(last)
+
+        for h in (MutableBinaryMinHeap(vs), MutableBinaryMaxHeap(vs), MutableBinaryHeap(ordering, vs2))
+            @test length(h) == length(vs)
+            @test !isempty(h)
+            ret = empty!(h)
+            @test ret === h
+            @test length(ret) == 0
+            @test isempty(ret)
+            @test verify_heap(ret)
+        end
+    end
 end # @testset MutableBinheap