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:
                break
Editor is loading...
Leave a Comment