Geek Notes

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

Алгоритм пирамидальной сортировки (сортировка кучей)

Далее представлен краткий конспект разбора пирамидальной сортировки по книге «Алгоритмы. Построение и анализ» (Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн). Примеры кода написаны на языке Java.

Время работы - O(n*logn).
Свойства:

  • Не требует дополнительной памяти, работает с тем же массивом данных.
  • Используется структура данных - Двоичное дерево (куча) .

Принцип работы:

  1. Строим пирамиду
  2. Сохраняем размер массива в отдельную переменную
  3. Так как максимальный элемент находится в корне т.е. a[0], то меняем местами с последним элементом массива, и уменьшаем размер переменной в которой у нас записан размер массива
  4. Вызываем метод поддержки свойств пирамиды heapify(array, 0)

Бинарное дерево с максимальным элементом в корне

Представление бинарного дерева в виде массива

Родитель и потомки любого узла вычисляются по следующем методам:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

    /**
     * 
     * @param int i
     * @return int
     * 
     * применяем побитовый сдвиг влево для быстрого увеличения индекса в 2 раза
     */
    private int left(int i) {
        return i << 1;
    }

    /**
     * 
     * @param int i
     * @return int
     */
    private int right(int i) {
        return (i << 1) + 1;
    }

    /**
     * 
     * @param int i
     * @return int
     * 
     * прменяем побитовый сдвиг вправо для быстрого уменьшения индекса в 2 раза
     */
    public int parent(int i) {
        return i >> 1;
    }

Метод поддержки свойств пирамиды:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

    /**
     * 
     * @param int[] arr
     * @param int length
     * @param int i 
     */
    public void maxHeapify(int[] arr, int length, int i) {
        int left = left(i);
        int right = right(i);
        int largest = i;

        if (left < length && arr[left] > arr[i]) {
            largest = left;
        }
        if (right < length && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest != i) {
            swap(arr, i, largest);
            maxHeapify(arr, length, largest);
        }
    }

Пример работы

Метод создания пирамиды

1
2
3
4
5
6
7
8
9
10

    /**
     * 
     * @param int[] arr 
     */
    private void buildMaxHeap(int[] arr) {

        for (int i = arr.length / 2; i >=0; --i) {
            maxHeapify(arr, arr.length, i);
        }
    }

Пример работы построения кучи из массива A

Метод сортировки:

1
2
3
4
5
6
7
8
9
10
11
12
13

    /**
     * 
     * @param int[] arr 
     */
    public void heapSort(int[] arr) {
        buildMaxHeap(arr);
        int length = arr.length - 1;
        while (length > 0) {
            swap(arr, 0, length);
            maxHeapify(arr, length, 0);
            length--;
        }
    }

Пример работы алгоритма пирамидальной сортировки