Last active
July 20, 2023 15:54
-
-
Save jul/3927135 to your computer and use it in GitHub Desktop.
Exact translation of an heap obfuscated algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
"""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) |
Line 176 had error while running. I changed it to:
print(".join([ %2d % i , offset , offset.join(l)]")
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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