(l)
| 2 | from collections import defaultdict |
| 3 | |
| 4 | def PrimsAlgorithm(l): |
| 5 | |
| 6 | nodePosition = [] |
| 7 | def getPosition(vertex): |
| 8 | return nodePosition[vertex] |
| 9 | |
| 10 | def setPosition(vertex, pos): |
| 11 | nodePosition[vertex] = pos |
| 12 | |
| 13 | def topToBottom(heap, start, size, positions): |
| 14 | if start > size // 2 - 1: |
| 15 | return |
| 16 | else: |
| 17 | if 2 * start + 2 >= size: |
| 18 | m = 2 * start + 1 |
| 19 | else: |
| 20 | if heap[2 * start + 1] < heap[2 * start + 2]: |
| 21 | m = 2 * start + 1 |
| 22 | else: |
| 23 | m = 2 * start + 2 |
| 24 | if heap[m] < heap[start]: |
| 25 | temp, temp1 = heap[m], positions[m] |
| 26 | heap[m], positions[m] = heap[start], positions[start] |
| 27 | heap[start], positions[start] = temp, temp1 |
| 28 | |
| 29 | temp = getPosition(positions[m]) |
| 30 | setPosition(positions[m], getPosition(positions[start])) |
| 31 | setPosition(positions[start], temp) |
| 32 | |
| 33 | topToBottom(heap, m, size, positions) |
| 34 | |
| 35 | # Update function if value of any node in min-heap decreases |
| 36 | def bottomToTop(val, index, heap, position): |
| 37 | temp = position[index] |
| 38 | |
| 39 | while(index != 0): |
| 40 | if index % 2 == 0: |
| 41 | parent = int( (index-2) / 2 ) |
| 42 | else: |
| 43 | parent = int( (index-1) / 2 ) |
| 44 | |
| 45 | if val < heap[parent]: |
| 46 | heap[index] = heap[parent] |
| 47 | position[index] = position[parent] |
| 48 | setPosition(position[parent], index) |
| 49 | else: |
| 50 | heap[index] = val |
| 51 | position[index] = temp |
| 52 | setPosition(temp, index) |
| 53 | break |
| 54 | index = parent |
| 55 | else: |
| 56 | heap[0] = val |
| 57 | position[0] = temp |
| 58 | setPosition(temp, 0) |
| 59 | |
| 60 | def heapify(heap, positions): |
| 61 | start = len(heap) // 2 - 1 |
no test coverage detected