heapify

Convenience function that returns a BinaryHeap!Store object initialized with s and initialSize.

BinaryHeap!(Store, less)

heapify

(

alias less = "a < b"

Store

)

(

Store s

size_t initialSize = size_t.max

)

Examples

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);
    assert(h.front == 16);
    assert(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);
        assert(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);
    }
    assert(b == [ 16, 14, 10, 8, 7, 3, 9, 1, 4, 2 ], to!string(b));
}

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;
assert(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;
assert(h.front() == 40);

The OpenD Programming Language

heapify

Examples

Meta

Source