Минимальное двоичное дерево кучи

Двоичное дерево с минимальной кучей — это двоичное дерево, в котором корневой узел имеет минимальный ключ в дереве.

Приведенное выше определение справедливо для всех поддеревьев дерева. Это называется свойством Min Heap.

Почти каждый узел, кроме двух последних слоев, должен иметь двух дочерних элементов. То есть это почти полное бинарное дерево, за исключением последних 2-х слоев.

Приведенное ниже дерево является примером двоичного дерева с минимальной кучей, поскольку сохраняются два вышеуказанных свойства.

Теперь, когда мы рассмотрели, что такое дерево минимальной кучи, давайте посмотрим, как мы можем его представить.

Представление дерева минимальной кучи

Двоичное дерево минимальной кучи обычно представляется в виде массива, который индексируется в соответствии со следующим форматом:

Корень всего дерева находится в arr[0].

Мы будем использовать индексацию, как показано на рисунке ниже. Здесь не очень сложно найти шаблон, который будет соответствовать приведенной выше таблице.

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

На приведенном выше рисунке показано представление массива дерева минимальной кучи.

Теперь, когда мы рассмотрели концепции, давайте перейдем к реализации этого на C!

Реализация дерева минимальной кучи

Мы будем использовать представление массива для построения дерева. Давайте начнем писать структуру для Min Heap.

typedef struct MinHeap MinHeap;
struct MinHeap {
    int* arr;
    // Current Size of the Heap
    int size;
    // Maximum capacity of the heap
    int capacity;
};

У нас будет массив элементов и размер, который обновляется по мере вставки или удаления элементов.

Массив также имеет емкость, которая указывает максимальный размер массива.

Есть несколько функций, которые нам нужно написать, чтобы указать, что мы представляем дерево минимальной кучи, например, найти родителя и дочерние элементы.

int parent(int i) {
    // Get the index of the parent
    return (i - 1) / 2;
}

int left_child(int i) {
    return (2*i + 1);
}

int right_child(int i) {
    return (2*i + 2);
}

int get_min(MinHeap* heap) {
    // Return the root node element,
    // since that's the minimum, by the min-heap
    // property
    return heap->arr[0];
}

Мы напишем функции для инициализации и освобождения кучи.

MinHeap* init_minheap(int capacity) {
    MinHeap* minheap = (MinHeap*) calloc (1, sizeof(MinHeap));
    minheap->arr = (int*) calloc (capacity, sizeof(int));
    minheap->capacity = capacity;
    minheap->size = 0;
    return minheap;
}

void free_minheap(MinHeap* heap) {
    if (!heap)
        return;
    free(heap->arr);
    free(heap);
}

После этого давайте теперь перейдем к тому, как мы можем вставлять элементы!

Вставка в минимальную кучу

Алгоритм включения прост. Это вставляет элемент в дерево.

Разбираем алгоритм:

• Во-первых, всегда вставляйте в конец дерева. Исходное положение вставленного элемента — последний уровень.
• Теперь нам нужно обновить позицию этого элемента, чтобы удовлетворялось свойство min-heap.
• Поскольку корневой узел каждого поддерева должен быть минимальным, проверьте поддерево его непосредственного родителя.
• Если родительский элемент больше этого вставленного элемента, нам нужно обновить его позицию, заменив его местами.
• Но это еще не все, так как свойство min-heap может быть нарушено в поддереве обновленного узла!
• Нам нужно продолжать обмен, пока мы не достигнем корневого узла, после чего мы закончим.

Чтобы понять эту процедуру, давайте возьмем пример.

Рассмотрим дерево ниже, имеющее только один элемент.

Давайте вставим элемент 40. Так как есть только один элемент, он вставляется в самый низ, и мы видим, что свойство min-heap выполняется, так как 10 < 40. Так что нет необходимости менять местами.

Далее мы вставим 50. Далее следует аналогичная процедура.

Затем мы вставим 5. Итак, теперь мы сначала вставляем в нижнюю часть дерева по индексу 3.

Свойство min heap нарушается для поддерева 1-3, а значит, и для всего дерева. Таким образом, мы должны продолжать менять местами родителя, пока не достигнем корня.

Итак, нам нужен еще один своп, так как снова нарушается свойство min-heap для поддерева с корнем в узле 0.

Хорошо. Теперь, когда мы визуализировали это, давайте запишем!

MinHeap* insert_minheap(MinHeap* heap, int element) {
    // Inserts an element to the min heap
    // We first add it to the bottom (last level)
    // of the tree, and keep swapping with it's parent
    // if it is lesser than it. We keep doing that until
    // we reach the root node. So, we will have inserted the
    // element in it's proper position to preserve the min heap property
    if (heap->size == heap->capacity) {
        fprintf(stderr, "Cannot insert %d. Heap is already full!\n", element);
        return heap;
    }
    // We can add it. Increase the size and add it to the end
    heap->size++;
    heap->arr[heap->size - 1] = element;

    // Keep swapping until we reach the root
    int curr = heap->size - 1;
    // As long as you aren't in the root node, and while the 
    // parent of the last element is greater than it
    while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) {
        // Swap
        int temp = heap->arr[parent(curr)];
        heap->arr[parent(curr)] = heap->arr[curr];
        heap->arr[curr] = temp;
        // Update the current index of element
        curr = parent(curr);
    }
    return heap; 
}

