Packages

abstract class LeftistHeap[T, HC <: HeapCollector[T, HC]] extends Iterable[T]

This class implements the leftist heap, see "Functional Data Structures" by Chris Okasaki

Linear Supertypes
Iterable[T], IterableFactoryDefaults[T, Iterable], IterableOps[T, Iterable, Iterable[T]], IterableOnceOps[T, Iterable, Iterable[T]], IterableOnce[T], AnyRef, Any
Known Subclasses
EmptyHeap, Node
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. LeftistHeap
  2. Iterable
  3. IterableFactoryDefaults
  4. IterableOps
  5. IterableOnceOps
  6. IterableOnce
  7. AnyRef
  8. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. Protected

Instance Constructors

  1. new LeftistHeap()(implicit ord: Ordering[T])

Abstract Value Members

  1. abstract def collector: HC

    Interface for collecting information about the elements stored in the heap

  2. abstract def deleteMin: LeftistHeap[T, HC]

    Remove the minimum element from this heap, or raise an exception iff this heap is empty (isEmpty()==true)

    Remove the minimum element from this heap, or raise an exception iff this heap is empty (isEmpty()==true)

    returns

    a heap that contains all elements of this heap except for the minimum element

  3. abstract def emptyHeap: LeftistHeap[T, HC]

    Construct an empty heap

    Construct an empty heap

    Attributes
    protected
  4. abstract def findMin: T

    returns

    the minimum element of this heap, or raise an exception iff this heap is empty (isEmpty()==true)

  5. abstract def flatItMapRec(f: (T) => Iterator[T], stop: (LeftistHeap[T, HC]) => Boolean): LeftistHeap[T, HC]

    Apply a function f to all elements in this heap.

    Apply a function f to all elements in this heap. The heap traversal is skipped for a subheap if the function stop applied to this subheap returns true. The function f can return null to signal that a data element has not changed.

  6. abstract def insert(element: T): LeftistHeap[T, HC]

    Add an element to this heap object

    Add an element to this heap object

    element

    The element to be added

    returns

    a heap that contains all elements of this heap, and additionally element

  7. abstract def insertHeap(h: LeftistHeap[T, HC]): LeftistHeap[T, HC]

    Add multiple elements to this heap object.

    Add multiple elements to this heap object. We keep this method protected, because otherwise one could use it to insert heaps that are sorted differently

    h

    a heap containing the elements to be added

    returns

    a heap that contains all elements of this heap, and additionally all objects from h

    Attributes
    protected[basetypes]
  8. abstract def removeAll(element: T): LeftistHeap[T, HC]

    Remove all elements of this heap which are equal to element.

    Remove all elements of this heap which are equal to element.

    returns

    heap that has all occurrences of element removed

  9. abstract def rightHeight: Int

    Length of the right spine, i.e.

    Length of the right spine, i.e. the length of the path from the root to rightmost leaf

