View source code
Display the source code in std/container/binaryheap.d from which this
page was generated on github.
Report a bug
If you spot a problem with this page, click here to create a
Bugzilla issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page.
Requires a signed-in GitHub account. This works well for small changes.
If you'd like to make larger changes you may want to consider using
local clone.
Function std.container.binaryheap.heapify
Convenience function that returns a BinaryHeap!Store
object
initialized with s
and initialSize
.
Example
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);
writeln(h .front); // 16
writeln(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);
writeln(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);
}
writeln(b); // [16, 14, 10, 8, 7, 3, 9, 1, 4, 2]
}
Example
Example for unintuitive behaviour It is important not to use the Store after a Heap has been instantiated from it, at least in the cases of Dynamic Arrays. For example, inserting a new element in a Heap, which is using a Dyamic Array as a Store, will cause a reallocation of the Store, if the Store is already full. The Heap will not point anymore to the original Dyamic Array, but point to a new Dynamic Array.
import std .stdio;
import std .algorithm .comparison : equal;
import std .container .binaryheap;
int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
auto h = heapify(a);
// Internal representation of Binary Heap tree
assert(a .equal([16, 14, 10, 8, 7, 9, 3, 2, 4, 1]));
h .replaceFront(30);
// Value 16 was replaced by 30
assert(a .equal([30, 14, 10, 8, 7, 9, 3, 2, 4, 1]));
// Making changes to the Store will be seen in the Heap
a[0] = 40;
writeln(h .front()); // 40
// Inserting a new element will reallocate the Store, leaving
// the original Store unchanged.
h .insert(20);
assert(a .equal([40, 14, 10, 8, 7, 9, 3, 2, 4, 1]));
// Making changes to the original Store will not affect the Heap anymore
a[0] = 60;
writeln(h .front()); // 40
Authors
License
Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at ).
Copyright © 1999-2024 by the D Language Foundation | Page generated by ddox.