Create a gist now

Instantly share code, notes, and snippets.

@jul /heapify.py
Last active Oct 11, 2015

What would you like to do?
Exact translation of an heap obfuscated algorithm
"""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
Owner

jul commented Oct 21, 2012

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment