Кучи – это широко используемые структуры данных, которые обеспечивают эффективный доступ к самому маленькому (или самому большому) элементу коллекции. Одной из важнейших операций в кучах является вставка новых элементов, что предполагает сохранение свойства кучи. В этой статье блога мы рассмотрим несколько методов вставки элементов в кучу, а также примеры кода на Python.

1. Метод 1: вставка в конец и всплеск:
   Этот метод включает в себя вставку нового элемента в конец кучи, а затем его повторную замену его родительским элементом до тех пор, пока свойство кучи не будет удовлетворено.

def insert(heap, value):
    heap.append(value)
    current_index = len(heap) - 1
    parent_index = (current_index - 1) // 2
    while current_index > 0 and heap[current_index] < heap[parent_index]:
        heap[current_index], heap[parent_index] = heap[parent_index], heap[current_index]
        current_index = parent_index
        parent_index = (current_index - 1) // 2
heap = [10, 15, 20, 30, 25, 5]
insert(heap, 12)
print(heap)  # Output: [5, 10, 12, 30, 25, 15, 20]

2. Метод 2: вставка в конец и куча вверх.
   Этот метод похож на предыдущий, но вместо многократной замены элементов он использует функцию heapify_upдля поддержания кучи. свойство.

def heapify_up(heap, index):
    parent_index = (index - 1) // 2
    if parent_index >= 0 and heap[index] < heap[parent_index]:
        heap[index], heap[parent_index] = heap[parent_index], heap[index]
        heapify_up(heap, parent_index)
def insert(heap, value):
    heap.append(value)
    heapify_up(heap, len(heap) - 1)
heap = [10, 15, 20, 30, 25, 5]
insert(heap, 12)
print(heap)  # Output: [5, 10, 12, 30, 25, 15, 20]

3. Метод 3. Вставка в конец и куча вниз:
   Этот метод вставляет новый элемент в конец кучи, а затем использует функцию heapify_downдля сохранения свойства кучи.

def heapify_down(heap, index):
    left_child_index = 2 * index + 1
    right_child_index = 2 * index + 2
    smallest = index
    if left_child_index < len(heap) and heap[left_child_index] < heap[smallest]:
        smallest = left_child_index
    if right_child_index < len(heap) and heap[right_child_index] < heap[smallest]:
        smallest = right_child_index
    if smallest != index:
        heap[index], heap[smallest] = heap[smallest], heap[index]
        heapify_down(heap, smallest)
def insert(heap, value):
    heap.append(value)
    heapify_down(heap, 0)
heap = [10, 15, 20, 30, 25, 5]
insert(heap, 12)
print(heap)  # Output: [5, 10, 12, 30, 25, 15, 20]

В этой статье мы рассмотрели различные методы вставки элементов в кучу. Мы обсудили три метода: вставка в конце и всплывание вверх, вставка в конце и накопление вверх, вставка в конце и накопление вниз. Каждый метод имеет свои преимущества и может быть более подходящим для различных сценариев. Понимание этих методов вставки имеет решающее значение для эффективной работы с кучами и другими структурами данных, использующими свойства кучи.

Реализуя эти методы вставки в Python, вы сможете улучшить свое понимание куч и их операций. Экспериментируя с различными сценариями и наборами данных, вы сможете понять тонкости вставки кучи и ее влияние на общую структуру кучи.

В целом, освоение методов вставки кучи имеет основополагающее значение для всех, кто работает с кучами или приоритетными очередями, поскольку это обеспечивает эффективное и точное управление данными.