Практика 2 октября. Сортировка подсчётом, цифровая сортировка, двоичная куча

Практика из двух частей. В первой разобрали линейные сортировки: сортировку подсчётом и построенную на ней цифровую (Radix sort) в двух вариантах, LSD и MSD. Они обходят нижнюю оценку $n\log n$, потому что вообще не сравнивают элементы. Во второй части, немного опережая лекции, началась новая тема: приоритетная очередь и двоичная куча, которая хранится в обычном массиве.

1. Лабораторная по сортировкам

В начале пары обсудили лабораторную 1 «Сортировки: музыкальный стриминг».

2. Сортировка подсчётом

2.1. Зачем сортировки без сравнений

На прошлой практике было доказано, что любая сортировка, основанная на сравнениях, в худшем случае не быстрее $n\log n$ (конспект). Сортировка подсчётом и цифровая сортировка работают за линейное время, потому что на эту оценку не попадают: элементы не сравниваются друг с другом, а раскладываются по своим значениям.

Из курса важно вынести не код конкретных сортировок, а этот концепт: нижняя оценка верна только для своей модели вычислений, и выйти из модели иногда выгоднее, чем оптимизировать внутри неё.

2.2. Простая версия

Пусть все значения целые и лежат в диапазоне $[\min;\max]$. Обозначим $k=\max-\min+1$ — сколько разных значений вообще может встретиться.

1. Одним проходом найти минимум и максимум.
2. Завести массив счётчиков $C$ длины $k$ и одним проходом посчитать, сколько раз встречается каждое значение.
3. Пройти по $C$ слева направо и выписать каждое значение $v$ столько раз, сколько оно встретилось.

void counting_sort(vector<int>& a) {
    if (a.empty()) return;
    auto [mn, mx] = minmax_element(a.begin(), a.end());
    int lo = *mn, k = *mx - *mn + 1;
    vector<int> c(k, 0);
    for (int x : a) c[x - lo]++;          // сдвиг на lo: годится и для отрицательных
    int pos = 0;
    for (int v = 0; v < k; v++)
        while (c[v]-- > 0) a[pos++] = v + lo;
}

Эта версия годится только для «голых» чисел: она не переставляет элементы, а пишет значения заново. Если сортировать объекты по ключу (песни по году, студентов по баллу), сами объекты так не восстановить.

2.3. Версия с префиксными суммами

Для объектов $C$ превращают в префиксные суммы: после этого $C[v]$ — сколько элементов имеют ключ не больше $v$. Значит, последний элемент с ключом $v$ должен встать на позицию $C[v]-1$, предпоследний — на $C[v]-2$ и так далее.

Остаётся пройти по исходному массиву справа налево, ставить каждый элемент на позицию $C[\text{ключ}]-1$ в новый массив $B$ и уменьшать счётчик.

void counting_sort(vector<int>& a) {
    if (a.empty()) return;
    auto [mn, mx] = minmax_element(a.begin(), a.end());
    int lo = *mn, k = *mx - *mn + 1;
    vector<int> c(k, 0);
    for (int x : a) c[x - lo]++;
    for (int v = 1; v < k; v++) c[v] += c[v - 1];  // c[v] = сколько элементов <= v
    vector<int> b(a.size());
    for (int i = (int)a.size() - 1; i >= 0; i--)   // справа налево
        b[--c[a[i] - lo]] = a[i];
    a = move(b);
}

Почему проход справа налево. Из двух равных элементов правый встречается первым и занимает правую из свободных позиций своего ключа. Левый попадает левее. Порядок равных элементов сохраняется, то есть сортировка устойчива. Если идти слева направо, равные элементы встанут в обратном порядке.

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

2.4. Время и память

По времени алгоритм — это несколько линейных проходов подряд:

По памяти — массив $C$ длины $k$ и, в версии с префиксными суммами, выходной массив $B$ длины $n$: $\Theta(n+k)$. В простой версии только $\Theta(k)$.

Отсюда и главное ограничение: подсчёт хорош, только когда диапазон значений небольшой. Для массива из двух чисел $10^6$ и $1$ придётся завести миллион счётчиков ради двух элементов. При огромном диапазоне массив $C$ может вообще не поместиться в память.

3. Цифровая сортировка

3.1. Идея

Цифровая (поразрядная) сортировка, она же Radix sort, сортирует числа или строки, «если они не супер большие». Ключ разбивается на разряды: цифры числа или символы строки. У каждого разряда диапазон маленький (10 цифр, 26 латинских букв), поэтому по одному разряду можно сортировать подсчётом.

Обозначения, которые будут дальше:

Разряды можно перебирать с конца (LSD, least significant digit — младший разряд) или с начала (MSD, most significant digit — старший разряд). Для понимания удобнее начинать с конца.

3.2. LSD: от последнего разряда к первому

Сначала массив сортируется по последнему символу, потом по предпоследнему и так до первого. Каждый проход — устойчивая сортировка подсчётом по одному символу.

Зачем устойчивость. Посмотрите на aba и abc на последнем проходе. Обе начинаются с a, и по первому символу они равны. Правильный порядок между ними уже установлен предыдущими проходами: по второму символу они тоже равны, а по третьему a меньше c. Устойчивая сортировка оставит их в этом порядке. Неустойчивая может их переставить: результат прошлых проходов потеряется, и вся сортировка сломается.

Отсюда инвариант LSD: после $j$ проходов массив отсортирован по последним $j$ символам. Очередной проход упорядочивает по новому символу, а при равенстве сохраняет уже готовый порядок по младшим.

3.3. Ключи разной длины

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

• Числа дополняются нулями слева: $7\to007$. Ведущие нули значение не меняют.
• Строки дополняются справа символом, которого нет в алфавите и который меньше всех его символов. Например, $: его код в ASCII 36, а у букв — от 65 (A) и от 97 (a). Тогда ab превратится в ab$ и окажется раньше abc, как и положено в лексикографическом порядке: префикс идёт раньше более длинной строки.

Дополнять строки самой маленькой буквой алфавита, например a, нельзя: ab превратится в aba, и строки ab и aba станут неотличимы. Алгоритм не будет знать, какая из них короче.

3.4. Время LSD

Делается $d$ проходов, каждый — сортировка подсчётом за $\Theta(n+k)$: $T(n)=\Theta\big(d\,(n+k)\big).$

Считать $k$ константой можно, только если алфавит заранее ограничен. В примере выше были только маленькие латинские буквы, $k=26$. Но в сервисе перевода или локализации строки могут содержать символы практически любых алфавитов, а также собственные символы. Тогда $k$ огромно, и выбросить его из оценки нельзя.

Память LSD — $\Theta(n+k)$: один массив счётчиков и один буфер, которые переиспользуются на каждом проходе.

void radix_sort(vector<uint32_t>& a) {
    vector<uint32_t> b(a.size());
    for (int shift = 0; shift < 32; shift += 8) {   // d = 4 прохода, от младшего байта
        array<size_t, 256> c{};                      // k = 256
        for (uint32_t x : a) c[(x >> shift) & 255]++;
        for (int v = 1; v < 256; v++) c[v] += c[v - 1];
        for (size_t i = a.size(); i-- > 0;)         // справа налево — устойчиво
            b[--c[(a[i] >> shift) & 255]] = a[i];
        swap(a, b);                                  // проходов чётное число, ответ в a
    }
}

3.5. MSD: от первого разряда к последнему

Если просто отсортировать сначала по первому символу, потом по второму, потом по третьему, получится ерунда. Каждый следующий проход перемешает то, что упорядочил предыдущий. Поэтому MSD устроен иначе.

1. Сортируем подсчётом по первому символу.
2. Строки с одинаковым первым символом теперь стоят подряд — это блоки («корзины»). Строки из разных корзин больше никогда не перемешиваются: всё, что начинается на a, меньше всего, что начинается на b.
3. Рекурсивно запускаемся от каждой корзины, сортируя её уже по второму символу, и так далее.
4. Рекурсия останавливается, когда в корзине остался один элемент или символы кончились.

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

Глубина рекурсии — до $d$, а не $\log d$. Каждый уровень рекурсии «съедает» ровно один символ, поэтому до $d$-го символа можно дойти только через $d$ уровней.

// a[l..r) сортируются по символам с позиции pos;
// все строки заранее дополнены '$' до одной длины
void msd(vector<string>& a, int l, int r, int pos) {
    if (r - l <= 1 || pos == (int)a[l].size()) return;
    array<int, 257> c{};                                   // k = 256
    for (int i = l; i < r; i++) c[(unsigned char)a[i][pos] + 1]++;
    for (int v = 1; v <= 256; v++) c[v] += c[v - 1];      // c[v] = начало корзины v
    {
        vector<string> b(r - l);
        for (int i = l; i < r; i++) b[c[(unsigned char)a[i][pos]]++] = move(a[i]);
        for (int i = l; i < r; i++) a[i] = move(b[i - l]);
    }                                                      // буфер освобождён до рекурсии
    for (int v = 0, start = 0; v < 256; start = c[v++])   // теперь c[v] = конец корзины v
        msd(a, l + start, l + c[v], pos + 1);
}

3.6. LSD или MSD

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

