Пирамиды и пирамидальная сортировка - EcsFlash/DataTypes GitHub Wiki

Структура данных под названием пирамида(heap) представляет собой хитроумную частичную упорядоченную структуру данных, которая в особенности хорошо подходит для реализации очередей с приоритетами.

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

1. Требование к форме дерева. Бинарное дерево практически полное или просто полное, т.е. все его уровни заполнены, за исключением, возможно, последнего уровня, в котором могут отсутствовать некоторые крайние справа листья.
2. Требование доминирования родительских узлов. Ключ в каждом узле не меньше ключей в его дочерних узлах.

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

void toDown(int root_index) {
    while (true) {
        int leftSon_index = 2 * root_index + 1;
        int rightSon_index = 2 * root_index + 2;
        int toSwap_index = root_index;
        if (leftSon_index < heap.size() && heap[leftSon_index] > heap[toSwap_index]) {
            toSwap_index = leftSon_index;
        }
        if (rightSon_index < heap.size() && heap[rightSon_index] > heap[toSwap_index]) {
            toSwap_index = rightSon_index;
        }
        if (toSwap_index != root_index) {
            swap(heap[root_index], heap[toSwap_index]);
            root_index = toSwap_index;
        }
        else {
            break;
        }
    }
}
void fromArray(vector<int> arr) {
    heap = arr;
    for (int i = heap.size() / 2 - 1; i >= 0; i--) {
        toDown(i);
    }
}