Теперь мы реализуем метод удаления.

Удалить из минимальной кучи

Прежде чем мы рассмотрим удаление элемента любого индекса, поскольку минимальная куча очень тесно связана с корнем, мы сначала рассмотрим удаление корня.

Чтобы удалить минимальный элемент (то есть корень), мы сделаем следующее:

• Обновить корень как последний элемент массива (дерева)
• Теперь мы удалим последний элемент внизу. Это похоже на замену и удаление в конце! Только потому, что нас больше не интересует корневое значение, мы просто обновляем его.
• Снова проблема в том, что нам нужно поддерживать свойство min-heap.
• Поэтому мы должны убедиться, что все дерево поддерживает это свойство. Для этого мы воспользуемся функцией heapify().

Итак, мы знаем, что метод удаления будет завершен после того, как мы также выполним метод heapify().

MinHeap* delete_minimum(MinHeap* heap) {
    // Deletes the minimum element, at the root
    if (!heap || heap->size == 0)
        return heap;

    int size = heap->size;
    int last_element = heap->arr[size-1];
    
    // Update root value with the last element
    heap->arr[0] = last_element;

    // Now remove the last element, by decreasing the size
    heap->size--;
    size--;

    // We need to call heapify(), to maintain the min-heap
    // property
    heap = heapify(heap, 0);
    return heap;
}

Процедура heapify()

Эта функция принимает индекс элемента index и поддерживает свойство минимальной кучи, заменяя его наименьшим элементом своего непосредственного поддерева.

Результирующее дерево будет удовлетворять свойству минимальной кучи.

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

После этого нам все еще нужно убедиться, что все дерево удовлетворяет этому. Итак, нам нужно рекурсивно вызывать процедуру на наименьшем элементе, пока мы не достигнем корня!

MinHeap* heapify(MinHeap* heap, int index) {
    // Rearranges the heap as to maintain
    // the min-heap property
    if (heap->size <= 1)
        return heap;
    
    int left = left_child(index); 
    int right = right_child(index); 

    // Variable to get the smallest element of the subtree
    // of an element an index
    int smallest = index; 
    
    // If the left child is smaller than this element, it is
    // the smallest
    if (left < heap->size && heap->arr[left] < heap->arr[index]) 
        smallest = left; 
    
    // Similarly for the right, but we are updating the smallest element
    // so that it will definitely give the least element of the subtree
    if (right < heap->size && heap->arr[right] < heap->arr[smallest]) 
        smallest = right; 

    // Now if the current element is not the smallest,
    // swap with the current element. The min heap property
    // is now satisfied for this subtree. We now need to
    // recursively keep doing this until we reach the root node,
    // the point at which there will be no change!
    if (smallest != index) 
    { 
        int temp = heap->arr[index];
        heap->arr[index] = heap->arr[smallest];
        heap->arr[smallest] = temp;
        heap = heapify(heap, smallest); 
    }

    return heap;
}

Теперь мы можем расширить эту функцию delete_minimum(), чтобы удалить любой элемент.

Удаление произвольного элемента

Это включает в себя только установку желаемого элемента на минимально возможное значение, которое будет get_min() - 1, поскольку оно должно быть меньше текущего минимума.

Теперь мы будем продолжать менять местами, пока не обновим позицию, чтобы новым корнем был этот элемент.

Теперь мы вернулись к нашей старой функции delete_minimum()! Мы можем просто удалить новый корень!

При этом вся наша процедура удаления будет выглядеть так:

MinHeap* delete_element(MinHeap* heap, int index) {
    // Deletes an element, indexed by index
    // Ensure that it's lesser than the current root
    heap->arr[index] = get_min(heap) - 1;
    
    // Now keep swapping, until we update the tree
    int curr = index;
    while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) {
        int temp = heap->arr[parent(curr)];
        heap->arr[parent(curr)] = heap->arr[curr];
        heap->arr[curr] = temp;
        curr = parent(curr);
    }

    // Now simply delete the minimum element
    heap = delete_minimum(heap);
    return heap;
}

Фу! Мы наконец закончили. Сейчас я покажу вам весь код вместе с функцией print() для визуализации дерева.

Полный код

#include <stdio.h>
#include <stdlib.h>

typedef struct MinHeap MinHeap;
struct MinHeap {
    int* arr;
    // Current Size of the Heap
    int size;
    // Maximum capacity of the heap
    int capacity;
};

int parent(int i) {
    // Get the index of the parent
    return (i - 1) / 2;
}

int left_child(int i) {
    return (2*i + 1);
}

int right_child(int i) {
    return (2*i + 2);
}

int get_min(MinHeap* heap) {
    // Return the root node element,
    // since that's the minimum
    return heap->arr[0];
}

