Skip to content

Instantly share code, notes, and snippets.

@zulonas
Created April 5, 2020 16:38
Show Gist options
  • Save zulonas/63ced57f93db22e89be41a04a8d3af28 to your computer and use it in GitHub Desktop.
Save zulonas/63ced57f93db22e89be41a04a8d3af28 to your computer and use it in GitHub Desktop.
Max heap implementation using binary tree(in array) (Python)
#!/usr/bin/python3
#max heap implementation
class Bin_heap:
def __init__(self, input_heap = []):
self.heap = input_heap
if (input_heap):
self.build_heap()
def heapify(self, n, i):
larg = i #largest value
l_child = self.left_child(i)
r_child = self.right_child(i)
# check left child
if (l_child < n and self.heap[l_child] > self.heap[larg]):
larg = l_child
# check right child
if (r_child < n and self.heap[r_child] > self.heap[larg]):
larg = r_child
# swap and heapify subtree
if larg != i:
self.swap(larg, i)
self.heapify(n, larg)
def build_heap(self):
last = self.parent(len(self.heap))
for x in range(last, -1, -1):
self.heapify(len(self.heap), x)
def heap_sort(self):
for x in range(len(self.heap) - 1, 0, -1):
self.swap(0, x)
self.heapify(x, 0)
def left_child(self, i):
return (2 * i) + 1
def right_child(self, i):
return (2 * i) + 2
def parent(self, i):
return (i - 1) // 2
def perc_up(self, i):
if i == 0:
return
if self.heap[i] > self.heap[self.parent(i)]:
self.swap(i, self.parent(i))
self.perc_up(self.parent(i))
def insert(self, data):
self.heap.append(data)
self.perc_up(len(self.heap) - 1)
print(self.heap)
def swap(self, a, b):
self.heap[a], self.heap[b] = self.heap[b], self.heap[a]
arr = [2, 7, 26, 25, 19, 52, 50, 51]
print(arr)
heap = Bin_heap(arr)
print(arr)
heap.heap_sort()
print(arr)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment