Heap deletion
Anonymous
plain_text
02/26/2026 1:31 AM
2.7 KB
17
Indexable
class MinHeap:
def __init__(self):
self.heap = []
# Insert element
def insert(self, value):
self.heap.append(value)
self.heapify_up(len(self.heap)-1)
def heapify_up(self, index):
while index > 0:
parent = (index -1)//2
if self.heap[index] < self.heap[parent]:
self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
index = parent
else:
break
def peek(self):
return self.heap[0] if self.heap else None
class MaxHeap:
def __init__(self):
self.heap = []
# Insert element
def insert(self, value):
self.heap.append(value)
self.heapify_up(len(self.heap)-1)
def heapify_up(self, index):
while index > 0:
parent = (index -1)//2
if self.heap[index] > self.heap[parent]:
self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
index = parent
else:
break
def delete(self):
if len(self.heap) == 0:
return None
if len(self.heap) == 1:
return self.heap.pop()
root = self.heap[0]
self.heap[0] = self.heap.pop()
self.heapify_down(0)
return root
def heapify_down(self, index):
size = len(self.heap)
while True:
left = 2* index +1
right 2* index +2
biggest = index
if left < size and self.heap[left] > self.heap[biggest]:
biggest = left
if right < size and self.heap[right] > self.heap[biggest]:
biggest = right
if biggest != index:
self.heap[index], self.heap[biggest] = self.heap[biggest], self.heap[index]
index = biggest
else:
breakEditor is loading...
Leave a Comment