Всем привет.

Начал изучение алгоритмов, наткнулся на работу с пирамидами и как-то не смог найти объяснения для людей околонулевого уровня.

Да, есть статьи вроде этой, но мне кажется, что в них немного не хватает контекста, фундамента на котором всё строится.

В этой статье я попытаюсь исправить это упущение.

Будут рассмотрены следующие подтемы:

• Heap/пирамида как структура данных. Её устройство и построение невозрастающей пирамиды.

• Объяснение на пальцах некоторых сопутствующих тем(что такое деревья, например).

• Операции с heap(сортировка, очередь с приоритетами) время их работы и, конечно, исходный код на C.

При написании опирался на CLRS: "Алгоритмы: построение и анализ" и многочисленные статьи.

Heap как структура данных

В различных источниках перевод для слова heap может выглядеть как "пирамида" или "куча". Чтобы не путаться, в этой статье мы будем использовать только "пирамиду".

Если посмотреть в википедию, можно найти следующее определение:

"Heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node."

Для тех, кто знаком с понятием "дерева" всё выглядит более-менее понятно. Однако, для некоторых, эта тема нова и поэтому будет рассмотрена ниже.

Деревья

Итак, что за деревья-то?

Если говорить, немного абстрактно, дерево представляет собой набор объектов называемых узлами, которые соединены между собой рёбрами.

Каждый узел содержит значение или данные и может иметь или не иметь дочерние узлы.
Узлы без дочерних узлов называются листьями.

По-факту, дерево представляет собой обыкновенный массив(список, вектор и т.д.). Отличается дерево от него тем, что в упорядоченном виде оно выглядит не так, как привычный всем линейный массив.

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

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

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

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

Абстрактное представление пирамиды показано на картинке ниже

Массив, который представляет это дерево выглядит следующим образом:
[20, 11, 15, 6, 9, 7, 8, 1, 3, 5]

Итак, что мы здесь видим?

• Узел с индексом 0 и значением 20 является корнем дерева. Находится в самом верху и имеет наибольшее значение.

• Корневой узел имеет два дочерних узла с индексами 1, 2 и значениями 11 и 15.

• Каждый из этих узлов имеет по два собственных дочерних узла.

• Узлы, не имеющие дочерних узлов называются листьями. Примерами служат узлы с индексами 6, 5, 9, 8, 7.

• Узлы, имеющие один и тот же родительский узел, называются родственными (или братьями).

• Не до конца заполненный последний уровень, за счёт узла с индексом 4, который имеет всего один дочерний узел.

Это не все определения, связанные с деревьями, но нам пока хватит.

Надеюсь, стало немного понятнее, о каких деревьях идёт речь. Далее, будем говорить о них только в рамках работы с пирамидой.

Построение пирамиды

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

Но не каждый массив входных данных соответствует этим правилам. Зачастую, над массивами требуется провести ряд операций, чтобы привести их в надлежащий вид.

Для того, чтобы массив(пирамида) соответствовал свойству невозрастающих пирамид, для каждого из узлов, которые содержат дочерние элементы, мы вызываем процедуру heapMaxify, которая, в случае, если узел имеет значение меньше дочернего, сплавляет его вниз по пирамиде.

Процедура heapMaxify для одного узла выглядит следующим образом:

//Для удобства разместим это здесь. Макросы для поиска левого и правого
//дочерних узлов
#define LEFT(i) (2*i)
#define RIGHT(i) (LEFT(i)+1)

//процедура, с помощью которой, узел дерева, в случае
//если он меньше дочернего,
//сплавляется вниз по дереву(его индекс в массиве увеличивается)
void heapMaxify(int *array, int size, int i) 
{      
    int l, r;
    //Изначально, мы предполагаем, что узел с индексом i
  	//обладает наибольшим значением
    int largest = i;

    //определяем левый и правый дочерние узлы
    l = LEFT(i);
    r = RIGHT(i);

    //если левый дочерний узел больше чем корень
  	//поддерева(корень с индексом largest)
    //то мы изменяем largest на индекс левого
  	//или правого дочернего узла
    if (l < size && array[l] > array[largest]) {
        largest = l;
    }
    if (r < size && array[r] > array[largest]) {
        largest = r;
    }

    //если всё-таки значение изначально проверяемого 
  	//узла с индексом i не является самым большим
    //то проверяемый узел и узел с большим значением меняются местами
    if (largest != i) {
        swap(array, i, largest);
        
        //Рекурсивно вызываем функцию, чтобы в случае чего
      	//отправить элемент ниже по пирамиде
        heapMaxify(array, size, largest);
    }
}