MinHeap* init_minheap(int capacity) {
    MinHeap* minheap = (MinHeap*) calloc (1, sizeof(MinHeap));
    minheap->arr = (int*) calloc (capacity, sizeof(int));
    minheap->capacity = capacity;
    minheap->size = 0;
    return minheap;
}

MinHeap* insert_minheap(MinHeap* heap, int element) {
    // Inserts an element to the min heap
    // We first add it to the bottom (last level)
    // of the tree, and keep swapping with it's parent
    // if it is lesser than it. We keep doing that until
    // we reach the root node. So, we will have inserted the
    // element in it's proper position to preserve the min heap property
    if (heap->size == heap->capacity) {
        fprintf(stderr, "Cannot insert %d. Heap is already full!\n", element);
        return heap;
    }
    // We can add it. Increase the size and add it to the end
    heap->size++;
    heap->arr[heap->size - 1] = element;

    // Keep swapping until we reach the root
    int curr = heap->size - 1;
    // As long as you aren't in the root node, and while the 
    // parent of the last element is greater than it
    while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) {
        // Swap
        int temp = heap->arr[parent(curr)];
        heap->arr[parent(curr)] = heap->arr[curr];
        heap->arr[curr] = temp;
        // Update the current index of element
        curr = parent(curr);
    }
    return heap; 
}

MinHeap* heapify(MinHeap* heap, int index) {
    // Rearranges the heap as to maintain
    // the min-heap property
    if (heap->size <= 1)
        return heap;
    
    int left = left_child(index); 
    int right = right_child(index); 

    // Variable to get the smallest element of the subtree
    // of an element an index
    int smallest = index; 
    
    // If the left child is smaller than this element, it is
    // the smallest
    if (left < heap->size && heap->arr[left] < heap->arr[index]) 
        smallest = left; 
    
    // Similarly for the right, but we are updating the smallest element
    // so that it will definitely give the least element of the subtree
    if (right < heap->size && heap->arr[right] < heap->arr[smallest]) 
        smallest = right; 

    // Now if the current element is not the smallest,
    // swap with the current element. The min heap property
    // is now satisfied for this subtree. We now need to
    // recursively keep doing this until we reach the root node,
    // the point at which there will be no change!
    if (smallest != index) 
    { 
        int temp = heap->arr[index];
        heap->arr[index] = heap->arr[smallest];
        heap->arr[smallest] = temp;
        heap = heapify(heap, smallest); 
    }

    return heap;
}

MinHeap* delete_minimum(MinHeap* heap) {
    // Deletes the minimum element, at the root
    if (!heap || heap->size == 0)
        return heap;

    int size = heap->size;
    int last_element = heap->arr[size-1];
    
    // Update root value with the last element
    heap->arr[0] = last_element;

    // Now remove the last element, by decreasing the size
    heap->size--;
    size--;

    // We need to call heapify(), to maintain the min-heap
    // property
    heap = heapify(heap, 0);
    return heap;
}

MinHeap* delete_element(MinHeap* heap, int index) {
    // Deletes an element, indexed by index
    // Ensure that it's lesser than the current root
    heap->arr[index] = get_min(heap) - 1;
    
    // Now keep swapping, until we update the tree
    int curr = index;
    while (curr > 0 && heap->arr[parent(curr)] > heap->arr[curr]) {
        int temp = heap->arr[parent(curr)];
        heap->arr[parent(curr)] = heap->arr[curr];
        heap->arr[curr] = temp;
        curr = parent(curr);
    }

    // Now simply delete the minimum element
    heap = delete_minimum(heap);
    return heap;
}

void print_heap(MinHeap* heap) {
    // Simply print the array. This is an
    // inorder traversal of the tree
    printf("Min Heap:\n");
    for (int i=0; i<heap->size; i++) {
        printf("%d -> ", heap->arr[i]);
    }
    printf("\n");
}

void free_minheap(MinHeap* heap) {
    if (!heap)
        return;
    free(heap->arr);
    free(heap);
}

int main() {
    // Capacity of 10 elements
    MinHeap* heap = init_minheap(10);

    insert_minheap(heap, 40);
    insert_minheap(heap, 50);
    insert_minheap(heap, 5);
    print_heap(heap);
    
    // Delete the heap->arr[1] (50)
    delete_element(heap, 1);

    print_heap(heap);
    free_minheap(heap);
    return 0;
}

Выход

Min Heap:
5 -> 50 -> 40 -> 
Min Heap:
5 -> 40 -> 

Временная сложность реализации

Временные сложности вышеуказанных процедур указаны ниже:

Скачать код

Вы можете загрузить полный код в виде Github Gist, который я загрузил. Если у вас есть какие-либо вопросы по этому поводу, задавайте их в разделе комментариев ниже!

Заключение

В этой статье мы узнали, как мы можем представить двоичное дерево Min Heap, а также рассмотрели реализацию на C.

Рекомендации

• Иллюстрация Хипса из Кормена.
• Статья в Википедии о двоичных кучах