Functional Programming
A Heap
A New Heap
A heap is a tree structure where the largest element is in the root of the tree and where the left and right branch are heaps. Define a data structure that is suitable to represent a heap and implement a function new/0
that returns a heap. Assume that we only should handle integers.
@spec new() :: heap()
Insert
Implement the function add/2
that adds an integer to a heap.
@spec add(heap(), integer()) :: heap()
To keep the heap balanced you should switch the left and right branches that is, when you add an element to a branch you add it to the right branch but make the result the left branch of the heap.
Pop
Implement the function pop/1
that removes the highest element in an heap and returns either :fail
, if the heap is empty or {:ok, integer(), heap()}
@spec pop(heap()) :fail | {:ok, integer(), heap()}
Swap
Implement the function swap/2
that takes a heap and a number and returns {:ok, integer(), heap()}
where the number is the highest number and the heap the remaining heap. The function should have the same meaning as first add/2
a number to a heap and then pop/1
the highest but we should do this in one function, not by calling the two functions.
@spec swap(heap(), integer()) {:ok, integer(), heap()}
A General Heap
The heap we now have will have the largest element in the root and be limited to integers (or what is comparable with <
). Implement a function add/3
that takes a heap, an element and a function that can be used to compare two elements. The function add/3
should as before add an element to a heap but now used the provided function when doing the comparison.
@type cmp() :: (any(), any() > bool())
@spec add(heap(), any(), cmp()) :: heap()
Specify a type cheap()
that holds a function for comparison and a heap. Implement a function new/1
that takes a function and returns a structure of the type cheap()
.
@spec new(cmp()) :: cheap()
Implement a function add/2
that takes a structure of type cheap()
, that calls add/3
with the correct arguments and returns a structure of the same form.
@spec add(cheap(), any()) :: cheap()
Mirror a Tree
If we have the below definition of a function that mirrors a tree, what is the asymptotic time complexity of the function?
def mirror(nil) do nil end
def mirror({:node, left, right}) do
{:node, mirror(right), mirror(left)}
end
Complexity of a Queue
Assume that we represent a queue with the help of two lists and have the below implementation of enqueue/2
and dequeue/1
. What is the amortised time complexity for adding and then removing an element from a queue?
def enqueue({:queue, head, tail}, elem) do
{:queue, head, [elem|tail]}
end
def dequeue({:queue, [], []}) do :fail end
def dequeue({:queue, [elem|head], tail}) do
{:ok, elem, {:queue, head, tail}
end
def dequeue({:queue, [], tail}) do
dequeue({:queue, reverse(tail), []})
end
Last updated