//Освобождаем имена
#undef LEFT
#undef RIGHT

Как я и сказал, вызов происходит в функции heapBuild для каждого узла содержащего дочерние элементы:

void heapBuild(int *array, int size) 
{   
    //Проходим по всем узлам, 
  	//имеющим дочерние элементы и, если требуется,
    //"сплавляем" их вних по пирамиде
    for (int i = size / 2 - 1;i >= 0; i--) {
        heapMaxify(array, size, i);
    }
}

В результате мы получим массив, который удовлетворяет свойствам невозрастающей пирамиды.

Далее можно выполнять операции с пирамидой. Первой рассмотрим самую популярную - heapSort. Выглядит она следующим образом:

void heapSort(int *heap, int size) 
{   
    for (int i = size-1; i > 0; i--) {
        swap(heap, 0, i);
        heapMaxify(heap, i, 0);
    } 
}

Начиная с последнего, каждый элемент меняется значениями с корнем дерева. С этого момента мы не работаем с последним элементом. В итоге, вся пирамида является упорядоченной и свойство пирамиды нарушает только корень, который меньше своих дочерних узлов. Чтобы это исправить, мы выполняем процедуру heapMaxify по отношению к нему и всё становится на свои места. Проделав эту операцию со всеми элементами, мы, в конечном итоге, отсортируем пирамиду по возрастанию.

Ну и main.c для полноты:

#include <stdio.h>
#include "heapify.c"

int main(int argc, char **argv) {

    int inputArray[] = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1};
  	
  	//вычисляем длину массива
    int size = sizeof(array) / sizeof(array[0]);
  	
  	//Создаём переменную в которую будет помещён входной массив.
  	//В дальнейшем нам понадобится изменять размер массива и поэтому
  	//стоит создать сейчас его с помощью выделения памяти malloc'ом.
  	int *heap = (int*)malloc(size * sizeof(inputArray[0]));
  
  	//Копируем элементы из входного массива
    memcpy(inputArray, heap, sizeof(inputArray));
  
    heapBuild(array, size);
  	//после преобразования массив выглядит так:
		// [16, 14, 10, 4, 8, 9, 3, 2, 7, 1]
  
    heapSort(array, size);
    //и отсортированный:
  	// [1, 2, 3, 4, 7, 8, 9, 10, 14, 16]
    return 0;
}

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

Не одной сортировкой едины

Пирамидальная сортировка действительно стоящий алгоритм, однако некоторые алгоритмы вроде быстрой сортировки, во многих ситуациях, окажутся более эффективны.
Несмотря на это, пирамида как структура данных имеет и другие применения. Здесь мы рассмотрим только одно - очередь с приоритетами

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

Очередь с приоритетами имеет ту же структуру, что и пирамида и поддерживает следующие операции(не только, но рассмотрим мы только их):

• Insert(A, x) - вставляет элемент x в очередь A.

• Maximum(A) - возвращает элемент с наибольшим приоритетом(значением элемента).

• Extract-Max(A) - возвращает элемент с наибольшим приоритетом и удаляет его из очереди.

• Increase-Key(A, x, k) - увеличивает значение ключа x до значения k. k не может быть меньше предыдущего значения x.

В конце также будет приведена таблица с временем работы операций.

При реализации пирамид и проведения над ними операций, удобнее использовать структуру вида:

typedef struct {
    int *h; //массив в котором будут храниться значения узлов пирамиды
    int sizeOfHeap; //Размер пирамиды, который будет изменяться.
    int sizeOfArray; //Фактический размер оставшегося массива
} heapStr; //название

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

Далее, будет приведён код, который строит пирамиду на основе передаваемого массива и его размера:

//Выделение памяти для структуры
heapStr * heapInit(size_t size) 
{
    heapStr *h;
    h = malloc(sizeof(heapStr *));
    h->h = malloc(sizeof(int) * (1+size));
    h->sizeOfArray = (int) size;
    h->sizeOfHeap = 0;
    return h;
}

