A min-heap implemented over an array

The order is given by the comparator.

var a = [3,4,1,2]
var h = new MinHeap[Int].default
h.add_all(a)
assert h.peek == 1
var b = h.take_all
assert b == [1, 2, 3, 4]

Introduced properties

fun comparator: Comparator

core :: MinHeap :: comparator

The comparator used to order the Heap
protected fun comparator=(comparator: Comparator)

core :: MinHeap :: comparator=

The comparator used to order the Heap
init default

core :: MinHeap :: default

Use the default_comparator on Comparable elements
init defaultinit(comparator: Comparator)

core :: MinHeap :: defaultinit

Redefined properties

redef type SELF: MinHeap[E]

core $ MinHeap :: SELF

Type of this instance, automatically specialized in every class
redef fun add(e: E)

core $ MinHeap :: add

Add item to this collection.
redef fun clear

core $ MinHeap :: clear

Remove all items
redef fun core_serialize_to(v: Serializer)

serialization :: serialization_core $ MinHeap :: core_serialize_to

Actual serialization of self to serializer
redef init from_deserializer(v: Deserializer)

serialization :: serialization_core $ MinHeap :: from_deserializer

Create an instance of this class from the deserializer
redef fun is_empty: Bool

core $ MinHeap :: is_empty

Is there no item in the collection?
redef fun iterator: Iterator[E]

core $ MinHeap :: iterator

Get a new iterator on the collection.
redef fun length: Int

core $ MinHeap :: length

Number of items in the collection.
redef fun peek: E

core $ MinHeap :: peek

Look at the next element but does not remove it
redef fun take: E

core $ MinHeap :: take

Take the next element (according to the specific queue)

All properties

fun !=(other: nullable Object): Bool

core :: Object :: !=

Have self and other different values?
fun ==(other: nullable Object): Bool

core :: Object :: ==

Have self and other the same value?
type CLASS: Class[SELF]

core :: Object :: CLASS

The type of the class of self.
type CONCURRENT: ConcurrentCollection[E]

core :: Collection :: CONCURRENT

Type of the concurrent variant of this collection
type SELF: Object

core :: Object :: SELF

Type of this instance, automatically specialized in every class
protected fun accept_json_serializer(v: JsonSerializer)

serialization :: Serializable :: accept_json_serializer

Refinable service to customize the serialization of this class to JSON
protected fun accept_msgpack_attribute_counter(v: AttributeCounter)

serialization :: Serializable :: accept_msgpack_attribute_counter

Hook to customize the behavior of the AttributeCounter
protected fun accept_msgpack_serializer(v: MsgPackSerializer)

serialization :: Serializable :: accept_msgpack_serializer

Hook to customize the serialization of this class to MessagePack
abstract fun add(item: E)

core :: SimpleCollection :: add

Add item to this collection.
fun add_all(coll: Collection[E])

core :: SimpleCollection :: add_all

Add each item of coll.
protected fun add_to_bundle(bundle: NativeBundle, key: JavaString)

serialization :: Serializable :: add_to_bundle

Called by []= to dynamically choose the appropriate method according
fun as_random: Queue[E]

core :: SimpleCollection :: as_random

Return a random proxy queue where result.take is random.
protected fun class_factory(name: String): CLASS

core :: Object :: class_factory

Implementation used by get_class to create the specific class.
fun class_name: String

core :: Object :: class_name

The class name of the object.
abstract fun clear

core :: RemovableCollection :: clear

Remove all items
fun combinations(r: Int): Collection[SequenceRead[E]]

core :: Collection :: combinations

All r-length combinations on self (in same order) without repeated elements.
fun combinations_with_replacement(r: Int): Collection[SequenceRead[E]]

core :: Collection :: combinations_with_replacement

All r-length combination on self (in same order) with repeated elements.
fun comparator: Comparator

core :: MinHeap :: comparator

The comparator used to order the Heap
protected fun comparator=(comparator: Comparator)

core :: MinHeap :: comparator=

The comparator used to order the Heap
fun core_serialize_to(serializer: Serializer)

serialization :: Serializable :: core_serialize_to

Actual serialization of self to serializer
fun count(item: nullable Object): Int

core :: Collection :: count

How many occurrences of item are in the collection?
init default

core :: MinHeap :: default

Use the default_comparator on Comparable elements
init defaultinit(comparator: Comparator)

core :: MinHeap :: defaultinit

fun first: E

core :: Collection :: first

Return the first item of the collection
init from_deserializer(deserializer: Deserializer)

serialization :: Serializable :: from_deserializer

Create an instance of this class from the deserializer
fun get_class: CLASS

core :: Object :: get_class

The meta-object representing the dynamic type of self.
fun has(item: nullable Object): Bool

core :: Collection :: has

Is item in the collection ?
fun has_all(other: Collection[nullable Object]): Bool

core :: Collection :: has_all

Does the collection contain at least each element of other?
fun has_any(other: Collection[nullable Object]): Bool

core :: Collection :: has_any

Does the collection contain at least one element of other?
fun has_exactly(other: Collection[nullable Object]): Bool

core :: Collection :: has_exactly

Does the collection contain exactly all the elements of other?
fun has_only(item: nullable Object): Bool

core :: Collection :: has_only

Is the collection contain only item?
fun hash: Int

core :: Object :: hash

The hash code of the object.
init init

core :: Object :: init

fun inspect: String

core :: Object :: inspect

Developer readable representation of self.
protected fun inspect_head: String

core :: Object :: inspect_head

Return "CLASSNAME:#OBJECTID".
fun is_empty: Bool

core :: Collection :: is_empty

Is there no item in the collection?
intern fun is_same_instance(other: nullable Object): Bool

core :: Object :: is_same_instance

Return true if self and other are the same instance (i.e. same identity).
fun is_same_serialized(other: nullable Object): Bool

core :: Object :: is_same_serialized

Is self the same as other in a serialization context?
intern fun is_same_type(other: Object): Bool

core :: Object :: is_same_type

Return true if self and other have the same dynamic type.
abstract fun iterator: Iterator[E]

core :: Collection :: iterator

Get a new iterator on the collection.
fun join(separator: nullable Text, last_separator: nullable Text): String

core :: Collection :: join

Concatenate and separate each elements with separator.
fun length: Int

core :: Collection :: length

Number of items in the collection.
protected fun msgpack_extra_array_items: Int

serialization :: Serializable :: msgpack_extra_array_items

Hook to request a larger than usual metadata array
fun not_empty: Bool

core :: Collection :: not_empty

Alias for not is_empty.
intern fun object_id: Int

core :: Object :: object_id

An internal hash code for the object based on its identity.
fun output

core :: Object :: output

Display self on stdout (debug only).
intern fun output_class_name

core :: Object :: output_class_name

Display class name on stdout (debug only).
abstract fun peek: E

core :: Queue :: peek

Look at the next element but does not remove it
fun permutations(r: Int): Collection[SequenceRead[E]]

core :: Collection :: permutations

All r-length permutations on self (all possible ordering) without repeated elements.
fun plain_to_s: String

core :: Collection :: plain_to_s

Concatenate elements without separators
fun product(r: Int): Collection[SequenceRead[E]]

core :: Collection :: product

Cartesian product, over r times self.
fun rand: E

core :: Collection :: rand

Return a random element form the collection
abstract fun remove(item: nullable Object)

core :: RemovableCollection :: remove

Remove an occurrence of item
fun remove_all(item: nullable Object)

core :: RemovableCollection :: remove_all

Remove all occurrences of item
fun sample(length: Int): Array[E]

core :: Collection :: sample

Return a new array made of (at most) length elements randomly chosen.
fun serialization_hash: Int

core :: Object :: serialization_hash

Hash value use for serialization
fun serialize_msgpack(plain: nullable Bool): Bytes

serialization :: Serializable :: serialize_msgpack

Serialize self to MessagePack bytes
fun serialize_to(serializer: Serializer)

serialization :: Serializable :: serialize_to

Serialize self to serializer
fun serialize_to_json(plain: nullable Bool, pretty: nullable Bool): String

serialization :: Serializable :: serialize_to_json

Serialize self to JSON
intern fun sys: Sys

core :: Object :: sys

Return the global sys object, the only instance of the Sys class.
abstract fun take: E

core :: Queue :: take

Take the next element (according to the specific queue)
fun take_all: Array[E]

core :: Queue :: take_all

Take and return all elements until the queue is empty.
fun to_a: Array[E]

core :: Collection :: to_a

Build a new array from a collection
abstract fun to_concurrent: CONCURRENT

core :: Collection :: to_concurrent

