Repository: JuliaCollections/DataStructures.jl (julia)

Issue:
BoundsError in MutableBinaryHeap delete!
If run with ```--check-bounds=yes```, the following throws ```BoundsError```:
```Julia
x = MutableBinaryMinHeap{Int}()
h1 = push!(x, 1)
h2 = push!(x, 2)
delete!(x, h2)
```
[Offending line](https://github.com/JuliaCollections/DataStructures.jl/blob/v0.17.13/src/heaps/mutable_binary_heap.jl#L116)
```Julia
        @inbounds nodes[nd_id] = new_rt = pop!(nodes)
```

Looks to happen when deleting from the end of the heap. The code is safe under the assumption that ```pop!(::Vector)``` doesn't resize underlying storage, but not ideal to have this throw when bounds checks are forced.

Pull request description:
Fixes #611

Patch:
diff --git a/Project.toml b/Project.toml
index 352dfea40..f114a5977 100644
--- a/Project.toml
+++ b/Project.toml
@@ -1,6 +1,6 @@
 name = "DataStructures"
 uuid = "864edb3b-99cc-5e75-8d2d-829cb0a9cfe8"
-version = "0.17.13"
+version = "0.17.14"
 
 [deps]
 InteractiveUtils = "b77e0a4c-d291-57a0-90e8-8db25a27a240"
diff --git a/src/heaps/mutable_binary_heap.jl b/src/heaps/mutable_binary_heap.jl
index e39bbc92f..8b1cc005e 100644
--- a/src/heaps/mutable_binary_heap.jl
+++ b/src/heaps/mutable_binary_heap.jl
@@ -113,7 +113,8 @@ function _binary_heap_pop!(comp::Comp,
         empty!(nodes)
     else
         # move the last node to the position of the removed node
-        @inbounds nodes[nd_id] = new_rt = pop!(nodes)
+        @inbounds nodes[nd_id] = new_rt = nodes[end]
+        pop!(nodes)
         @inbounds nodemap[new_rt.handle] = nd_id
 
         if length(nodes) > 1


Test patch:
diff --git a/test/test_mutable_binheap.jl b/test/test_mutable_binheap.jl
index 395e5adee..a817da27e 100644
--- a/test/test_mutable_binheap.jl
+++ b/test/test_mutable_binheap.jl
@@ -193,6 +193,14 @@ end
         @test isequal(extract_all!(hp), [1, 9, 11, 17, 19, 21, 22, 27])
     end
 
+    @testset "test delete! at end" begin
+        h = MutableBinaryMinHeap{Int}()
+        push!(h, 1)
+        handle = push!(h, 2)
+        delete!(h, handle)
+        @test isequal(heap_values(h), [1])
+    end
+
     @testset "test update! and top_with_handle" begin
         for (hf,m) = [(MutableBinaryMinHeap,-2.0), (MutableBinaryMaxHeap,2.0)]
             xs = rand(100)