task1 - master - evabaraniuk/homework

task1
105 строк3 KB
evabaraniuk
update task1
07 июн 2025, 13:23
07 июн 2025, 13:2364cf9d1
class BinaryHeap:
    def __init__(self, is_min_heap=True):
        self.heap = []
        self.is_min_heap = is_min_heap
    
    def _compare(self, a, b):
        if self.is_min_heap:
            return a < b
        else:
            return a > b
    
    def _parent(self, i):
        return (i - 1) // 2
    
    def _left_child(self, i):
        return 2 * i + 1
    
    def _right_child(self, i):
        return 2 * i + 2
    
    def heapify_up(self, i):
        """
        Восстанавливает свойство кучи снизу вверх начиная с индекса i
        Инвариант: элемент может нарушать свойство кучи только со своим родителем
        """
        while i > 0:
            parent_i = self._parent(i)
            if self._compare(self.heap[i], self.heap[parent_i]):
                self.heap[i], self.heap[parent_i] = self.heap[parent_i], self.heap[i]
                i = parent_i
            else:
                break
    
    def heapify_down(self, i):

        while True:
            smallest = i
            left = self._left_child(i)
            right = self._right_child(i)
            
            if left < len(self.heap) and self._compare(self.heap[left], self.heap[smallest]):
                smallest = left
            
            if right < len(self.heap) and self._compare(self.heap[right], self.heap[smallest]):
                smallest = right
            
            if smallest != i:
                self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
                i = smallest
            else:
                break
    
    def insert(self, value):
        self.heap.append(value)
        self.heapify_up(len(self.heap) - 1)
    
    def extract_top(self):
        if not self.heap:
            raise IndexError("Heap is empty")
        
        if len(self.heap) == 1:
            return self.heap.pop()
        
        top = self.heap[0]
        self.heap[0] = self.heap.pop()
        self.heapify_down(0)
        return top
    
    def build(self, array):
        self.heap = array[:]
        # Начинаем с последнего родительского узла
        for i in range(len(self.heap) // 2 - 1, -1, -1):
            self.heapify_down(i)
    
    def is_heap(self):
        for i in range(len(self.heap)):
            left = self._left_child(i)
            right = self._right_child(i)
            
            if left < len(self.heap) and not self._compare(self.heap[i], self.heap[left]):
                return False
            if right < len(self.heap) and not self._compare(self.heap[i], self.heap[right]):
                return False
        return True


if __name__ == "__main__":
    # Тестирование
    heap = BinaryHeap()
    
    # Тест insert и extract
    heap.insert(3)
    heap.insert(1)
    heap.insert(4)
    heap.insert(1)
    heap.insert(5)
    
    print("Куча после вставок:", heap.heap)
    print("Является кучей:", heap.is_heap())
    
    # Тест build
    heap2 = BinaryHeap()
    heap2.build([9, 5, 6, 2, 3, 7, 1, 4, 8])
    print("Куча после build:", heap2.heap)
    print("Является кучей:", heap2.is_heap())