//Освобождение памяти
void heapFree(heapStr *h) {
    free(h->h);
    free(h);
}

//Инициализирует структуру и из входного массива создаёт
//невозрастающую пирамиду
heapStr * heapBuild(int *a, int size) 
{
    heapStr *h;
    //Память для структуры
    h = heapInit(size);
    //Копирование элементов из входного массива
    //в массив, который находится в структуре
    memcpy((h->h), a, sizeof(int) * size);

    h->sizeOfHeap = size;
    h->sizeOfArray = size;

    //упорядочивание пирамиды
    for (int i = size/2; i >= 0; i--) {
        heapMaxify(h, i);
    }

    return h;
}

Все функции, работающие ранее, теперь принимают в качестве аргументов, вместо массива и размера, просто структуру heapStr.

Начнём с реализации процедуры Extract-Max:

int queueMax(heapStr *h) {
    return h->h[0];
}

int queueExtraMax(heapStr *h)
{
    //проверка на наличие элементов в пирамиде
    if (h->sizeOfHeap < 1) {
        printf("Size of heap must be bigger than 0\n");
        exit(1);
    }
    int max = h->h[0];

    //Присваиваем первому(пока самому большому) элементу значение
    // последнего, чтобы оно не "потерялось"
    h->h[0] = h->h[h->sizeOfHeap-1];

    // Выделение нового объёма памяти для массива,
    // которое меньше на один int. 
    // Отсекаем последний(бывший самый большой) элемент.
    int memSize = (h->sizeOfHeap) * sizeof(h->h[0]);
    h->sizeOfHeap--;
    h->sizeOfArray--;
    h->h = (int*)realloc(h->h, memSize);

    // Приводим пирамиду в порядок.
    heapMaxify(h, 0);
    return max;
}

Реализация Increase-Key:

//Ещё один макрос для определения родительского узла
#define PARENT(i) ((i-1)/2)

int queueIncreaseKey(heapStr *h, int i, int key)
{
  	//Больше ли новое значение
    if (key < h->h[i]) {
        printf("New key smaller than previous\n");
        exit(0);
    }
    //Определяем родительский узел
    int p = PARENT(i)
    h->h[i] = key;
    // Подобие heapMaxify, только здесь
    // узел поднимается вверх по дереву приводя пирамиду в порядок
    while (i > 0 && h->h[p] < h->h[i]) {
        swap(h->h, i, p);
        i = PARENT(i);
        p = PARENT(i)
    }
    return 0;
}

#undef PARENT

Insert:

void queueInsertKey(heapStr *h, int key) 
{
    ++h->sizeOfHeap;

    //Устанавливаем наименьшее возможное число
    int bits = 8 * sizeof(int);
    h->h[h->sizeOfHeap-1] = -(1LL<<(bits-1));

    int memSize = (h->sizeOfHeap) * sizeof(h->h[0]);
    h->h = (int*)realloc(h->h, memSize);
    //Вызываем процедуру, чтобы впихнуть новый ключ
    // и построить дерево уже с ним
    queueIncreaseKey(h, h->sizeOfHeap-1, key);
}

main для примера:

#include "heapify.c"

int main(int argc, char **argv) {
    int a[] = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1};
    int size = sizeof(a) / sizeof(a[0]);
    heapStr *h;
  
		//построение пирамиды
    h = heapBuild(a, size);

    //изменение значения ключа с индексом 4 на значаение 17
    queueIncreaseKey(h, 4, 17); //[17, 16, 10, 8, 14, 9, 3, 2, 4, 1]

    //Получение и удаление максимального значения
    int max = queueExtraMax(h);//17

    //Добавление ключа
    queueInsertKey(h, 100);//[100, 16, 10, 8, 14, 9, 3, 2, 4, 1]
  
  	//освобождение памяти
    heapFree(h);
    return 0;
}

И обещанная таблица времени работы основных алгоритмов:

Итог

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

Конечно, написанное выше - лишь малая часть того, что относится к теме, однако для базового понимания, что, как и зачем - вполне сойдёт.

Надеюсь, вы узнали для себя хоть что-то новое. Если вдруг подобные разборы "на пальцах" зайдут - буду писать и дальше.

Всех благ!