# 1).  Pseudo-Code to Python (20 Marks)

One way to speed up Dijkstra’s algorithm is to keep the list of pending nodes in sorted order.  If we were to apply a sort every time, though, this could get prohibitive because the best sorts are O(n lg n).  An alternative uses a Heap.  The pseudo-code for the functions below implement insert and serve for a Heap.  Insert adds a new node to the list in the appropriate place.  Serve removes the lowest node from the list and reorders the list.  A heap is O (lg n) which is much faster than a sort.

In the following two sections, each entry in the list consists of a tuple of the form (name, value).  Implement each function from the pseudo-code given.  Put both the insert and serve functions in a single python file called ‘heap.py”.

1a). Heap Insert (10)   insert (list, node, value)

Creates a new tuple (node, list) and uses the following algorithm to put that node into the list in heap order

I.      Create the tuple

II.    Add the tuple to the end of the list

III.   Child = length of list - 1

IV.  Parent = Child // 2

V.    While Child ≠ Parent and list[Child]’s cost < list[Parent] cost

A.   Swap list[Child] with list[Parent]

B.   Child = Parent

C.   Parent = Child // 2

Example Run:

def test():     heap = []     insert (heap, "A", 10)     print (heap)     insert (heap, "B", 15)     insert (heap, "C", 5)     print (heap)     insert (heap, "D", 18)     insert (heap, "E", 2)     print (heap)

Output:

>>> test()

[('A', 10)]

[('C', 5), ('A', 10), ('B', 15)]

[('E', 2), ('C', 5), ('A', 10), ('D', 18), ('B', 15)]

## 1b). Heap Serve (10)serve (list)

Returns the first element in the list.

II.    Last = Pop Last Element in list

III.   list = Last

IV.  Parent = 0

V.    While True

A.   Left = Parent * 2 + 1

B.   Right = Parent * 2 + 2

C.   If Left >= length of list

Else if Right >= length of list

1.    Swap list[Parent] and list[Left]

2.    Parent = Left

Else if list[Left]’s cost < list[Right]’s Cost

1.    Swap list[Parent] and list[Left]

2.    Parent = Left

Else

1.    Swap list[Parent] and list[Right]

2.    Parent = Right