trait Heap[A] extends Cloneable[Heap[A]]
D-way Heap
The default branching factor is four, which might work in most cases. To create a heap with a different branching factor, use Heap.withBranchingFactor.
There must be implicit scala.math.Ordering available at creation for prioritizing elements. An element with higher order is considered a higher priority.
It's not allowed to insert the same elements. Two elements are considered the same if both have the same hash code. If the same element is inserted, the existing one will be removed. In this case, the priority of the element will update if the new element has a different priority.
As some limitations applied, this heap supports removing the element from any position on logarithmic time.
- A
The type of elements in the heap
- Alphabetic
- By Inheritance
- Heap
- Cloneable
- Cloneable
- AnyRef
- Any
- Hide All
- Show All
- Public
- Protected
Abstract Value Members
- abstract def branchingFactor: Int
Returns the branching factor of this heap
Returns the branching factor of this heap
- Note
Time Complexity: O(1)
- abstract def clear(): Heap.this.type
Removes all elements from this heap
Removes all elements from this heap
- Note
Time Complexity: O(1)
- abstract def contains(value: A): Boolean
Returns true if this heap contains the given value
Returns true if this heap contains the given value
- Note
Time Complexity: O(1)
- abstract def isEmpty: Boolean
Returns true if this heap is empty
Returns true if this heap is empty
- Note
Time Complexity: O(1)
- abstract def nonEmpty: Boolean
Returns true if this heap is not empty
Returns true if this heap is not empty
- Note
Time Complexity: O(1)
- abstract def ordering: Ordering[A]
Returns the ordering of this heap
Returns the ordering of this heap
- Note
Time Complexity: O(1)
- abstract def pop(): A
Removes and returns the element with the highest priority from this heap
Removes and returns the element with the highest priority from this heap
- Exceptions thrown
java.util.NoSuchElementExceptionif this heap is empty- Note
Time Complexity: O(log n) amortized
- abstract def popAll(): IndexedSeq[A]
Removes and returns all elements in priority order from this heap
Removes and returns all elements in priority order from this heap
- Note
Time Complexity: O(n log n)
- abstract def push(value: A): Heap.this.type
Inserts the given value into this heap
Inserts the given value into this heap
If the given value already exists in this heap, the element will be inserted again. The existing one will be removed.
- Note
Time Complexity: O(log n) amortized
- abstract def remove(value: A): Heap.this.type
Removes the give value from this heap
Removes the give value from this heap
If the given value is not in this heap, this method does nothing.
- Note
Time Complexity: O(log n) amortized
- abstract def reversed: Heap[A]
Returns the reverse of this heap
Returns the reverse of this heap
The reversed heap has the same elements of this heap, but the reverse ordering.
- Note
Time Complexity: O(n)
- abstract def size: Int
Returns the size of this heap
Returns the size of this heap
- Note
Time Complexity: O(1)
- abstract def top: A
Returns the element with the highest priority of this heap
Returns the element with the highest priority of this heap
- Exceptions thrown
java.util.NoSuchElementExceptionif this heap is empty- Note
Time Complexity: O(1)
- abstract def topOption: Option[A]
Returns the element with the highest priority of this heap
Returns the element with the highest priority of this heap
If this heap is empty, returns scala.None.
- Note
Time Complexity: O(1)
- abstract def update(oldValue: A, newValue: A): Heap.this.type
Removes the old value from this heap and inserts the new value into this heap
Removes the old value from this heap and inserts the new value into this heap
update(oldValue,newValue)is equivalent to the following calls but more efficient:remove(oldValue) push(newValue)
If the old value is not in this heap, this method skips the removal. If the new value already exists in this heap, this method inserts the new element again and removes the existing one.
- Note
Time Complexity: O(log n) amortized
Concrete Value Members
- final def !=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- final def ##: Int
- Definition Classes
- AnyRef → Any
- final def ==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- final def asInstanceOf[T0]: T0
- Definition Classes
- Any
- def clone(): Heap[A]
- Definition Classes
- Cloneable → AnyRef
- final def eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def equals(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef → Any
- final def getClass(): Class[_ <: AnyRef]
- Definition Classes
- AnyRef → Any
- Annotations
- @native() @HotSpotIntrinsicCandidate()
- def hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @native() @HotSpotIntrinsicCandidate()
- final def isInstanceOf[T0]: Boolean
- Definition Classes
- Any
- final def ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- final def notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native() @HotSpotIntrinsicCandidate()
- final def notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native() @HotSpotIntrinsicCandidate()
- final def synchronized[T0](arg0: => T0): T0
- Definition Classes
- AnyRef
- def toString(): String
- Definition Classes
- AnyRef → Any
- final def wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException]) @native()
- final def wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])