abstract class BinaryHeap def empty Boolean def getValue def getHeight

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
abstract class BinaryHeap[T] {
def empty: Boolean
def getValue: T
def getHeight: Int
def getSize: Int
def getLeft: BinaryHeap[T]
def getRight: BinaryHeap[T]
def equals(a:T):Boolean
def insert(a:Int): BinaryHeap[T]
def remove: BinaryHeap[T]
def BinaryHeap[T](value: T, left: BinaryHeap[T], right: BinaryHeap[T]): BinaryHeap[T] =
Node[T](value, left, right)
}
case class Node[T](val value: T, val left: BinaryHeap[T], val right: BinaryHeap[T]) extends BinaryHeap[T] {
val size: Int = left.getSize + right.getSize + 1
val height: Int = if(left.getHeight > right.getHeight) left.getHeight + 1 else right.getHeight + 1
def changeLeft(newLeft: Node[T]) = new Node[T](value, newLeft, right)
def changeRight(newRight: Node[T]) = new Node[T](value, left, newRight)
def changeValue(newValue: T) = new Node[T](newValue, left, right)
def empty = false
def getValue = value
def getHeight = height
def getSize = size
def getLeft = left
def getRight = right
def changeParents(v: Int, l: BinaryHeap[T], r: BinaryHeap[T]) =
if (!l.empty && v.moreThen(l.getValue))
new Node(l.getValue, new Node(v, l.getLeft, l.getRight), r)
else if (!r.empty && v > r.getValue)
new Node(r.getValue, l, new Node(v, r.getLeft, r.getRight))
else
new Node(v, l, r)
def insert(v: T) =
if (left.getSize < math.pow(2, left.getHeight) - 1)
changeParents(value, left.insert(v), right)
else if (right.getSize < math.pow(2, right.getHeight) - 1 || right.getHeight < left.getHeight)
changeParents(value, left, right.insert(v))
else
changeParents(value, left.insert(v), right)
def changeChildren(v: T, l: BinaryHeap[T], r: BinaryHeap[T]):Node[T] =
if (!l.empty && !r.empty && r.getValue < l.getValue && v > r.getValue)
new Node[T](r.getValue, l, changeChildren(v, r.getLeft, r.getRight))
else if (!l.empty && v > l.getValue)
new Node[T](l.getValue, changeChildren(v, l.getLeft, r.getLeft), r)
else
new Node[T](v, l, r)
override def remove = new EmptyNode
}
case class EmptyNode[T]() extends BinaryHeap[T] {
def empty = true
def getValue = throw new Exception("Node is non-existing")
def getHeight = 0
def getSize = 0
def getLeft = throw new Exception("Node is non-existing")
def getRight = throw new Exception("Node is non-existing")
def equals(a: BinaryHeap[T]) = (getValue == a.getValue && !empty && !a.empty)
def insert(value: T) = new Node(value, new EmptyNode, new EmptyNode)
def remove = new EmptyNode
}