Exact translation of an heap obfuscated algorithm (validating python syntax rules)

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 = TreeView([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