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 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 137 public: 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 /** 153 Takes ownership of a store. After this, manipulating `s` may make 154 the 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 /** 167 Takes ownership of a store assuming it already was organized as a 168 heap. 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 /** 179 Clears 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), 181 heap 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 /** 196 Returns `true` if the heap is _empty, `false` otherwise. 197 */ 198 @property bool empty() 199 { 200 return !length; 201 } 202 203 /** 204 Returns a duplicate of the heap. The `dup` method is available only if the 205 underlying 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 /** 219 Returns the _length of the heap. 220 */ 221 @property size_t length() 222 { 223 return _payload.refCountedStore.isInitialized ? _length : 0; 224 } 225 226 /** 227 Returns the _capacity of the heap, which is the length of the 228 underlying store (if the store is a range) or the _capacity of the 229 underlying 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 /** 245 Returns a copy of the _front of the heap, which is the largest element 246 according 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 /** 255 Clears the heap by detaching it from the underlying store. 256 */ 257 void clear() 258 { 259 _payload = _payload.init; 260 } 261 262 /** 263 Inserts `value` into the store. If the underlying store is a range 264 and $(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 /** 314 Removes 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 /** 334 Removes the largest element from the heap and returns a copy of 335 it. The element still resides in the heap's store. For performance 336 reasons you may want to use `removeFront` with heaps of objects 337 that are expensive to copy. 338 */ 339 ElementType!Store removeAny() 340 { 341 removeFront(); 342 return _store[_length]; 343 } 344 345 /** 346 Replaces 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 /** 358 If the heap has room to grow, inserts `value` into the store and 359 returns `true`. Otherwise, if $(D less(value, front)), calls $(D 360 replaceFront(value)) and returns again `true`. Otherwise, leaves 361 the heap unaffected and returns `false`. This method is useful in 362 scenarios where the smallest `k` elements of a set of candidates 363 must 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 /** 384 Swapping is allowed if the heap is full. If $(D less(value, front)), the 385 method exchanges store.front and value and returns `true`. Otherwise, it 386 leaves 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 /** 431 Convenience function that returns a `BinaryHeap!Store` object 432 initialized with `s` and `initialSize`. 433 */ 434 BinaryHeap!(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 }