proteus.StupidHeap module

A stupid implementation of a heap for fast marching methods

Inheritance diagram of proteus.StupidHeap

class proteus.StupidHeap.StupidHeap[source]

Min Heap

heap = [(key,val), ...] such that heap[i][1] <= heap[2*i+1][1], heap[2*i+2][1] heapPos= {key:i} heap[heapPos[key]]=val

keyIndex = 0[source]
valIndex = 1[source]
isempty()[source]
insert(key, val)[source]
insertWithCheckForExistingKey(key, val)[source]
pop(debugLevel=0)[source]

return smallest value in heap, maintain heap property

updateNode(key, newval, debugLevel=0)[source]

modify value associated with key and restore heap property requires that key exist in heap

updateNodeWithMin(key, newval, debugLevel=0)[source]

modify value associated with key and restore heap property requires that key exist in heap

this version only updates value if new value is less

upHeap(pos, debugLevel=0)[source]

recursively move node at pos up the heap while it is less than its parent

downHeap(pos, debugLevel=0)[source]

assume left and right children of pos are heap, but left or right child < pos

promote smaller of children of node at pos, then repeat on its subheap

then put original value at pos and work back up

checkHeap()[source]
printHeap()[source]