proteus.StupidHeap module

A stupid implementation of a heap for fast marching methods

class proteus.StupidHeap.StupidHeap

Bases: object

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

valIndex = 1

isempty()

insert(key, val)

insertWithCheckForExistingKey(key, val)

pop(debugLevel=0)

return smallest value in heap, maintain heap property

updateNode(key, newval, debugLevel=0)

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

updateNodeWithMin(key, newval, debugLevel=0)

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)

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

downHeap(pos, debugLevel=0)

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()

printHeap()