Created
June 28, 2025 12:12
-
-
Save sina-programer/245e80f5996444d3343de0b9e32df925 to your computer and use it in GitHub Desktop.
implementation of Max-Heap data structure class in python from scratch
This file contains hidden or 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
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