За MSD. LSD всегда проходит по всем $n$ ключам на каждом из $d$ разрядов. MSD останавливается, как только корзина стала маленькой. Если ключи различаются уже в первых символах, до остальных символов он вообще не доходит. На схеме выше до третьего символа дошли только aba и abc.

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

За LSD (дополнение, на паре этот тезис доказать не успели). LSD проще: нет рекурсии, память $\Theta(n+k)$ при любых данных, каждый проход — один линейный пробег по массиву. MSD платит $\Theta(k)$ за каждую корзину, и на множестве мелких корзин это обходится дорого (см. ниже).

Память. У MSD к сортировке подсчётом добавляется рекурсия. На каждом уровне рекурсии лежит свой массив счётчиков длины $k$. Значение $k$ одно на весь алфавит и в глубине не меняется, а $n$ на память счётчиков не влияет.

4. Приоритетная очередь и двоичная куча

4.1. Задача

Есть объекты, у каждого — приоритет. Объекты добавляются и удаляются, приоритеты могут меняться. Важно в любой момент знать, кто следующий: кто первым зайдёт к врачу, кто первым сядет в самолёт. Человек с высшим приоритетом идёт первым, остальные «когда-то потом».

Если хранить объекты просто в массиве, следующего каждый раз приходится искать заново. Нужна структура, которая сама поддерживает инвариант «наверху — самый приоритетный элемент» и дёшево его восстанавливает после изменений.

Дополнение. Сравнение с наивными способами:

4.2. Куча

Определение 1. Min-куча (min-heap) — дерево, в котором каждый узел не больше своих детей. Max-куча (max-heap) — наоборот, каждый узел не меньше своих детей. По-русски кучу ещё называют пирамидой.

Дальше везде min-куча: наверху минимальный элемент. Его и считаем элементом с наивысшим приоритетом. Max-куча устроена так же с обратным знаком сравнения.

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

Куча не отсортирована: про двух братьев или про узлы в разных ветках ничего не известно. Гарантия одна — путь от корня к любому листу не убывает.

4.3. Полное двоичное дерево

Двоичная (бинарная) куча строится на полном двоичном дереве:

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

Требования «у каждого узла 0 или 2 ребёнка» тут нет: у последнего заполненного узла может быть один левый ребёнок, а узлы последнего уровня — листья.

Высота полного двоичного дерева из $n$ узлов — $\lfloor\log_2n\rfloor$. Уровень $\ell$, если он заполнен целиком, содержит $2^\ell$ узлов. Поэтому дерево высоты $h$ содержит от $2^h$ до $2^{h+1}-1$ узлов, откуда $h=\lfloor\log_2n\rfloor$. Отсюда все логарифмы ниже.

4.4. Хранение в массиве

Раз дерево заполняется строго по уровням и слева направо, указатели не нужны: узлы можно выписать в массив в том же порядке. Корень — на индексе $0$, потом весь уровень $1$, потом весь уровень $2$ и так далее.

Для узла с индексом $i$ (индексы с нуля):

Формула родителя — обратная операция к формулам детей. Округление вниз: левый ребёнок $2i+1$ нечётный, правый $2i+2$ чётный, и для обоих должно получиться одно и то же $i$. Проверка на паре: у узла $9$ родитель $\frac{9-1}2=4$, у узла $10$ — $\left\lfloor\frac{10-1}2\right\rfloor=\lfloor4{,}5\rfloor=4$. Оба — дети узла $4$: $2\cdot4+1=9$, $2\cdot4+2=10$. Детей узла $2$ ищем так же: $2\cdot2+1=5$ и $2\cdot2+2=6$.

В C++ деление неотрицательных целых (i - 1) / 2 само округляет вниз. Но для корня $(0-1)/2$ даёт $0$, а не $-1$, потому что деление округляет к нулю. Поэтому цикл подъёма должен явно останавливаться на $i=0$.

Дополнение: откуда формулы. Уровень $\ell$ начинается с индекса $2^\ell-1$. Если $i$ — $p$-й узел своего уровня ($i=2^\ell-1+p$), то перед его детьми на следующем уровне стоят $2p$ узлов. Значит, левый ребёнок — $2^{\ell+1}-1+2p=2(2^\ell-1+p)+1=2i+1$.

4.5. Вставка: просеивание вверх

Новый элемент кладётся в конец массива, то есть в первую свободную позицию последнего уровня. Если он не меньше родителя, всё в порядке. Если меньше, свойство кучи нарушено, и элемент нужно поднять. Эта операция называется sift up (просеивание вверх):

1. сравнить элемент с родителем;
2. если элемент меньше — поменять их местами и повторить с новой позиции;
3. остановиться, когда элемент не меньше родителя или стал корнем.