Concrete Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##: Int
    Definition Classes
    AnyRef → Any
  3. def +(el: T): LeftistHeap[T, HC]
  4. def ++(els: Iterable[T]): LeftistHeap[T, HC]
  5. def ++(els: Iterator[T]): LeftistHeap[T, HC]
  6. final def ++[B >: T](suffix: IterableOnce[B]): Iterable[B]
    Definition Classes
    IterableOps
    Annotations
    @inline()
  7. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  8. final def addString(b: StringBuilder): b.type
    Definition Classes
    IterableOnceOps
    Annotations
    @inline()
  9. final def addString(b: StringBuilder, sep: String): b.type
    Definition Classes
    IterableOnceOps
    Annotations
    @inline()
  10. def addString(b: StringBuilder, start: String, sep: String, end: String): b.type
    Definition Classes
    IterableOnceOps
  11. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  12. def className: String
    Attributes
    protected[this]
    Definition Classes
    Iterable
  13. def clone(): AnyRef
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.CloneNotSupportedException]) @HotSpotIntrinsicCandidate() @native()
  14. final def coll: LeftistHeap.this.type
    Attributes
    protected
    Definition Classes
    Iterable → IterableOps
  15. def collect[B](pf: PartialFunction[T, B]): Iterable[B]
    Definition Classes
    IterableOps → IterableOnceOps
  16. def collectFirst[B](pf: PartialFunction[T, B]): Option[B]
    Definition Classes
    IterableOnceOps
  17. def concat[B >: T](suffix: IterableOnce[B]): Iterable[B]
    Definition Classes
    IterableOps
  18. def copyToArray[B >: T](xs: Array[B], start: Int, len: Int): Int
    Definition Classes
    IterableOnceOps
  19. def copyToArray[B >: T](xs: Array[B], start: Int): Int
    Definition Classes
    IterableOnceOps
    Annotations
    @deprecatedOverriding()
  20. def copyToArray[B >: T](xs: Array[B]): Int
    Definition Classes
    IterableOnceOps
    Annotations
    @deprecatedOverriding()
  21. def corresponds[B](that: IterableOnce[B])(p: (T, B) => Boolean): Boolean
    Definition Classes
    IterableOnceOps
  22. def count(p: (T) => Boolean): Int
    Definition Classes
    IterableOnceOps
  23. def drop(n: Int): Iterable[T]
    Definition Classes
    IterableOps → IterableOnceOps
  24. def dropRight(n: Int): Iterable[T]
    Definition Classes
    IterableOps
  25. def dropWhile(p: (T) => Boolean): Iterable[T]
    Definition Classes
    IterableOps → IterableOnceOps
  26. def empty: Iterable[T]
    Definition Classes
    IterableFactoryDefaults → IterableOps
  27. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  28. def equals(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef → Any
  29. def exists(p: (T) => Boolean): Boolean
    Definition Classes
    IterableOnceOps
  30. def filter(pred: (T) => Boolean): Iterable[T]
    Definition Classes
    IterableOps → IterableOnceOps
  31. def filterNot(pred: (T) => Boolean): Iterable[T]
    Definition Classes
    IterableOps → IterableOnceOps
  32. def find(p: (T) => Boolean): Option[T]
    Definition Classes
    IterableOnceOps
  33. def findMinOption: Option[T]

    returns

    the minimum element of this heap, or None> iff this heap is empty (isEmpty()==true)

  34. def flatItMap(f: (T) => Iterator[T], stop: (LeftistHeap[T, HC]) => Boolean): LeftistHeap[T, HC]

    Apply a function f to all elements in this heap.

    Apply a function f to all elements in this heap. The heap traversal is skipped for a subheap if the function stop applied to this subheap returns true. The function f can return null to signal that a data element has not changed.

  35. def flatItMapIter(f: (T) => Iterator[T], stop: (LeftistHeap[T, HC]) => Boolean): LeftistHeap[T, HC]

    Apply a function f to all elements in this heap.

    Apply a function f to all elements in this heap. The heap traversal is skipped for a subheap if the function stop applied to this subheap returns true. The function f can return null to signal that a data element has not changed.

  36. def flatMap[B](f: (T) => IterableOnce[B]): Iterable[B]
    Definition Classes
    IterableOps → IterableOnceOps
  37. def flatten[B](implicit asIterable: (T) => IterableOnce[B]): Iterable[B]
    Definition Classes
    IterableOps → IterableOnceOps
  38. def fold[A1 >: T](z: A1)(op: (A1, A1) => A1): A1
    Definition Classes
    IterableOnceOps
  39. def foldLeft[B](z: B)(op: (B, T) => B): B
    Definition Classes
    IterableOnceOps
  40. def foldRight[B](z: B)(op: (T, B) => B): B
    Definition Classes
    IterableOnceOps
  41. def forall(p: (T) => Boolean): Boolean
    Definition Classes
    IterableOnceOps
  42. def foreach[U](f: (T) => U): Unit
    Definition Classes
    IterableOnceOps
  43. def fromSpecific(coll: IterableOnce[T]): Iterable[T]
    Attributes
    protected
    Definition Classes
    IterableFactoryDefaults → IterableOps
  44. final def getClass(): Class[_ <: AnyRef]
    Definition Classes
    AnyRef → Any
    Annotations
    @HotSpotIntrinsicCandidate() @native()
  45. def groupBy[K](f: (T) => K): Map[K, Iterable[T]]
    Definition Classes
    IterableOps
  46. def groupMap[K, B](key: (T) => K)(f: (T) => B): Map[K, Iterable[B]]
    Definition Classes
    IterableOps
  47. def groupMapReduce[K, B](key: (T) => K)(f: (T) => B)(reduce: (B, B) => B): Map[K, B]
    Definition Classes
    IterableOps
  48. def grouped(size: Int): Iterator[Iterable[T]]
    Definition Classes
    IterableOps
  49. def hashCode(): Int
    Definition Classes
    AnyRef → Any
    Annotations
    @HotSpotIntrinsicCandidate() @native()
  50. def head: T
    Definition Classes
    IterableOps
  51. def headOption: Option[T]
    Definition Classes
    IterableOps
  52. def init: Iterable[T]
    Definition Classes
    IterableOps
  53. def inits: Iterator[Iterable[T]]
    Definition Classes
    IterableOps
  54. def insertIt(elements: Iterator[T]): LeftistHeap[T, HC]

    Add multiple elements to this heap object

    Add multiple elements to this heap object

    elements

    the elements to be added

    returns

    a heap that contains all elements of this heap, and additionally all objects from elements

  55. def isEmpty: Boolean
    Definition Classes
    IterableOnceOps
  56. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  57. def isTraversableAgain: Boolean
    Definition Classes
    IterableOps → IterableOnceOps
  58. def iterableFactory: IterableFactory[Iterable]
    Definition Classes
    Iterable → IterableOps
  59. def iterator: Iterator[T]
    Definition Classes
    LeftistHeap → IterableOnce
  60. def knownSize: Int
    Definition Classes
    IterableOnce
  61. def last: T
    Definition Classes
    IterableOps
  62. def lastOption: Option[T]
    Definition Classes
    IterableOps
  63. def lazyZip[B](that: Iterable[B]): LazyZip2[T, B, LeftistHeap.this.type]
    Definition Classes
    Iterable
  64. def map[B](f: (T) => B): Iterable[B]
    Definition Classes
    IterableOps → IterableOnceOps
  65. def max[B >: T](implicit ord: Ordering[B]): T
    Definition Classes
    IterableOnceOps
  66. def maxBy[B](f: (T) => B)(implicit ord: Ordering[B]): T
    Definition Classes
    IterableOnceOps
  67. def maxByOption[B](f: (T) => B)(implicit ord: Ordering[B]): Option[T]
    Definition Classes
    IterableOnceOps
  68. def maxOption[B >: T](implicit ord: Ordering[B]): Option[T]
    Definition Classes
    IterableOnceOps
  69. def min[B >: T](implicit ord: Ordering[B]): T
    Definition Classes
    IterableOnceOps
  70. def minBy[B](f: (T) => B)(implicit ord: Ordering[B]): T
    Definition Classes
    IterableOnceOps
  71. def minByOption[B](f: (T) => B)(implicit ord: Ordering[B]): Option[T]
    Definition Classes
    IterableOnceOps
  72. def minOption[B >: T](implicit ord: Ordering[B]): Option[T]
    Definition Classes
    IterableOnceOps
  73. final def mkString: String
    Definition Classes
    IterableOnceOps
    Annotations
    @inline()
  74. final def mkString(sep: String): String
    Definition Classes
    IterableOnceOps
    Annotations
    @inline()
  75. final def mkString(start: String, sep: String, end: String): String
    Definition Classes
    IterableOnceOps
  76. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  77. def newSpecificBuilder: Builder[T, Iterable[T]]
    Attributes
    protected
    Definition Classes
    IterableFactoryDefaults → IterableOps
  78. def nonEmpty: Boolean
    Definition Classes
    IterableOnceOps
    Annotations
    @deprecatedOverriding()
  79. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @HotSpotIntrinsicCandidate() @native()
  80. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @HotSpotIntrinsicCandidate() @native()
  81. def partition(p: (T) => Boolean): (Iterable[T], Iterable[T])
    Definition Classes
    IterableOps
  82. def partitionMap[A1, A2](f: (T) => Either[A1, A2]): (Iterable[A1], Iterable[A2])
    Definition Classes
    IterableOps
  83. def product[B >: T](implicit num: Numeric[B]): B
    Definition Classes
    IterableOnceOps
  84. def reduce[B >: T](op: (B, B) => B): B
    Definition Classes
    IterableOnceOps
  85. def reduceLeft[B >: T](op: (B, T) => B): B
    Definition Classes
    IterableOnceOps
  86. def reduceLeftOption[B >: T](op: (B, T) => B): Option[B]
    Definition Classes
    IterableOnceOps
  87. def reduceOption[B >: T](op: (B, B) => B): Option[B]
    Definition Classes
    IterableOnceOps
  88. def reduceRight[B >: T](op: (T, B) => B): B
    Definition Classes
    IterableOnceOps
  89. def reduceRightOption[B >: T](op: (T, B) => B): Option[B]
    Definition Classes
    IterableOnceOps
  90. def reversed: Iterable[T]
    Attributes
    protected
    Definition Classes
    IterableOnceOps
  91. def scan[B >: T](z: B)(op: (B, B) => B): Iterable[B]
    Definition Classes
    IterableOps
  92. def scanLeft[B](z: B)(op: (B, T) => B): Iterable[B]
    Definition Classes
    IterableOps → IterableOnceOps
  93. def scanRight[B](z: B)(op: (T, B) => B): Iterable[B]
    Definition Classes
    IterableOps
  94. def size: Int
    Definition Classes
    IterableOnceOps
  95. def sizeCompare(that: Iterable[_]): Int
    Definition Classes
    IterableOps
  96. def sizeCompare(otherSize: Int): Int
    Definition Classes
    IterableOps
  97. final def sizeIs: SizeCompareOps
    Definition Classes
    IterableOps
    Annotations
    @inline()
  98. def slice(from: Int, until: Int): Iterable[T]
    Definition Classes
    IterableOps → IterableOnceOps
  99. def sliding(size: Int, step: Int): Iterator[Iterable[T]]
    Definition Classes
    IterableOps
  100. def sliding(size: Int): Iterator[Iterable[T]]
    Definition Classes
    IterableOps
  101. def sortedIterator: Iterator[T]

    returns

    an iterator that returns all elements of this heap in increasing order

  102. def span(p: (T) => Boolean): (Iterable[T], Iterable[T])
    Definition Classes
    IterableOps → IterableOnceOps
  103. def splitAt(n: Int): (Iterable[T], Iterable[T])
    Definition Classes
    IterableOps → IterableOnceOps
  104. def stepper[S <: Stepper[_]](implicit shape: StepperShape[T, S]): S
    Definition Classes
    IterableOnce
  105. def stringPrefix: String
    Attributes
    protected[this]
    Definition Classes
    Iterable
    Annotations
    @deprecatedOverriding()
  106. def sum[B >: T](implicit num: Numeric[B]): B
    Definition Classes
    IterableOnceOps
  107. final def synchronized[T0](arg0: => T0): T0
    Definition Classes
    AnyRef
  108. def tail: Iterable[T]
    Definition Classes
    IterableOps
  109. def tails: Iterator[Iterable[T]]
    Definition Classes
    IterableOps
  110. def take(n: Int): Iterable[T]
    Definition Classes
    IterableOps → IterableOnceOps
  111. def takeRight(n: Int): Iterable[T]
    Definition Classes
    IterableOps
  112. def takeWhile(p: (T) => Boolean): Iterable[T]
    Definition Classes
    IterableOps → IterableOnceOps
  113. def tapEach[U](f: (T) => U): Iterable[T]
    Definition Classes
    IterableOps → IterableOnceOps
  114. def to[C1](factory: Factory[T, C1]): C1
    Definition Classes
    IterableOnceOps
  115. def toArray[B >: T](implicit arg0: ClassTag[B]): Array[B]
    Definition Classes
    IterableOnceOps
  116. final def toBuffer[B >: T]: Buffer[B]
    Definition Classes
    IterableOnceOps
    Annotations
    @inline()
  117. def toIndexedSeq: IndexedSeq[T]
    Definition Classes
    IterableOnceOps
  118. def toList: List[T]
    Definition Classes
    IterableOnceOps
  119. def toMap[K, V](implicit ev: <:<[T, (K, V)]): Map[K, V]
    Definition Classes
    IterableOnceOps
  120. def toSeq: Seq[T]
    Definition Classes
    IterableOnceOps
  121. def toSet[B >: T]: Set[B]
    Definition Classes
    IterableOnceOps
  122. def toString(): String
    Definition Classes
    LeftistHeap → Iterable → AnyRef → Any
  123. def toVector: Vector[T]
    Definition Classes
    IterableOnceOps
  124. def transpose[B](implicit asIterable: (T) => Iterable[B]): Iterable[Iterable[B]]
    Definition Classes
    IterableOps
  125. def unsortedIterator: Iterator[T]

    returns

    an iterator that returns all elements of this heap

  126. def unzip[A1, A2](implicit asPair: (T) => (A1, A2)): (Iterable[A1], Iterable[A2])
    Definition Classes
    IterableOps
  127. def unzip3[A1, A2, A3](implicit asTriple: (T) => (A1, A2, A3)): (Iterable[A1], Iterable[A2], Iterable[A3])
    Definition Classes
    IterableOps
  128. def view: View[T]
    Definition Classes
    IterableOps
  129. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  130. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException]) @native()
  131. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  132. def withFilter(p: (T) => Boolean): WithFilter[T, Iterable]
    Definition Classes
    IterableOps
  133. def zip[B](that: IterableOnce[B]): Iterable[(T, B)]
    Definition Classes
    IterableOps
  134. def zipAll[A1 >: T, B](that: Iterable[B], thisElem: A1, thatElem: B): Iterable[(A1, B)]
    Definition Classes
    IterableOps
  135. def zipWithIndex: Iterable[(T, Int)]
    Definition Classes
    IterableOps → IterableOnceOps

Deprecated Value Members

  1. def ++:[B >: T](that: IterableOnce[B]): Iterable[B]
    Definition Classes
    IterableOps
    Annotations
    @deprecated
    Deprecated

    (Since version 2.13.0) Use ++ instead of ++: for collections of type Iterable

  2. final def /:[B](z: B)(op: (B, T) => B): B
    Definition Classes
    IterableOnceOps
    Annotations
    @deprecated @inline()
    Deprecated

    (Since version 2.13.0) Use foldLeft instead of /:

  3. final def :\[B](z: B)(op: (T, B) => B): B
    Definition Classes
    IterableOnceOps
    Annotations
    @deprecated @inline()
    Deprecated

    (Since version 2.13.0) Use foldRight instead of :\

  4. def aggregate[B](z: => B)(seqop: (B, T) => B, combop: (B, B) => B): B
    Definition Classes
    IterableOnceOps
    Annotations
    @deprecated
    Deprecated

    (Since version 2.13.0) For sequential collections, prefer foldLeft(z)(seqop). For parallel collections, use ParIterableLike#aggregate.

  5. def companion: IterableFactory[Iterable]
    Definition Classes
    IterableOps
    Annotations
    @deprecated @deprecatedOverriding() @inline()
    Deprecated

    (Since version 2.13.0) Use iterableFactory instead

  6. final def copyToBuffer[B >: T](dest: Buffer[B]): Unit
    Definition Classes
    IterableOnceOps
    Annotations
    @deprecated @inline()
    Deprecated

    (Since version 2.13.0) Use dest ++= coll instead

  7. def finalize(): Unit
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.Throwable]) @Deprecated
    Deprecated

    (Since version 9)

  8. def hasDefiniteSize: Boolean
    Definition Classes
    IterableOnceOps
    Annotations
    @deprecated
    Deprecated

    (Since version 2.13.0) Check .knownSize instead of .hasDefiniteSize for more actionable information (see scaladoc for details)

  9. final def repr: Iterable[T]
    Definition Classes
    IterableOps
    Annotations
    @deprecated
    Deprecated

    (Since version 2.13.0) Use coll instead of repr in a collection implementation, use the collection value itself from the outside

  10. def seq: LeftistHeap.this.type
    Definition Classes
    Iterable
    Annotations
    @deprecated
    Deprecated

    (Since version 2.13.0) Iterable.seq always returns the iterable itself

  11. final def toIterable: LeftistHeap.this.type
    Definition Classes
    Iterable → IterableOps
    Annotations
    @deprecated
    Deprecated

    (Since version 2.13.7) toIterable is internal and will be made protected; its name is similar to toList or toSeq, but it doesn't copy non-immutable collections

  12. final def toIterator: Iterator[T]
    Definition Classes
    IterableOnceOps
    Annotations
    @deprecated @inline()
    Deprecated

    (Since version 2.13.0) Use .iterator instead of .toIterator

  13. final def toStream: Stream[T]
    Definition Classes
    IterableOnceOps
    Annotations
    @deprecated @inline()
    Deprecated

    (Since version 2.13.0) Use .to(LazyList) instead of .toStream

  14. final def toTraversable: Traversable[T]
    Definition Classes
    IterableOps
    Annotations
    @deprecated
    Deprecated

    (Since version 2.13.0) toTraversable is internal and will be made protected; its name is similar to toList or toSeq, but it doesn't copy non-immutable collections

  15. def view(from: Int, until: Int): View[T]
    Definition Classes
    IterableOps
    Annotations
    @deprecated
    Deprecated

    (Since version 2.13.0) Use .view.slice(from, until) instead of .view(from, until)

Inherited from Iterable[T]

Inherited from IterableFactoryDefaults[T, Iterable]

Inherited from IterableOps[T, Iterable, Iterable[T]]

Inherited from IterableOnceOps[T, Iterable, Iterable[T]]

Inherited from IterableOnce[T]

Inherited from AnyRef

Inherited from Any

Ungrouped