kone.collections/dev.lounres.kone.collections.heap/MinimumHeap

MinimumHeap

interface MinimumHeap<Element, Priority>(source)

In Kone, minimum heap is a structure that consists of:

an order on values called "priorities" (thus, heap is contextful)
and a tree (in computer science sense of the word) that holds one priority value and one "element" value in each its vertex and satisfies heap property: for any given vertex \(C\), if \(P\) is the parent vertex of \(C\), then the priority of \(P\) is less than or equal to the priority of \(C\).

This interface's inheritors must have some specific structure that provides optimized minimum node access. Without it (or with bad time complexity like \(O(n)\)) the interface should not be used.

Inheritors

LinkedMinimumHeap

KoneBinaryGCMinimumHeap

KoneBinaryListBackedMinimumHeap

KoneFibonacciGCMinimumHeap

Properties

abstract val elementsView: KoneRemovableIterable<Element>

Iterable that is a view on elements of the heap.

val <Element, Priority> MinimumHeap<Element, Priority>.nodes: KoneReifiedSet<HeapNode<Element, Priority>>

abstract val nodesView: KoneRemovableReifiedSet<HeapNode<Element, Priority>>

Reified set that is a view on nodes of that heap.

abstract val prioritiesView: KoneRemovableIterable<Priority>

Iterable that is a view on priorities of the heap.

abstract val size: UInt

Number of elements in the collection.

Functions

@IgnorableReturnValue

abstract fun add(element: Element, priority: Priority): HeapNode<Element, Priority>

Adds the element with corresponding priority to the heap and returns constructed node that corresponds to the element and the priority.

abstract operator override fun equals(other: Any?): Boolean

Legacy equality operation. Must return the result of referential equality.

abstract override fun hashCode(): Int

Legacy hash computation operation. Must return any Int value.

fun MinimumHeap<*, *>.isEmpty(): Boolean

Checks if the heap is empty.

fun MinimumHeap<*, *>.isNotEmpty(): Boolean

Checks if the heap is not empty.

@IgnorableReturnValue

abstract fun popMinimum(): HeapNode<Element, Priority>

Retrieves the root node and removes it from the heap. It is a node with the minimum priority.

abstract fun takeMinimum(): HeapNode<Element, Priority>

Retrieves the root node. It is a node with the minimum priority.

abstract override fun toString(): String

Represents the heap as a string. Must return a string in the following form.