Wraps self in a thread-safe collection
fun to_counter: Counter[E]

core :: Collection :: to_counter

Create and fill up a counter with the elements of `self.
fun to_curlslist: CURLSList

core :: Collection :: to_curlslist

Convert Collection[String] to CURLSList
fun to_json: String

serialization :: Serializable :: to_json

Serialize self to plain JSON
abstract fun to_jvalue(env: JniEnv): JValue

core :: Object :: to_jvalue

fun to_pretty_json: String

serialization :: Serializable :: to_pretty_json

Serialize self to plain pretty JSON
fun to_s: String

core :: Object :: to_s

User readable representation of self.
fun to_shuffle: Array[E]

core :: Collection :: to_shuffle

Return a new array made of elements in a random order.
package_diagram core::MinHeap MinHeap core::Queue Queue core::MinHeap->core::Queue core::SimpleCollection SimpleCollection core::Queue->core::SimpleCollection ...core::SimpleCollection ... ...core::SimpleCollection->core::SimpleCollection

Ancestors

interface Collection[E: nullable Object]

core :: Collection

The root of the collection hierarchy.
interface Object

core :: Object

The root of the class hierarchy.
interface RemovableCollection[E: nullable Object]

core :: RemovableCollection

Items can be removed from this collection
interface Serializable

serialization :: Serializable

Instances of this class can be passed to Serializer::serialize
interface SimpleCollection[E: nullable Object]

core :: SimpleCollection

Items can be added to these collections.

Parents

interface Queue[E: nullable Object]

core :: Queue

Queues are collection that controls how elements are retrieved.

Class definitions

core $ MinHeap
# A min-heap implemented over an array
#
# The order is given by the `comparator`.
#
# ~~~
# var a = [3,4,1,2]
# var h = new MinHeap[Int].default
# h.add_all(a)
# assert h.peek == 1
# var b = h.take_all
# assert b == [1, 2, 3, 4]
# ~~~
class MinHeap[E: Object]
	super Queue[E]

	private var items = new Array[E]

	# The comparator used to order the Heap
	var comparator: Comparator

	# Use the `default_comparator` on Comparable elements
	#
	# Require self isa MinHeap[Comparable]
	init default
	do
		assert self isa MinHeap[Comparable]
		init(default_comparator)
	end

	redef fun is_empty do return items.is_empty
	redef fun length do return items.length
	redef fun iterator do return items.iterator
	redef fun clear do items.clear

	redef fun peek do return items.first
	redef fun add(e)
	do
		#assert assert_best else print "try to add {e}"
		#var ol = length
		var ei = items.length + 1
		while ei > 1 do
			var pi = ei/2
			var p = items[pi-1]
			if comparator.compare(p, e) <= 0 then break

			# bubble-up
			items[ei-1] = p

			# next
			ei = pi
		end
		items[ei-1] = e
		#assert length == ol + 1
		#assert assert_best else print "added {e}"
	end

	redef fun take do
		#assert assert_best else print "tri to take"
		#var ol = length
		if length < 2 then return items.pop

		var res = items.first
		var ei = 1
		var e = items.pop

		var last = items.length
		loop
			# Check first child
			var ci = ei*2
			if ci > last then break # no children
			var c = items[ci-1]
			var upc = comparator.compare(e, c) > 0

			# Check second child
			var c2i = ci + 1
			if c2i <= last then do
				var c2 = items[c2i-1]
				# possibility to bubble-down to c2, or not?
				if comparator.compare(e, c2) <= 0 then break label
				# c2 is a better path, or not?
				if upc and comparator.compare(c2, c) > 0 then break label
				# goes to c2 path
				upc = true
				c = c2
				ci = c2i
			end label

			# bubble-down?
			if not upc then break

			items[ei-1] = c
			ei = ci
		end
		items[ei-1] = e
		#assert length == ol - 1 else print "is {length}, expected {ol - 1}"
		#assert assert_best else print "dequed {res}"
		return res
	end

	# Used internally do debug the Heap.
	# Not removed because this can still be useful.
	private fun assert_best: Bool
	do
		if is_empty then return true
		var b = peek
		for i in self do if comparator.compare(b, i) > 0 then
			#print "  peek is {b} but better found {i}"
			for j in self do
				#print "   {j}"
			end
			return false
		end
		return true
	end
end
lib/core/queue.nit:209,1--323,3