Skip to content

Instantly share code, notes, and snippets.

@sina-programer
Created June 28, 2025 12:12
Show Gist options
  • Save sina-programer/245e80f5996444d3343de0b9e32df925 to your computer and use it in GitHub Desktop.
Save sina-programer/245e80f5996444d3343de0b9e32df925 to your computer and use it in GitHub Desktop.
implementation of Max-Heap data structure class in python from scratch
class Node:
def __init__(self, identifier, priority):
self.identifier = identifier
self.priority = priority
def set_priority(self, value):
self.priority = value
def __gt__(self, other):
return self.priority > other.priority
def __repr__(self):
return f"Node({self.identifier}, priority={self.priority})"
class MaxHeap:
def __init__(self):
self.array = []
@classmethod
def left(cls, idx):
return 2 * idx + 1
@classmethod
def right(cls, idx):
return 2 * idx + 2
@classmethod
def parent(cls, idx):
return (idx - 1) // 2
@property
def size(self):
return len(self.array)
def is_empty(self):
return self.size == 0
def get_maximum(self):
if not self.is_empty():
return self.array[0]
def swap(self, i, j):
self.array[i], self.array[j] = self.array[j], self.array[i]
def get_node_by_index(self, idx):
if 0 <= idx < self.size:
return self.array[idx]
def get_index_by_node(self, node):
return self.array.find(node)
def print(self):
level = 0
index = 0
while index < self.size:
n = 2 ** level
new_index = index + n
row = self.array[index : new_index]
print(' - '.join(map(str, row)))
index = new_index
level += 1
def increase_priority(self, i, new_priority):
node = self.array[i]
if new_priority < node.priority:
print('can not decrease priority')
return
node.set_priority(new_priority)
while i > 0:
node = self.array[i]
p = self.parent(i)
parent = self.array[p]
if parent.priority >= node.priority:
break
self.swap(i, p)
i = p
def insert(self, identifier, priority):
node = Node(identifier, -float('inf'))
self.array.append(node)
self.increase_priority(self.size-1, priority)
return node
def heapify(self, idx=0):
left = self.left(idx)
right = self.right(idx)
largest = idx
if (left < self.size) and (self.array[left] > self.array[largest]):
largest = left
if (right < self.size) and (self.array[right] > self.array[largest]):
largest = right
if largest != idx:
self.swap(idx, largest)
self.heapify(largest)
def extract_max(self):
if self.is_empty():
return
maximum = self.get_maximum()
self.array[0] = self.array.pop(-1)
self.heapify()
return maximum
def delete(self, idx):
self.increase_priority(idx, float('inf'))
return self.extract_max()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment