1 /**
2 This module provides a `BinaryHeap` (aka priority queue)
3 adaptor that makes a binary heap out of any user-provided random-access range.
4 
5 This module is a submodule of $(MREF std, container).
6 
7 Source: $(PHOBOSSRC std/container/binaryheap.d)
8 
9 Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
10 
11 License: Distributed under the Boost Software License, Version 1.0.
12 (See accompanying file LICENSE_1_0.txt or copy at $(HTTP
13 boost.org/LICENSE_1_0.txt)).
14 
15 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
16 */
17 module std.container.binaryheap;
18 
19 import std.range.primitives;
20 import std.traits;
21 
22 public import std.container.util;
23 
24 ///
25 @system unittest
26 {
27     import std.algorithm.comparison : equal;
28     import std.range : take;
29     auto maxHeap = heapify([4, 7, 3, 1, 5]);
30     assert(maxHeap.take(3).equal([7, 5, 4]));
31 
32     auto minHeap = heapify!"a > b"([4, 7, 3, 1, 5]);
33     assert(minHeap.take(3).equal([1, 3, 4]));
34 }
35 
36 // BinaryHeap
37 /**
38 Implements a $(HTTP en.wikipedia.org/wiki/Binary_heap, binary heap)
39 container on top of a given random-access range type (usually $(D
40 T[])) or a random-access container type (usually `Array!T`). The
41 documentation of `BinaryHeap` will refer to the underlying range or
42 container as the $(I store) of the heap.
43 
44 The binary heap induces structure over the underlying store such that
45 accessing the largest element (by using the `front` property) is a
46 $(BIGOH 1) operation and extracting it (by using the $(D
47 removeFront()) method) is done fast in $(BIGOH log n) time.
48 
49 If `less` is the less-than operator, which is the default option,
50 then `BinaryHeap` defines a so-called max-heap that optimizes
51 extraction of the $(I largest) elements. To define a min-heap,
52 instantiate BinaryHeap with $(D "a > b") as its predicate.
53 
54 Simply extracting elements from a `BinaryHeap` container is
55 tantamount to lazily fetching elements of `Store` in descending
56 order. Extracting elements from the `BinaryHeap` to completion
57 leaves the underlying store sorted in ascending order but, again,
58 yields elements in descending order.
59 
60 If `Store` is a range, the `BinaryHeap` cannot grow beyond the
61 size of that range. If `Store` is a container that supports $(D
62 insertBack), the `BinaryHeap` may grow by adding elements to the
63 container.
64      */
65 struct BinaryHeap(Store, alias less = "a < b")
66 if (isRandomAccessRange!(Store) || isRandomAccessRange!(typeof(Store.init[])))
67 {
68     import std.algorithm.comparison : min;
69     import std.algorithm.mutation : move, swapAt;
70     import std.algorithm.sorting : HeapOps;
71     import std.exception : enforce;
72     import std.functional : binaryFun;
73     import std.typecons : RefCounted, RefCountedAutoInitialize;
74 
75     static if (isRandomAccessRange!Store)
76         alias Range = Store;
77     else
78         alias Range = typeof(Store.init[]);
79     alias percolate = HeapOps!(less, Range).percolate;
80     alias buildHeap = HeapOps!(less, Range).buildHeap;
81 
82 // Really weird @@BUG@@: if you comment out the "private:" label below,
83 // std.algorithm can't unittest anymore
84 //private:
85 
86     // The payload includes the support store and the effective length
87     private static struct Data
88     {
89         Store _store;
90         size_t _length;
91     }
92     // TODO: migrate to use the SafeRefCounted. The problem is that some member
93     // functions here become @system with a naive switch.
94     private RefCounted!(Data, RefCountedAutoInitialize.no) _payload;
95     // Comparison predicate
96     private alias comp = binaryFun!(less);
97     // Convenience accessors
98     private @property ref Store _store()
99     {
100         assert(_payload.refCountedStore.isInitialized,
101                 "BinaryHeap not initialized");
102         return _payload._store;
103     }
104     private @property ref size_t _length()
105     {
106         assert(_payload.refCountedStore.isInitialized,
107                 "BinaryHeap not initialized");
108         return _payload._length;
109     }
110 
111     // Asserts that the heap property is respected.
112     private void assertValid()
113     {
114         debug
115         {
116             import std.conv : to;
117             if (!_payload.refCountedStore.isInitialized) return;
118             if (_length < 2) return;
119             for (size_t n = _length - 1; n >= 1; --n)
120             {
121                 auto parentIdx = (n - 1) / 2;
122                 assert(!comp(_store[parentIdx], _store[n]), to!string(n));
123             }
124         }
125     }
126 
127     // @@@BUG@@@: add private here, std.algorithm doesn't unittest anymore
128     /*private*/ void pop(Store store)
129     {
130         assert(!store.empty, "Cannot pop an empty store.");
131         if (store.length == 1) return;
132         auto t1 = store[].moveFront();
133         auto t2 = store[].moveBack();
134         store.front = move(t2);
135         store.back = move(t1);
136         percolate(store[], 0, store.length - 1);
137     }
138 
139 public:
140 
141     /**
142        Converts the store `s` into a heap. If `initialSize` is
143        specified, only the first `initialSize` elements in `s`
144        are transformed into a heap, after which the heap can grow up
145        to `r.length` (if `Store` is a range) or indefinitely (if
146        `Store` is a container with `insertBack`). Performs
147        $(BIGOH min(r.length, initialSize)) evaluations of `less`.
148      */
149     this(Store s, size_t initialSize = size_t.max)
150     {
151         acquire(s, initialSize);
152     }
153 
154 /**
155 Takes ownership of a store. After this, manipulating `s` may make
156 the heap work incorrectly.
157      */
158     void acquire(Store s, size_t initialSize = size_t.max)
159     {
160         _payload.refCountedStore.ensureInitialized();
161         _store = move(s);
162         _length = min(_store.length, initialSize);
163         if (_length < 2) return;
164         buildHeap(_store[]);
165         assertValid();
166     }
167 
168 /**
169 Takes ownership of a store assuming it already was organized as a
170 heap.
171      */
172     void assume(Store s, size_t initialSize = size_t.max)
173     {
174         _payload.refCountedStore.ensureInitialized();
175         _store = s;
176         _length = min(_store.length, initialSize);
177         assertValid();
178     }
179 
180 /**
181 Clears the heap. Returns the portion of the store from `0` up to
182 `length`, which satisfies the $(LINK2 https://en.wikipedia.org/wiki/Heap_(data_structure),
183 heap property).
184      */
185     auto release()
186     {
187         if (!_payload.refCountedStore.isInitialized)
188         {
189             return typeof(_store[0 .. _length]).init;
190         }
191         assertValid();
192         auto result = _store[0 .. _length];
193         _payload = _payload.init;
194         return result;
195     }
196 
197 /**
198 Returns `true` if the heap is _empty, `false` otherwise.
199      */
200     @property bool empty()
201     {
202         return !length;
203     }
204 
205 /**
206 Returns a duplicate of the heap. The `dup` method is available only if the
207 underlying store supports it.
208      */
209     static if (is(typeof((Store s) { return s.dup; }(Store.init)) == Store))
210     {
211         @property BinaryHeap dup()
212         {
213             BinaryHeap result;
214             if (!_payload.refCountedStore.isInitialized) return result;
215             result.assume(_store.dup, length);
216             return result;
217         }
218     }
219 
220 /**
221 Returns the _length of the heap.
222      */
223     @property size_t length()
224     {
225         return _payload.refCountedStore.isInitialized ? _length : 0;
226     }
227 
228 /**
229 Returns the _capacity of the heap, which is the length of the
230 underlying store (if the store is a range) or the _capacity of the
231 underlying store (if the store is a container).
232      */
233     @property size_t capacity()
234     {
235         if (!_payload.refCountedStore.isInitialized) return 0;
236         static if (is(typeof(_store.capacity) : size_t))
237         {
238             return _store.capacity;
239         }
240         else
241         {
242             return _store.length;
243         }
244     }
245 
246 /**
247 Returns a copy of the _front of the heap, which is the largest element
248 according to `less`.
249      */
250     @property ElementType!Store front()
251     {
252         assert(!empty, "Cannot call front on an empty heap.");
253         return _store.front;
254     }
255 
256 /**
257 Clears the heap by detaching it from the underlying store.
258      */
259     void clear()
260     {
261         _payload = _payload.init;
262     }
263 
264 /**
265 Inserts `value` into the store. If the underlying store is a range
266 and $(D length == capacity), throws an exception.
267      */
268     size_t insert(ElementType!Store value)
269     {
270         static if (is(typeof(_store.insertBack(value))))
271         {
272             _payload.refCountedStore.ensureInitialized();
273             if (length == _store.length)
274             {
275                 // reallocate
276                 _store.insertBack(value);
277             }
278             else
279             {
280                 // no reallocation
281                 _store[_length] = value;
282             }
283         }
284         else
285         {
286             import std.traits : isDynamicArray;
287             static if (isDynamicArray!Store)
288             {
289                 if (length == _store.length)
290                     _store.length = (length < 6 ? 8 : length * 3 / 2);
291                 _store[_length] = value;
292             }
293             else
294             {
295                 // can't grow
296                 enforce(length < _store.length,
297                         "Cannot grow a heap created over a range");
298             }
299         }
300 
301         // sink down the element
302         for (size_t n = _length; n; )
303         {
304             auto parentIdx = (n - 1) / 2;
305             if (!comp(_store[parentIdx], _store[n])) break; // done!
306             // must swap and continue
307             _store.swapAt(parentIdx, n);
308             n = parentIdx;
309         }
310         ++_length;
311         debug(BinaryHeap) assertValid();
312         return 1;
313     }
314 
315 /**
316 Removes the largest element from the heap.
317      */
318     void removeFront()
319     {
320         assert(!empty, "Cannot call removeFront on an empty heap.");
321         if (_length > 1)
322         {
323             auto t1 = _store[].moveFront();
324             auto t2 = _store[].moveAt(_length - 1);
325             _store.front = move(t2);
326             _store[_length - 1] = move(t1);
327         }
328         --_length;
329         percolate(_store[], 0, _length);
330     }
331 
332     /// ditto
333     alias popFront = removeFront;
334 
335 /**
336 Removes the largest element from the heap and returns a copy of
337 it. The element still resides in the heap's store. For performance
338 reasons you may want to use `removeFront` with heaps of objects
339 that are expensive to copy.
340      */
341     ElementType!Store removeAny()
342     {
343         removeFront();
344         return _store[_length];
345     }
346 
347 /**
348 Replaces the largest element in the store with `value`.
349      */
350     void replaceFront(ElementType!Store value)
351     {
352         // must replace the top
353         assert(!empty, "Cannot call replaceFront on an empty heap.");
354         _store.front = value;
355         percolate(_store[], 0, _length);
356         debug(BinaryHeap) assertValid();
357     }
358 
359 /**
360 If the heap has room to grow, inserts `value` into the store and
361 returns `true`. Otherwise, if $(D less(value, front)), calls $(D
362 replaceFront(value)) and returns again `true`. Otherwise, leaves
363 the heap unaffected and returns `false`. This method is useful in
364 scenarios where the smallest `k` elements of a set of candidates
365 must be collected.
366      */
367     bool conditionalInsert(ElementType!Store value)
368     {
369         _payload.refCountedStore.ensureInitialized();
370         if (_length < _store.length)
371         {
372             insert(value);
373             return true;
374         }
375 
376         assert(!_store.empty, "Cannot replace front of an empty heap.");
377         if (!comp(value, _store.front)) return false; // value >= largest
378         _store.front = value;
379 
380         percolate(_store[], 0, _length);
381         debug(BinaryHeap) assertValid();
382         return true;
383     }
384 
385 /**
386 Swapping is allowed if the heap is full. If $(D less(value, front)), the
387 method exchanges store.front and value and returns `true`. Otherwise, it
388 leaves the heap unaffected and returns `false`.
389      */
390     bool conditionalSwap(ref ElementType!Store value)
391     {
392         _payload.refCountedStore.ensureInitialized();
393         assert(_length == _store.length,
394                 "length and number of stored items out of sync");
395         assert(!_store.empty, "Cannot swap front of an empty heap.");
396 
397         if (!comp(value, _store.front)) return false; // value >= largest
398 
399         import std.algorithm.mutation : swap;
400         swap(_store.front, value);
401 
402         percolate(_store[], 0, _length);
403         debug(BinaryHeap) assertValid();
404 
405         return true;
406     }
407 }
408 
409 /// Example from "Introduction to Algorithms" Cormen et al, p 146
410 @system unittest
411 {
412     import std.algorithm.comparison : equal;
413     int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
414     auto h = heapify(a);
415     // largest element
416     assert(h.front == 16);
417     // a has the heap property
418     assert(equal(a, [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]));
419 }
420 
421 /// `BinaryHeap` implements the standard input range interface, allowing
422 /// lazy iteration of the underlying range in descending order.
423 @system unittest
424 {
425     import std.algorithm.comparison : equal;
426     import std.range : take;
427     int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
428     auto top5 = heapify(a).take(5);
429     assert(top5.equal([16, 14, 10, 9, 8]));
430 }
431 
432 /**
433 Convenience function that returns a `BinaryHeap!Store` object
434 initialized with `s` and `initialSize`.
435  */
436 BinaryHeap!(Store, less) heapify(alias less = "a < b", Store)(Store s,
437         size_t initialSize = size_t.max)
438 {
439 
440     return BinaryHeap!(Store, less)(s, initialSize);
441 }
442 
443 ///
444 @system unittest
445 {
446     import std.conv : to;
447     import std.range.primitives;
448     {
449         // example from "Introduction to Algorithms" Cormen et al., p 146
450         int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
451         auto h = heapify(a);
452         h = heapify!"a < b"(a);
453         assert(h.front == 16);
454         assert(a == [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]);
455         auto witness = [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ];
456         for (; !h.empty; h.removeFront(), witness.popFront())
457         {
458             assert(!witness.empty);
459             assert(witness.front == h.front);
460         }
461         assert(witness.empty);
462     }
463     {
464         int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
465         int[] b = new int[a.length];
466         BinaryHeap!(int[]) h = BinaryHeap!(int[])(b, 0);
467         foreach (e; a)
468         {
469             h.insert(e);
470         }
471         assert(b == [ 16, 14, 10, 8, 7, 3, 9, 1, 4, 2 ], to!string(b));
472     }
473 }
474 
475 @system unittest
476 {
477     // Test range interface.
478     import std.algorithm.comparison : equal;
479     int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
480     auto h = heapify(a);
481     static assert(isInputRange!(typeof(h)));
482     assert(h.equal([16, 14, 10, 9, 8, 7, 4, 3, 2, 1]));
483 }
484 
485 // https://issues.dlang.org/show_bug.cgi?id=15675
486 @system unittest
487 {
488     import std.container.array : Array;
489 
490     Array!int elements = [1, 2, 10, 12];
491     auto heap = heapify(elements);
492     assert(heap.front == 12);
493 }
494 
495 // https://issues.dlang.org/show_bug.cgi?id=16072
496 @system unittest
497 {
498     auto q = heapify!"a > b"([2, 4, 5]);
499     q.insert(1);
500     q.insert(6);
501     assert(q.front == 1);
502 
503     // test more multiple grows
504     int[] arr;
505     auto r = heapify!"a < b"(arr);
506     foreach (i; 0 .. 100)
507         r.insert(i);
508 
509     assert(r.front == 99);
510 }
511 
512 @system unittest
513 {
514     import std.algorithm.comparison : equal;
515     int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
516     auto heap = heapify(a);
517     auto dup = heap.dup();
518     assert(dup.equal([16, 14, 10, 9, 8, 7, 4, 3, 2, 1]));
519 }
520 
521 @safe unittest
522 {
523     static struct StructWithoutDup
524     {
525         int[] a;
526         @disable StructWithoutDup dup();
527         alias a this;
528     }
529 
530     // Assert Binary heap can be created when Store doesn't have dup
531     // if dup is not used.
532     assert(__traits(compiles, ()
533         {
534             auto s = StructWithoutDup([1,2]);
535             auto h = heapify(s);
536         }));
537 
538     // Assert dup can't be used on BinaryHeaps when Store doesn't have dup
539     assert(!__traits(compiles, ()
540         {
541             auto s = StructWithoutDup([1,2]);
542             auto h = heapify(s);
543             h.dup();
544         }));
545 }
546 
547 @safe unittest
548 {
549     static struct StructWithDup
550     {
551         int[] a;
552         StructWithDup dup()
553         {
554             StructWithDup d;
555             return d;
556         }
557         alias a this;
558     }
559 
560     // Assert dup can be used on BinaryHeaps when Store has dup
561     assert(__traits(compiles, ()
562         {
563             auto s = StructWithDup([1, 2]);
564             auto h = heapify(s);
565             h.dup();
566         }));
567 }
568 
569 @system unittest
570 {
571     import std.algorithm.comparison : equal;
572     import std.internal.test.dummyrange;
573 
574     alias RefRange = DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random);
575 
576     RefRange a;
577     RefRange b;
578     a.reinit();
579     b.reinit();
580 
581     auto heap = heapify(a);
582     foreach (ref elem; b)
583     {
584         heap.conditionalSwap(elem);
585     }
586 
587     assert(equal(heap, [ 5, 5, 4, 4, 3, 3, 2, 2, 1, 1]));
588     assert(equal(b, [10, 9, 8, 7, 6, 6, 7, 8, 9, 10]));
589 }
590 
591 // https://issues.dlang.org/show_bug.cgi?id=17314
592 @system unittest
593 {
594     import std.algorithm.comparison : equal;
595     int[] a = [5];
596     auto heap = heapify(a);
597     heap.insert(6);
598     assert(equal(heap, [6, 5]));
599 }
600 
601 /**
602 Example for unintuitive behaviour
603 It is important not to use the Store after a Heap has been instantiated from
604 it, at least in the cases of Dynamic Arrays. For example, inserting a new element
605 in a Heap, which is using a Dyamic Array as a Store, will cause a reallocation of
606 the Store, if the Store is already full. The Heap will not point anymore to the
607 original Dyamic Array, but point to a new Dynamic Array.
608  */
609 
610 // https://issues.dlang.org/show_bug.cgi?id=18333
611 @system unittest
612 {
613     import std.stdio;
614     import std.algorithm.comparison : equal;
615     import std.container.binaryheap;
616 
617     int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
618     auto h = heapify(a);
619 
620     // Internal representation of Binary Heap tree
621     assert(a.equal([16, 14, 10, 8, 7, 9, 3, 2, 4, 1]));
622 
623     h.replaceFront(30);
624     // Value 16 was replaced by 30
625     assert(a.equal([30, 14, 10, 8, 7, 9, 3, 2, 4, 1]));
626 
627     // Making changes to the Store will be seen in the Heap
628     a[0] = 40;
629     assert(h.front() == 40);
630 
631     // Inserting a new element will reallocate the Store, leaving
632     // the original Store unchanged.
633     h.insert(20);
634     assert(a.equal([40, 14, 10, 8, 7, 9, 3, 2, 4, 1]));
635 
636     // Making changes to the original Store will not affect the Heap anymore
637     a[0] = 60;
638     assert(h.front() == 40);
639 }