core/org.gnit.lucenekmp.util/LongHeap

LongHeap

class LongHeap(maxSize: Int)

A min heap that stores longs; a primitive priority queue that like all priority queues maintains a partial ordering of its elements such that the least element can always be found in constant time. Put()'s and pop()'s require log(size). This heap provides unbounded growth via .push, and bounded-size insertion based on its nominal maxSize via .insertWithOverflow. The heap is a min heap, meaning that the top element is the lowest value of the heap.

Constructors

LongHeap

constructor(maxSize: Int)

Properties

heapArray

var heapArray: LongArray

This method returns the internal heap array.

Functions

clear

fun clear()

Removes all entries from the PriorityQueue.

get

fun get(i: Int): Long

Return the element at the ith location in the heap array. Use for iterating over elements when the order doesn't matter. Note that the valid arguments range from 1, size.

insertWithOverflow

fun insertWithOverflow(value: Long): Boolean

Adds a value to an LongHeap in log(size) time. If the number of values would exceed the heap's maxSize, the least value is discarded.

pop

fun pop(): Long

Removes and returns the least element of the PriorityQueue in log(size) time.

push

fun push(element: Long): Long

Adds a value in log(size) time. Grows unbounded as needed to accommodate new values.

pushAll

fun pushAll(other: LongHeap)

size

fun size(): Int

Returns the number of elements currently stored in the PriorityQueue.

top

fun top(): Long

Returns the least element of the LongHeap in constant time. It is up to the caller to verify that the heap is not empty; no checking is done, and if no elements have been added, 0 is returned.

updateTop

fun updateTop(value: Long): Long

Replace the top of the pq with newTop. Should be called when the top value changes. Still log(n) worst case, but it's at least twice as fast to