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 }