Почему обмен ничего не ломает: родитель был не больше своего второго ребёнка, а новый элемент меньше родителя, значит, меньше и этого ребёнка. Если вставить $0$, он поднимется до самого корня.

Время — $O(\log n)$: за каждый обмен элемент поднимается на уровень, а уровней $\lfloor\log_2n\rfloor+1$.

На паре спросили, нельзя ли быстрее, за $\log\log n$. В такой простой структуре нельзя. Бывают другие, более сложные кучи с другими оценками.

4.6. Извлечение минимума: просеивание вниз

Минимум лежит в корне — посмотреть его можно за $O(1)$. Чтобы его удалить:

1. поменять корень с последним элементом массива — в массиве это делается легко;
2. уменьшить размер на один (resize или просто сдвинуть правую границу) — бывший минимум больше не участвует;
3. на месте корня теперь чужой, скорее всего большой элемент. Его опускают операцией sift down (просеивание вниз): сравнить с обоими детьми и поменять с меньшим из них;
4. остановиться, когда детей нет или элемент не больше обоих детей.

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

Время — $O(\log n)$: на каждом шаге элемент спускается на уровень, так что шагов не больше высоты дерева. Удаление — это обмен за $O(1)$ плюс sift down, итого тоже $O(\log n)$.

4.7. Код

Дополнение — та же логика на C++:

struct MinHeap {
    vector<int> a;
 
    void sift_up(int i) {
        while (i > 0 && a[i] < a[(i - 1) / 2]) {
            swap(a[i], a[(i - 1) / 2]);
            i = (i - 1) / 2;
        }
    }
 
    void sift_down(int i) {
        int n = a.size();
        while (true) {
            int l = 2 * i + 1, r = 2 * i + 2, m = i;
            if (l < n && a[l] < a[m]) m = l;   // m — наименьший из трёх
            if (r < n && a[r] < a[m]) m = r;
            if (m == i) return;                // не больше детей или детей нет
            swap(a[i], a[m]);
            i = m;
        }
    }
 
    int top() const { return a[0]; }                       // O(1)
    void push(int x) { a.push_back(x); sift_up(a.size() - 1); }  // O(log n)
    void pop() {                                           // O(log n)
        swap(a[0], a.back());
        a.pop_back();
        if (!a.empty()) sift_down(0);
    }
};

В стандартной библиотеке это std::priority_queue. По умолчанию она max-куча: top() возвращает наибольший элемент. Min-куча объявляется как priority_queue<int, vector<int>, greater<int>>.

4.8. Что дальше

Если разобраться с sift up и sift down, все остальные операции кучи получаются из них автоматически. На паре остался открытый вопрос: за сколько построить кучу из готового массива. Его разберут на лекции.

Частые ошибки

• «Сортировка подсчётом работает за $\Theta(n)$». Нет, за $\Theta(n+k)$. При большом диапазоне $k$ доминирует.
• Префиксные суммы, а потом проход слева направо. Сортировка всё равно получится, но равные элементы выйдут в обратном порядке. Для LSD это ошибка.
• LSD с неустойчивой сортировкой по разряду. Каждый проход ломает результат предыдущих.
• MSD как «LSD наоборот» — просто несколько полных проходов с первого символа. Без разбиения на корзины и рекурсии ответ неверный.
• Дополнять строки самой маленькой буквой, а не символом вне алфавита. ab и aba становятся неотличимы.
• «Полное двоичное дерево — у каждого узла 0 или 2 ребёнка». У кучи «полное» значит «заполнено по уровням слева направо».
• Sift down с любым ребёнком. Менять нужно только с меньшим (в max-куче — с большим).
• Родитель $\frac i2$ вместо $\left\lfloor\frac{i-1}2\right\rfloor$ при индексации с нуля. Формула $\frac i2$ верна, только когда корень на индексе $1$.

Мини-тренажёр

1. Отсортируйте подсчётом массив $2,0,2,1,0$. Выпишите $k$, массив счётчиков и префиксные суммы.
2. Сортировка LSD по десятичным цифрам: каким станет массив $170,45,75,90,802,24,2,66$ после первого прохода?
3. Сколько проходов сделает LSD по байтам для 64-битных чисел и чему равно $k$?
4. Куча хранится в массиве $2,6,3,9,7,8$. Назовите индекс родителя элемента с индексом $5$ и индексы детей элемента с индексом $1$.
5. Вставьте $1$ в кучу из задачи 4. Каким станет массив?
6. Извлеките минимум из кучи $2,6,3,9,7,8$ (исходной). Каким станет массив?
7. Почему у MSD глубина рекурсии $d$, а не $\log d$?

Шпаргалка