A heap is a tree-based data structure where the maximum element is easily accessible. The Heap class implements a binary max-heap regarding the comparison operator (< by default).

import "data" for Heap

< Back to data

Static Methods

new()

Create a new empty heap.

import "data" for Heap

def h = Heap.new()
IO.println(h) #> []

new(comp)

Create a new empty heap with comp as a comparator.

import "data" for Heap

# define a min-heap
def h = Heap.new {|a, b| a > b }
IO.println(h) #> []

sort(seq), sort(seq,comp)

Sort the sequence and returns and array with the elements sorted using heapsort. Comparator comp is used to compare two elements, if it returns true then the first element will be put before the second element in the sorted array. If comp is not provided, < is used to compare elements.

import "data" for Heap

def a = [ 5, 10, 3, 6, 9, 2, 7 ]
IO.println(Heap.sort(a)) #> [2, 3, 5, 6, 7, 9, 10]

Methods

clear()

Remove all the elements from the heap.

import "data" for Heap

def h = Heap.new()
h.push(42)
h.clear()
IO.println(h) #> []

clone()

Get a deep copy of the heap. The elements of the heap must implement the clone method.

import "data" for Heap

def h0 = Heap.new()
h0.push(42)
def h1 = h0.clone()
IO.println(h1) #> [42]

empty

Return true if the heap has no elements.

import "data" for Heap

def h = Heap.new()
IO.println(h.empty) #> true
h.push(42)
IO.println(h.empty) #> false

See also: size

peek()

Get the maximum element of the heap.

import "data" for Heap

def h = Heap.new()
h.push(42)
h.push(69)
IO.println(h.peek()) #> 69
h.pop()
IO.println(h.peek()) #> 42

See also: pop(), push(item)

pop()

Remove the maximum element of the heap.

import "data" for Heap

def h = Heap.new()
h.push(42)
IO.println(h) #> [42]
h.pop()
IO.println(h) #> []

See also: peek(), push(item)

push(item)

Insert an element in the heap.

import "data" for Heap

def h = Heap.new()
h.push(42)
IO.println(h) #> [42]
h.push(69)
IO.println(h) #> [69, 42]

See also: peek(), pop()

size

Return the number of elements in the heap.

import "data" for Heap

def h = Heap.new()
IO.println(h.size) #> 0
h.push(42)
IO.println(h.size) #> 1

See also: empty

to_a

Transform the heap to an array with the same elements.

import "data" for Heap

def h = Heap.new()
h.push(42)
h.push(69)
IO.println(h.to_a) #> [69, 42]

to_s

Transform the heap to a String.

import "data" for Heap

def h = Heap.new()
h.push(42)
h.push(69)
IO.println(h.to_s) #> [69, 42]