Exact translation of an heap obfuscated algorithm

heapify.py

"""A heap is a recipie to represent an array as a 
binary tree.
A binary tree is a convenient structure for 
manipulating ordered data. 
Said simply: 
we implement a binary tree abstraction on top of an array.
this tree as the following properties:
any child value is smaller than its parent's value
left child is greater than right child.

Mostly used either to implement a priority queue
or a binary tree view on an array


"""


# moving in the heap (fonctions matching array offsets to position in a tree

def parent_offset(offset):
    return offset>>1

def left_offset(offset):
    return 2*offset

def right_offset(offset):
    return 2*offset + 1

class SENTINEL(object):
    pass

def build_heap(_array):
    """transform an array in such a way that heap properties are ensured"""
    for i in range((len(_array)-1)>>1,0,-1):
        heapify(_array,i)

def heapify(_array,index=1, heap_size=SENTINEL):
    """bubble downs the value at specified index to place it correct in the heap.
    heap_size can be used internally for optimization purpose"""
    if heap_size == SENTINEL:
        heap_size= len(_array)
    a_child_is_bigger= True
    while a_child_is_bigger:
        largest= index
        left_pos, right_pos = left_offset(index), right_offset(index)

        #check left
        if left_pos < heap_size and _array[left_pos] > _array[index]:
            largest= left_pos

        #check right
        if right_pos < heap_size and _array[right_pos]>_array[largest]:
            largest= right_pos

        if largest == index:
            # we are finally the king of the hill, end of story
            a_child_is_bigger= False
        else:
            #swap with child // bubble down
            _array[index], _array[largest] = _array[largest], _array[index]
            index= largest

def heapsort(_array):
    """in place sort"""
    build_heap(_array)
    heap_size= len(_array)-1
    root=1
    for i in range(heap_size,root,-1):
        _array[root], _array[i] = _array[i], _array[root]
        heap_size -= 1
        heapify(_array, root, heap_size) 

def extract_max(_array,heap_size=SENTINEL):
    """extract the maximum value from the heap and ensure heap properties are kept"""
    if heap_size==SENTINEL:
        heap_size=len(_array)
    if heap_size < 1:
        raise Exception("Underflow error")
    top=1
    #index of lowest possible index
    lowest=heap_size-1
    _max,_array[top] = _array[1], _array[lowest]
    # we bubble down the min element to place it in the right place.
    heapify(_array,top, heap_size)
    return _max

def heap_insert(_arr, value):
    """insert a value while keeping heap properties."""
    root=1
    # we start at the lowest position possible
    index=len(_arr)
    _arr += [ SENTINEL ]
    parent_index=parent_offset(index)
    must_swap_with_top = index>root and _arr[parent_index]<value
    while must_swap_with_top:
        #swapping
        _arr[index] = _arr[parent_index]
        index = parent_index
        parent_index=parent_offset(index)
        must_swap_with_top = index>root and _arr[parent_index]<value
    _arr[index]=value


def out_of_bound(func):
    def wrapper(*a,**kw):
        try:
            res=func(*a,**kw)
        except ValueError:
            return SENTINEL
        return res
    return wrapper

class Heap(object):
    def __init__(self, an_array):
        build_heap(an_array)
        # beware first usable element is at position 1
        # this helps keeping straightforward computation 
        # of left/right/top but since it is an internal representation...
        self._data=an_array

    def heapify(self,pos=1):
        heapify(self._data,pos)

    def sort(self):
        self.heapify(self._data)

    def insert(self, value):
        heap_insert(self._data,value)

    def extract_max(self):
        extract_max(self._data)

    @out_of_bound
    def top(self):
        return self._data[1]
   
    def __getitem__(self,index):
        return self._data[index]

    def __setitem__(self, index, value):
        self._data[index]=value

    def size(self):
        return len(self._data) - 1

    @out_of_bound
    def left(self, value):
        return self[left_offset(self._data.index(value))]

    @out_of_bound
    def right(self,value):
        return self[right_offset(self._data.index(value))]

    @out_of_bound
    def parent(self,value):
        return self[parent_offset(self._data.index(value))]


    def print_tree(self):
        level =  [ 1 ]
        heap_size=len(self._data)
        to_print= []
        
        while len(level):
            to_print += [ [ "%d:%s" % (i, str(self[i])) for i in level ] ]
            new_level=[]
            for l in level:
                left,right=  left_offset(l), right_offset(l) 
                if left < heap_size:
                    new_level += [ left ]
                if right < heap_size:
                    new_level += [ right ]
            level = new_level
        for i,l in enumerate(to_print):
            offset =  (2 ** ( len(to_print) - i )) * " "
            print("".join([ %2d % i , offset , offset.join(l)])





orig=[ SENTINEL, 16,4,10, 14, 7 , 9, 3, 2, 8 ,1 ]
x = [ i for i in orig ]
y=Heap([ i for i in  x ])
heapify(x,2)
right_answer=[ SENTINEL,16,14,10, 8,7,9,3,2,4,1 ]
assert x == [ SENTINEL,16,14,10, 8,7,9,3,2,4,1 ]
heapsort(x)
print(y._data)
print(x)
build_heap(orig)
print(orig)

Hum hum
I now have the feeling a bubbling_up and bubbling down fonction are extractable, and that it could be a min-max-HEAP very easily

Line 176 had error while running. I changed it to:
print(".join([ %2d % i , offset , offset.join(l)]")