Heap

public struct Heap[T] where T: Comparable { /* private fields */ }

Binary min-heap backed by Array[T].

O(log n) push/pop, O(1) peek at the minimum element. Builds from an existing array in O(n) via Floyd's heapify. Iteration yields elements in storage order (NOT sorted order).

Examples

var h = Heap[Int64]();
h.push(5);
h.push(1);
h.push(3);
h.peek();   // .Some(1)
h.pop();    // .Some(1)
h.pop();    // .Some(3)

Representation

A single Array[T] field in standard binary-heap layout: the minimum lives at index 0, children of node i are at 2i + 1 and 2i + 2.

Memory Model

Delegates storage to Array[T], inheriting its COW value semantics. Copying a Heap is O(1); the first mutation on a shared copy triggers the array's copy-on-write barrier.

Guarantees

peek() always returns the minimum element.
After pop(), the next-smallest element becomes the new minimum.
Iteration order is unspecified (internal heap layout).

Properties

public var count: Int64 { get }

Number of elements in the heap.

Examples

let h = Heap(from: [3, 1, 2]);
h.count;  // 3

public var isEmpty: Bool { get }

True when the heap contains no elements.

Examples

Heap[Int64]().isEmpty;  // true
Heap(from: [1]).isEmpty;  // false

Initializers

public init()

Creates an empty min-heap with no allocation.

No heap memory is allocated until the first push. Use Heap(capacity:) to pre-allocate when the expected size is known.

Examples

var h = Heap[Int64]();
h.isEmpty;  // true

init(data: Array[T])

Internal constructor that wraps an existing array as the heap's backing store. Used by clone() to avoid a redundant heapify.

public init[I](from: I) where I: Iterable, I.Item == T

Builds a min-heap by collecting elements then heapifying in O(n).

All elements are first appended to the backing array, then Floyd's algorithm establishes the heap invariant in a single bottom-up pass. This is faster than pushing elements one at a time (O(n) vs O(n log n)).

Examples

let h = Heap(from: [5, 3, 1, 4, 2]);
h.peek();   // .Some(1)
h.count;    // 5

public init(capacity: Int64)

Creates an empty min-heap with at least capacity slots reserved.

Pre-allocates the backing array so that up to capacity elements can be pushed without triggering a reallocation.

Examples

var h = Heap[Int64](capacity: 100);
h.count;  // 0

Methods

public mutating func clear()

Removes all elements, retaining allocated capacity.

After calling clear(), count is 0 but the backing array keeps its buffer so subsequent push calls avoid reallocation.

Examples

var h = Heap(from: [3, 1, 2]);
h.clear();
h.isEmpty;  // true

public func peek() -> T?

Returns the minimum element without removing it. O(1).

Returns .None on an empty heap. The removing counterpart is pop().

Examples

let h = Heap(from: [3, 1, 2]);
h.peek();  // .Some(1)
Heap[Int64]().peek();  // .None

public mutating func pop() -> T?

Removes and returns the minimum element, or .None if empty. O(log n).

Swaps the root with the last element, removes the last, then sifts the new root down to restore the heap invariant. The non-removing mirror is peek().

Examples

var h = Heap(from: [3, 1, 2]);
h.pop();  // .Some(1)
h.pop();  // .Some(2)
h.pop();  // .Some(3)
h.pop();  // .None

public mutating func push(T)

Inserts element, maintaining the min-heap invariant. O(log n).

The element is appended to the backing array then sifted up to restore the heap property. Amortized O(log n) because the array may occasionally grow its buffer.

Examples

var h = Heap[Int64]();
h.push(3);
h.push(1);
h.peek();  // .Some(1)

public mutating func reserveCapacity(minimumCapacity: Int64)

Ensures the backing array can hold at least capacity elements without reallocating.

If the current capacity already meets or exceeds capacity, this is a no-op. Otherwise the backing array grows to accommodate the requested number of slots.

Examples

var h = Heap[Int64]();
h.reserveCapacity(minimumCapacity: 100);

ImplementsIterable

Associated Types

type Item = T

Iterable element type.

type TargetIterator = ArraySliceIterator[T]

Iterable iterator type — reuses the backing array's iterator.

Methods

public func iter() -> ArraySliceIterator[T]

Returns an iterator over elements in storage order (NOT sorted).

The iteration order reflects the internal heap layout, not the sorted order. To consume elements smallest-first, use pop() in a loop instead.

Examples

let h = Heap(from: [5, 3, 1]);
var iter = h.iter();
// yields elements in heap-array order, not 1, 3, 5

ImplementsCloneable

Methods

public func clone() -> Heap[T]

Returns a shallow copy of this heap. O(1).

The backing array's copy-on-write semantics mean the actual deep copy is deferred until the first mutation on either the original or the clone.

Examples

let h = Heap(from: [3, 1, 2]);
var h2 = h.clone();
h2.push(0);
h.peek();   // .Some(1) -- original unchanged
h2.peek();  // .Some(0)

Defined in lang/std/collections/heap.ks