Created
April 5, 2020 16:38
-
-
Save zulonas/63ced57f93db22e89be41a04a8d3af28 to your computer and use it in GitHub Desktop.
Max heap implementation using binary tree(in array) (Python)
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
#!/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