kone.collections/dev.lounres.kone.collections.heap/MaximumHeap

MaximumHeap

interface MaximumHeap<Element, Priority>(source)

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

  1. an order on values called "priorities" (thus, heap is contextful)

  2. 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 greater than or equal to the priority of \(C\).

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

Inheritors

Properties

Link copied to clipboard
abstract val elementsView: KoneIterable<Element>

Iterable that is a view on elements of that heap.

Link copied to clipboard
abstract val nodesView: KoneReifiedSet<HeapNode<Element, Priority>>

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

Link copied to clipboard
abstract val size: UInt

Number of elements in the collection.

Functions

Link copied to clipboard
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.

Link copied to clipboard
abstract fun popMaximum(): HeapNode<Element, Priority>

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

Link copied to clipboard
abstract fun takeMaximum(): HeapNode<Element, Priority>

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