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