libphobos/src/std/container/binaryheap.d - gcc - Git at Google

 /**
 This module provides a `BinaryHeap` (aka priority queue)
 adaptor that makes a binary heap out of any user-provided random-access range.

 This module is a submodule of $(MREF std, container).

 Source: $(PHOBOSSRC std/container/binaryheap.d)

 Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.

 License: Distributed under the Boost Software License, Version 1.0.
 (See accompanying file LICENSE_1_0.txt or copy at $(HTTP
 boost.org/LICENSE_1_0.txt)).

 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
 */
 module std.container.binaryheap;

 import std.range.primitives;
 import std.traits;

 public import std.container.util;

 ///
 @system unittest
 {
     import std.algorithm.comparison : equal;
     import std.range : take;
     auto maxHeap = heapify([4, 7, 3, 1, 5]);
     assert(maxHeap.take(3).equal([7, 5, 4]));

     auto minHeap = heapify!"a > b"([4, 7, 3, 1, 5]);
     assert(minHeap.take(3).equal([1, 3, 4]));
 }

 // BinaryHeap
 /**
 Implements a $(HTTP en.wikipedia.org/wiki/Binary_heap, binary heap)
 container on top of a given random-access range type (usually $(D
 T[])) or a random-access container type (usually `Array!T`). The
 documentation of `BinaryHeap` will refer to the underlying range or
 container as the $(I store) of the heap.

 The binary heap induces structure over the underlying store such that
 accessing the largest element (by using the `front` property) is a
 $(BIGOH 1) operation and extracting it (by using the $(D
 removeFront()) method) is done fast in $(BIGOH log n) time.

 If `less` is the less-than operator, which is the default option,
 then `BinaryHeap` defines a so-called max-heap that optimizes
 extraction of the $(I largest) elements. To define a min-heap,
 instantiate BinaryHeap with $(D "a > b") as its predicate.

 Simply extracting elements from a `BinaryHeap` container is
 tantamount to lazily fetching elements of `Store` in descending
 order. Extracting elements from the `BinaryHeap` to completion
 leaves the underlying store sorted in ascending order but, again,
 yields elements in descending order.

 If `Store` is a range, the `BinaryHeap` cannot grow beyond the
 size of that range. If `Store` is a container that supports $(D
 insertBack), the `BinaryHeap` may grow by adding elements to the
 container.
      */
 struct BinaryHeap(Store, alias less = "a < b")
 if (isRandomAccessRange!(Store) || isRandomAccessRange!(typeof(Store.init[])))
 {
     import std.algorithm.comparison : min;
     import std.algorithm.mutation : move, swapAt;
     import std.algorithm.sorting : HeapOps;
     import std.exception : enforce;
     import std.functional : binaryFun;
     import std.typecons : RefCounted, RefCountedAutoInitialize;

     static if (isRandomAccessRange!Store)
         alias Range = Store;
     else
         alias Range = typeof(Store.init[]);
     alias percolate = HeapOps!(less, Range).percolate;
     alias buildHeap = HeapOps!(less, Range).buildHeap;

 // Really weird @@BUG@@: if you comment out the "private:" label below,
 // std.algorithm can't unittest anymore
 //private:

     // The payload includes the support store and the effective length
     private static struct Data
     {
         Store _store;
         size_t _length;
     }
     // TODO: migrate to use the SafeRefCounted. The problem is that some member
     // functions here become @system with a naive switch.
     private RefCounted!(Data, RefCountedAutoInitialize.no) _payload;
     // Comparison predicate
     private alias comp = binaryFun!(less);
     // Convenience accessors
     private @property ref Store _store()
     {
         assert(_payload.refCountedStore.isInitialized,
                 "BinaryHeap not initialized");
         return _payload._store;
     }
     private @property ref size_t _length()
     {
         assert(_payload.refCountedStore.isInitialized,
                 "BinaryHeap not initialized");
         return _payload._length;
     }

     // Asserts that the heap property is respected.
     private void assertValid()
     {
         debug
         {
             import std.conv : to;
             if (!_payload.refCountedStore.isInitialized) return;
             if (_length < 2) return;
             for (size_t n = _length - 1; n >= 1; --n)
             {
                 auto parentIdx = (n - 1) / 2;
                 assert(!comp(_store[parentIdx], _store[n]), to!string(n));
             }
         }
     }

     // @@@BUG@@@: add private here, std.algorithm doesn't unittest anymore
     /*private*/ void pop(Store store)
     {
         assert(!store.empty, "Cannot pop an empty store.");
         if (store.length == 1) return;
         auto t1 = store[].moveFront();
         auto t2 = store[].moveBack();
         store.front = move(t2);
         store.back = move(t1);
         percolate(store[], 0, store.length - 1);
     }

 public:

     /**
        Converts the store `s` into a heap. If `initialSize` is
        specified, only the first `initialSize` elements in `s`
        are transformed into a heap, after which the heap can grow up
        to `r.length` (if `Store` is a range) or indefinitely (if
        `Store` is a container with `insertBack`). Performs
        $(BIGOH min(r.length, initialSize)) evaluations of `less`.
      */
     this(Store s, size_t initialSize = size_t.max)
     {
         acquire(s, initialSize);
     }

 /**
 Takes ownership of a store. After this, manipulating `s` may make
 the heap work incorrectly.
      */
     void acquire(Store s, size_t initialSize = size_t.max)
     {
         _payload.refCountedStore.ensureInitialized();
         _store = move(s);
         _length = min(_store.length, initialSize);
         if (_length < 2) return;
         buildHeap(_store[]);
         assertValid();
     }

 /**
 Takes ownership of a store assuming it already was organized as a
 heap.
      */
     void assume(Store s, size_t initialSize = size_t.max)
     {
         _payload.refCountedStore.ensureInitialized();
         _store = s;
         _length = min(_store.length, initialSize);
         assertValid();
     }

 /**
 Clears the heap. Returns the portion of the store from `0` up to
 `length`, which satisfies the $(LINK2 https://en.wikipedia.org/wiki/Heap_(data_structure),
 heap property).
      */
     auto release()
     {
         if (!_payload.refCountedStore.isInitialized)
         {
             return typeof(_store[0 .. _length]).init;
         }
         assertValid();
         auto result = _store[0 .. _length];
         _payload = _payload.init;
         return result;
     }

 /**
 Returns `true` if the heap is _empty, `false` otherwise.
      */
     @property bool empty()
     {
         return !length;
     }

 /**
 Returns a duplicate of the heap. The `dup` method is available only if the
 underlying store supports it.
      */
     static if (is(typeof((Store s) { return s.dup; }(Store.init)) == Store))
     {
         @property BinaryHeap dup()
         {
             BinaryHeap result;
             if (!_payload.refCountedStore.isInitialized) return result;
             result.assume(_store.dup, length);
             return result;
         }
     }

 /**
 Returns the _length of the heap.
      */
     @property size_t length()
     {
         return _payload.refCountedStore.isInitialized ? _length : 0;
     }

 /**
 Returns the _capacity of the heap, which is the length of the
 underlying store (if the store is a range) or the _capacity of the
 underlying store (if the store is a container).
      */
     @property size_t capacity()
     {
         if (!_payload.refCountedStore.isInitialized) return 0;
         static if (is(typeof(_store.capacity) : size_t))
         {
             return _store.capacity;
         }
         else
         {
             return _store.length;
         }
     }

 /**
 Returns a copy of the _front of the heap, which is the largest element
 according to `less`.
      */
     @property ElementType!Store front()
     {
         enforce(!empty, "Cannot call front on an empty heap.");
         return _store.front;
     }

 /**
 Clears the heap by detaching it from the underlying store.
      */
     void clear()
     {
         _payload = _payload.init;
     }

 /**
 Inserts `value` into the store. If the underlying store is a range
 and $(D length == capacity), throws an exception.
      */
     size_t insert(ElementType!Store value)
     {
         static if (is(typeof(_store.insertBack(value))))
         {
             _payload.refCountedStore.ensureInitialized();
             if (length == _store.length)
             {
                 // reallocate
                 _store.insertBack(value);
             }
             else
             {
                 // no reallocation
                 _store[_length] = value;
             }
         }
         else
         {
             import std.traits : isDynamicArray;
             static if (isDynamicArray!Store)
             {
                 if (length == _store.length)
                     _store.length = (length < 6 ? 8 : length * 3 / 2);
                 _store[_length] = value;
             }
             else
             {
                 // can't grow
                 enforce(length < _store.length,
                         "Cannot grow a heap created over a range");
             }
         }

         // sink down the element
         for (size_t n = _length; n; )
         {
             auto parentIdx = (n - 1) / 2;
             if (!comp(_store[parentIdx], _store[n])) break; // done!
             // must swap and continue
             _store.swapAt(parentIdx, n);
             n = parentIdx;
         }
         ++_length;
         debug(BinaryHeap) assertValid();
         return 1;
     }

 /**
 Removes the largest element from the heap.
      */
     void removeFront()
     {
         enforce(!empty, "Cannot call removeFront on an empty heap.");
         if (_length > 1)
         {
             auto t1 = _store[].moveFront();
             auto t2 = _store[].moveAt(_length - 1);
             _store.front = move(t2);
             _store[_length - 1] = move(t1);
         }
         --_length;
         percolate(_store[], 0, _length);
     }

     /// ditto
     alias popFront = removeFront;

 /**
 Removes the largest element from the heap and returns a copy of
 it. The element still resides in the heap's store. For performance
 reasons you may want to use `removeFront` with heaps of objects
 that are expensive to copy.
      */
     ElementType!Store removeAny()
     {
         removeFront();
         return _store[_length];
     }

 /**
 Replaces the largest element in the store with `value`.
      */
     void replaceFront(ElementType!Store value)
     {
         // must replace the top
         assert(!empty, "Cannot call replaceFront on an empty heap.");
         _store.front = value;
         percolate(_store[], 0, _length);
         debug(BinaryHeap) assertValid();
     }

 /**
 If the heap has room to grow, inserts `value` into the store and
 returns `true`. Otherwise, if $(D less(value, front)), calls $(D
 replaceFront(value)) and returns again `true`. Otherwise, leaves
 the heap unaffected and returns `false`. This method is useful in
 scenarios where the smallest `k` elements of a set of candidates
 must be collected.
      */
     bool conditionalInsert(ElementType!Store value)
     {
         _payload.refCountedStore.ensureInitialized();
         if (_length < _store.length)
         {
             insert(value);
             return true;
         }

         assert(!_store.empty, "Cannot replace front of an empty heap.");
         if (!comp(value, _store.front)) return false; // value >= largest
         _store.front = value;

         percolate(_store[], 0, _length);
         debug(BinaryHeap) assertValid();
         return true;
     }

 /**
 Swapping is allowed if the heap is full. If $(D less(value, front)), the
 method exchanges store.front and value and returns `true`. Otherwise, it
 leaves the heap unaffected and returns `false`.
      */
     bool conditionalSwap(ref ElementType!Store value)
     {
         _payload.refCountedStore.ensureInitialized();
         assert(_length == _store.length,
                 "length and number of stored items out of sync");
         assert(!_store.empty, "Cannot swap front of an empty heap.");

         if (!comp(value, _store.front)) return false; // value >= largest

         import std.algorithm.mutation : swap;
         swap(_store.front, value);

         percolate(_store[], 0, _length);
         debug(BinaryHeap) assertValid();

         return true;
     }
 }

 /// Example from "Introduction to Algorithms" Cormen et al, p 146
 @system unittest
 {
     import std.algorithm.comparison : equal;
     int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
     auto h = heapify(a);
     // largest element
     assert(h.front == 16);
     // a has the heap property
     assert(equal(a, [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]));
 }

 /// `BinaryHeap` implements the standard input range interface, allowing
 /// lazy iteration of the underlying range in descending order.
 @system unittest
 {
     import std.algorithm.comparison : equal;
     import std.range : take;
     int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
     auto top5 = heapify(a).take(5);
     assert(top5.equal([16, 14, 10, 9, 8]));
 }

 /**
 Convenience function that returns a `BinaryHeap!Store` object
 initialized with `s` and `initialSize`.
  */
 BinaryHeap!(Store, less) heapify(alias less = "a < b", Store)(Store s,
         size_t initialSize = size_t.max)
 {

     return BinaryHeap!(Store, less)(s, initialSize);
 }

 ///
 @system unittest
 {
     import std.conv : to;
     import std.range.primitives;
     {
         // example from "Introduction to Algorithms" Cormen et al., p 146
         int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
         auto h = heapify(a);
         h = heapify!"a < b"(a);
         assert(h.front == 16);
         assert(a == [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]);
         auto witness = [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ];
         for (; !h.empty; h.removeFront(), witness.popFront())
         {
             assert(!witness.empty);
             assert(witness.front == h.front);
         }
         assert(witness.empty);
     }
     {
         int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
         int[] b = new int[a.length];
         BinaryHeap!(int[]) h = BinaryHeap!(int[])(b, 0);
         foreach (e; a)
         {
             h.insert(e);
         }
         assert(b == [ 16, 14, 10, 8, 7, 3, 9, 1, 4, 2 ], to!string(b));
     }
 }

 @system unittest
 {
     // Test range interface.
     import std.algorithm.comparison : equal;
     int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
     auto h = heapify(a);
     static assert(isInputRange!(typeof(h)));
     assert(h.equal([16, 14, 10, 9, 8, 7, 4, 3, 2, 1]));
 }

 // https://issues.dlang.org/show_bug.cgi?id=15675
 @system unittest
 {
     import std.container.array : Array;

     Array!int elements = [1, 2, 10, 12];
     auto heap = heapify(elements);
     assert(heap.front == 12);
 }

 // https://issues.dlang.org/show_bug.cgi?id=16072
 @system unittest
 {
     auto q = heapify!"a > b"([2, 4, 5]);
     q.insert(1);
     q.insert(6);
     assert(q.front == 1);

     // test more multiple grows
     int[] arr;
     auto r = heapify!"a < b"(arr);
     foreach (i; 0 .. 100)
         r.insert(i);

     assert(r.front == 99);
 }

 @system unittest
 {
     import std.algorithm.comparison : equal;
     int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
     auto heap = heapify(a);
     auto dup = heap.dup();
     assert(dup.equal([16, 14, 10, 9, 8, 7, 4, 3, 2, 1]));
 }

 @safe unittest
 {
     static struct StructWithoutDup
     {
         int[] a;
         @disable StructWithoutDup dup();
         alias a this;
     }

     // Assert Binary heap can be created when Store doesn't have dup
     // if dup is not used.
     assert(__traits(compiles, ()
         {
             auto s = StructWithoutDup([1,2]);
             auto h = heapify(s);
         }));

     // Assert dup can't be used on BinaryHeaps when Store doesn't have dup
     assert(!__traits(compiles, ()
         {
             auto s = StructWithoutDup([1,2]);
             auto h = heapify(s);
             h.dup();
         }));
 }

 @safe unittest
 {
     static struct StructWithDup
     {
         int[] a;
         StructWithDup dup()
         {
             StructWithDup d;
             return d;
         }
         alias a this;
     }

     // Assert dup can be used on BinaryHeaps when Store has dup
     assert(__traits(compiles, ()
         {
             auto s = StructWithDup([1, 2]);
             auto h = heapify(s);
             h.dup();
         }));
 }

 @system unittest
 {
     import std.algorithm.comparison : equal;
     import std.internal.test.dummyrange;

     alias RefRange = DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random);

     RefRange a;
     RefRange b;
     a.reinit();
     b.reinit();

     auto heap = heapify(a);
     foreach (ref elem; b)
     {
         heap.conditionalSwap(elem);
     }

     assert(equal(heap, [ 5, 5, 4, 4, 3, 3, 2, 2, 1, 1]));
     assert(equal(b, [10, 9, 8, 7, 6, 6, 7, 8, 9, 10]));
 }

 // https://issues.dlang.org/show_bug.cgi?id=17314
 @system unittest
 {
     import std.algorithm.comparison : equal;
     int[] a = [5];
     auto heap = heapify(a);
     heap.insert(6);
     assert(equal(heap, [6, 5]));
 }
	/**
	This module provides a `BinaryHeap` (aka priority queue)
	adaptor that makes a binary heap out of any user-provided random-access range.

	This module is a submodule of $(MREF std, container).

	Source: $(PHOBOSSRC std/container/binaryheap.d)

	Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.

	License: Distributed under the Boost Software License, Version 1.0.
	(See accompanying file LICENSE_1_0.txt or copy at $(HTTP
	boost.org/LICENSE_1_0.txt)).

	Authors: $(HTTP erdani.com, Andrei Alexandrescu)
	*/
	module std.container.binaryheap;

	import std.range.primitives;
	import std.traits;

	public import std.container.util;

	///
	@system unittest
	{
	import std.algorithm.comparison : equal;
	import std.range : take;
	auto maxHeap = heapify([4, 7, 3, 1, 5]);
	assert(maxHeap.take(3).equal([7, 5, 4]));

	auto minHeap = heapify!"a > b"([4, 7, 3, 1, 5]);
	assert(minHeap.take(3).equal([1, 3, 4]));
	}

	// BinaryHeap
	/**
	Implements a $(HTTP en.wikipedia.org/wiki/Binary_heap, binary heap)
	container on top of a given random-access range type (usually $(D
	T[])) or a random-access container type (usually `Array!T`). The
	documentation of `BinaryHeap` will refer to the underlying range or
	container as the $(I store) of the heap.

	The binary heap induces structure over the underlying store such that
	accessing the largest element (by using the `front` property) is a
	$(BIGOH 1) operation and extracting it (by using the $(D
	removeFront()) method) is done fast in $(BIGOH log n) time.

	If `less` is the less-than operator, which is the default option,
	then `BinaryHeap` defines a so-called max-heap that optimizes
	extraction of the $(I largest) elements. To define a min-heap,
	instantiate BinaryHeap with $(D "a > b") as its predicate.

	Simply extracting elements from a `BinaryHeap` container is
	tantamount to lazily fetching elements of `Store` in descending
	order. Extracting elements from the `BinaryHeap` to completion
	leaves the underlying store sorted in ascending order but, again,
	yields elements in descending order.

	If `Store` is a range, the `BinaryHeap` cannot grow beyond the
	size of that range. If `Store` is a container that supports $(D
	insertBack), the `BinaryHeap` may grow by adding elements to the
	container.
	*/
	struct BinaryHeap(Store, alias less = "a < b")
	if (isRandomAccessRange!(Store) \|\| isRandomAccessRange!(typeof(Store.init[])))
	{
	import std.algorithm.comparison : min;
	import std.algorithm.mutation : move, swapAt;
	import std.algorithm.sorting : HeapOps;
	import std.exception : enforce;
	import std.functional : binaryFun;
	import std.typecons : RefCounted, RefCountedAutoInitialize;

	static if (isRandomAccessRange!Store)
	alias Range = Store;
	else
	alias Range = typeof(Store.init[]);
	alias percolate = HeapOps!(less, Range).percolate;
	alias buildHeap = HeapOps!(less, Range).buildHeap;

	// Really weird @@BUG@@: if you comment out the "private:" label below,
	// std.algorithm can't unittest anymore
	//private:

	// The payload includes the support store and the effective length
	private static struct Data
	{
	Store _store;
	size_t _length;
	}
	// TODO: migrate to use the SafeRefCounted. The problem is that some member
	// functions here become @system with a naive switch.
	private RefCounted!(Data, RefCountedAutoInitialize.no) _payload;
	// Comparison predicate
	private alias comp = binaryFun!(less);
	// Convenience accessors
	private @property ref Store _store()
	{
	assert(_payload.refCountedStore.isInitialized,
	"BinaryHeap not initialized");
	return _payload._store;
	}
	private @property ref size_t _length()
	{
	assert(_payload.refCountedStore.isInitialized,
	"BinaryHeap not initialized");
	return _payload._length;
	}

	// Asserts that the heap property is respected.
	private void assertValid()
	{
	debug
	{
	import std.conv : to;
	if (!_payload.refCountedStore.isInitialized) return;
	if (_length < 2) return;
	for (size_t n = _length - 1; n >= 1; --n)
	{
	auto parentIdx = (n - 1) / 2;
	assert(!comp(_store[parentIdx], _store[n]), to!string(n));
	}
	}
	}

	// @@@BUG@@@: add private here, std.algorithm doesn't unittest anymore
	/private/ void pop(Store store)
	{
	assert(!store.empty, "Cannot pop an empty store.");
	if (store.length == 1) return;
	auto t1 = store[].moveFront();
	auto t2 = store[].moveBack();
	store.front = move(t2);
	store.back = move(t1);
	percolate(store[], 0, store.length - 1);
	}

	public:

	/**
	Converts the store `s` into a heap. If `initialSize` is
	specified, only the first `initialSize` elements in `s`
	are transformed into a heap, after which the heap can grow up
	to `r.length` (if `Store` is a range) or indefinitely (if
	`Store` is a container with `insertBack`). Performs
	$(BIGOH min(r.length, initialSize)) evaluations of `less`.
	*/
	this(Store s, size_t initialSize = size_t.max)
	{
	acquire(s, initialSize);
	}

	/**
	Takes ownership of a store. After this, manipulating `s` may make
	the heap work incorrectly.
	*/
	void acquire(Store s, size_t initialSize = size_t.max)
	{
	_payload.refCountedStore.ensureInitialized();
	_store = move(s);
	_length = min(_store.length, initialSize);
	if (_length < 2) return;
	buildHeap(_store[]);
	assertValid();
	}

	/**
	Takes ownership of a store assuming it already was organized as a
	heap.
	*/
	void assume(Store s, size_t initialSize = size_t.max)
	{
	_payload.refCountedStore.ensureInitialized();
	_store = s;
	_length = min(_store.length, initialSize);
	assertValid();
	}

	/**
	Clears the heap. Returns the portion of the store from `0` up to
	`length`, which satisfies the $(LINK2 https://en.wikipedia.org/wiki/Heap_(data_structure),
	heap property).
	*/
	auto release()
	{
	if (!_payload.refCountedStore.isInitialized)
	{
	return typeof(_store[0 .. _length]).init;
	}
	assertValid();
	auto result = _store[0 .. _length];
	_payload = _payload.init;
	return result;
	}

	/**
	Returns `true` if the heap is _empty, `false` otherwise.
	*/
	@property bool empty()
	{
	return !length;
	}

	/**
	Returns a duplicate of the heap. The `dup` method is available only if the
	underlying store supports it.
	*/
	static if (is(typeof((Store s) { return s.dup; }(Store.init)) == Store))
	{
	@property BinaryHeap dup()
	{
	BinaryHeap result;
	if (!_payload.refCountedStore.isInitialized) return result;
	result.assume(_store.dup, length);
	return result;
	}
	}

	/**
	Returns the _length of the heap.
	*/
	@property size_t length()
	{
	return _payload.refCountedStore.isInitialized ? _length : 0;
	}

	/**
	Returns the _capacity of the heap, which is the length of the
	underlying store (if the store is a range) or the _capacity of the
	underlying store (if the store is a container).
	*/
	@property size_t capacity()
	{
	if (!_payload.refCountedStore.isInitialized) return 0;
	static if (is(typeof(_store.capacity) : size_t))
	{
	return _store.capacity;
	}
	else
	{
	return _store.length;
	}
	}

	/**
	Returns a copy of the _front of the heap, which is the largest element
	according to `less`.
	*/
	@property ElementType!Store front()
	{
	enforce(!empty, "Cannot call front on an empty heap.");
	return _store.front;
	}

	/**
	Clears the heap by detaching it from the underlying store.
	*/
	void clear()
	{
	_payload = _payload.init;
	}

	/**
	Inserts `value` into the store. If the underlying store is a range
	and $(D length == capacity), throws an exception.
	*/
	size_t insert(ElementType!Store value)
	{
	static if (is(typeof(_store.insertBack(value))))
	{
	_payload.refCountedStore.ensureInitialized();
	if (length == _store.length)
	{
	// reallocate
	_store.insertBack(value);
	}
	else
	{
	// no reallocation
	_store[_length] = value;
	}
	}
	else
	{
	import std.traits : isDynamicArray;
	static if (isDynamicArray!Store)
	{
	if (length == _store.length)
	_store.length = (length < 6 ? 8 : length * 3 / 2);
	_store[_length] = value;
	}
	else
	{
	// can't grow
	enforce(length < _store.length,
	"Cannot grow a heap created over a range");
	}
	}

	// sink down the element
	for (size_t n = _length; n; )
	{
	auto parentIdx = (n - 1) / 2;
	if (!comp(_store[parentIdx], _store[n])) break; // done!
	// must swap and continue
	_store.swapAt(parentIdx, n);
	n = parentIdx;
	}
	++_length;
	debug(BinaryHeap) assertValid();
	return 1;
	}

	/**
	Removes the largest element from the heap.
	*/
	void removeFront()
	{
	enforce(!empty, "Cannot call removeFront on an empty heap.");
	if (_length > 1)
	{
	auto t1 = _store[].moveFront();
	auto t2 = _store[].moveAt(_length - 1);
	_store.front = move(t2);
	_store[_length - 1] = move(t1);
	}
	--_length;
	percolate(_store[], 0, _length);
	}

	/// ditto
	alias popFront = removeFront;

	/**
	Removes the largest element from the heap and returns a copy of
	it. The element still resides in the heap's store. For performance
	reasons you may want to use `removeFront` with heaps of objects
	that are expensive to copy.
	*/
	ElementType!Store removeAny()
	{
	removeFront();
	return _store[_length];
	}

	/**
	Replaces the largest element in the store with `value`.
	*/
	void replaceFront(ElementType!Store value)
	{
	// must replace the top
	assert(!empty, "Cannot call replaceFront on an empty heap.");
	_store.front = value;
	percolate(_store[], 0, _length);
	debug(BinaryHeap) assertValid();
	}

	/**
	If the heap has room to grow, inserts `value` into the store and
	returns `true`. Otherwise, if $(D less(value, front)), calls $(D
	replaceFront(value)) and returns again `true`. Otherwise, leaves
	the heap unaffected and returns `false`. This method is useful in
	scenarios where the smallest `k` elements of a set of candidates
	must be collected.
	*/
	bool conditionalInsert(ElementType!Store value)
	{
	_payload.refCountedStore.ensureInitialized();
	if (_length < _store.length)
	{
	insert(value);
	return true;
	}

	assert(!_store.empty, "Cannot replace front of an empty heap.");
	if (!comp(value, _store.front)) return false; // value >= largest
	_store.front = value;

	percolate(_store[], 0, _length);
	debug(BinaryHeap) assertValid();
	return true;
	}

	/**
	Swapping is allowed if the heap is full. If $(D less(value, front)), the
	method exchanges store.front and value and returns `true`. Otherwise, it
	leaves the heap unaffected and returns `false`.
	*/
	bool conditionalSwap(ref ElementType!Store value)
	{
	_payload.refCountedStore.ensureInitialized();
	assert(_length == _store.length,
	"length and number of stored items out of sync");
	assert(!_store.empty, "Cannot swap front of an empty heap.");

	if (!comp(value, _store.front)) return false; // value >= largest

	import std.algorithm.mutation : swap;
	swap(_store.front, value);

	percolate(_store[], 0, _length);
	debug(BinaryHeap) assertValid();

	return true;
	}
	}

	/// Example from "Introduction to Algorithms" Cormen et al, p 146
	@system unittest
	{
	import std.algorithm.comparison : equal;
	int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
	auto h = heapify(a);
	// largest element
	assert(h.front == 16);
	// a has the heap property
	assert(equal(a, [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]));
	}

	/// `BinaryHeap` implements the standard input range interface, allowing
	/// lazy iteration of the underlying range in descending order.
	@system unittest
	{
	import std.algorithm.comparison : equal;
	import std.range : take;
	int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
	auto top5 = heapify(a).take(5);
	assert(top5.equal([16, 14, 10, 9, 8]));
	}

	/**
	Convenience function that returns a `BinaryHeap!Store` object
	initialized with `s` and `initialSize`.
	*/
	BinaryHeap!(Store, less) heapify(alias less = "a < b", Store)(Store s,
	size_t initialSize = size_t.max)
	{

	return BinaryHeap!(Store, less)(s, initialSize);
	}

	///
	@system unittest
	{
	import std.conv : to;
	import std.range.primitives;
	{
	// example from "Introduction to Algorithms" Cormen et al., p 146
	int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
	auto h = heapify(a);
	h = heapify!"a < b"(a);
	assert(h.front == 16);
	assert(a == [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]);
	auto witness = [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ];
	for (; !h.empty; h.removeFront(), witness.popFront())
	{
	assert(!witness.empty);
	assert(witness.front == h.front);
	}
	assert(witness.empty);
	}
	{
	int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
	int[] b = new int[a.length];
	BinaryHeap!(int[]) h = BinaryHeap!(int[])(b, 0);
	foreach (e; a)
	{
	h.insert(e);
	}
	assert(b == [ 16, 14, 10, 8, 7, 3, 9, 1, 4, 2 ], to!string(b));
	}
	}

	@system unittest
	{
	// Test range interface.
	import std.algorithm.comparison : equal;
	int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
	auto h = heapify(a);
	static assert(isInputRange!(typeof(h)));
	assert(h.equal([16, 14, 10, 9, 8, 7, 4, 3, 2, 1]));
	}

	// https://issues.dlang.org/show_bug.cgi?id=15675
	@system unittest
	{
	import std.container.array : Array;

	Array!int elements = [1, 2, 10, 12];
	auto heap = heapify(elements);
	assert(heap.front == 12);
	}

	// https://issues.dlang.org/show_bug.cgi?id=16072
	@system unittest
	{
	auto q = heapify!"a > b"([2, 4, 5]);
	q.insert(1);
	q.insert(6);
	assert(q.front == 1);

	// test more multiple grows
	int[] arr;
	auto r = heapify!"a < b"(arr);
	foreach (i; 0 .. 100)
	r.insert(i);

	assert(r.front == 99);
	}

	@system unittest
	{
	import std.algorithm.comparison : equal;
	int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
	auto heap = heapify(a);
	auto dup = heap.dup();
	assert(dup.equal([16, 14, 10, 9, 8, 7, 4, 3, 2, 1]));
	}

	@safe unittest
	{
	static struct StructWithoutDup
	{
	int[] a;
	@disable StructWithoutDup dup();
	alias a this;
	}

	// Assert Binary heap can be created when Store doesn't have dup
	// if dup is not used.
	assert(__traits(compiles, ()
	{
	auto s = StructWithoutDup([1,2]);
	auto h = heapify(s);
	}));

	// Assert dup can't be used on BinaryHeaps when Store doesn't have dup
	assert(!__traits(compiles, ()
	{
	auto s = StructWithoutDup([1,2]);
	auto h = heapify(s);
	h.dup();
	}));
	}

	@safe unittest
	{
	static struct StructWithDup
	{
	int[] a;
	StructWithDup dup()
	{
	StructWithDup d;
	return d;
	}
	alias a this;
	}

	// Assert dup can be used on BinaryHeaps when Store has dup
	assert(__traits(compiles, ()
	{
	auto s = StructWithDup([1, 2]);
	auto h = heapify(s);
	h.dup();
	}));
	}

	@system unittest
	{
	import std.algorithm.comparison : equal;
	import std.internal.test.dummyrange;

	alias RefRange = DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random);

	RefRange a;
	RefRange b;
	a.reinit();
	b.reinit();

	auto heap = heapify(a);
	foreach (ref elem; b)
	{
	heap.conditionalSwap(elem);
	}

	assert(equal(heap, [ 5, 5, 4, 4, 3, 3, 2, 2, 1, 1]));
	assert(equal(b, [10, 9, 8, 7, 6, 6, 7, 8, 9, 10]));
	}

	// https://issues.dlang.org/show_bug.cgi?id=17314
	@system unittest
	{
	import std.algorithm.comparison : equal;
	int[] a = [5];
	auto heap = heapify(a);
	heap.insert(6);
	assert(equal(heap, [6, 5]));
	}