Алгоритм пирамидальной сортировки (с кодом в Python и C++)

Что такое алгоритм пирамидальной сортировки?

Heap Sort — один из популярных и быстрых алгоритмов сортировки. Он построен на полной структуре данных двоичного дерева. Мы найдем максимальный элемент и поместим его на вершину максимальной кучи. Мы поместим его в родительский узел бинарного дерева.

Допустим, дан массив, данные = [10,5, 7, 9, 4, 11, 45, 17, 60].

В массиве, если i-й (i=0,1,2,3…) индекс является родительским узлом, то (2i+1) и (2i+2) будут левым и правым дочерними узлами. Создание полного двоичного дерева с помощью этого массива будет выглядеть так:

Алгоритм сортировки кучи

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

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

Вот некоторые примеры использования алгоритма сортировки кучи:

  • Для построения «приоритетных очередей» требуется пирамидальная сортировка. Потому что пирамидальная сортировка сохраняет сортировку элемента после каждой вставки.
  • Структура данных кучи эффективна при поиске kth наибольший элемент в заданном массиве.
  • Ядро Linux использует сортировку кучи по умолчанию. алгоритм сортировки так как имеет пространственную сложность O(1).

Создайте пирамидальную сортировку с примером

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

Создайте пирамидальную сортировку с примером

Листовыми узлами являются 17, 60, 4, 11 и 45. У них нет дочерних узлов. Вот почему они являются листовыми узлами. Итак, мы запустим метод heapify из родительского узла. Вот шаги:

Шаг 1) Выберите самое левое поддерево. Если дочерние узлы больше, поменяйте местами родительский узел с дочерним узлом.

Здесь родительским узлом является 9. А дочерними узлами являются 17 и 60. Поскольку 60 является самым большим, 60 и 9 будут заменены местами для сохранения максимальная куча.

Создайте пирамидальную сортировку с примером

Шаг 2) Теперь самое левое поддерево разбито на кучу. Следующий родительский узел — 7. У этого родителя есть два дочерних узла, самый большой — 45. Таким образом, 45 и 7 будут заменены местами.

Создайте пирамидальную сортировку с примером

Создайте пирамидальную сортировку с примером

Шаг 3) Узлы 60 и 4 имеют родительский узел 5. Поскольку «5» меньше дочернего узла 60, он будет заменен.

Создайте пирамидальную сортировку с примером

Создайте пирамидальную сортировку с примером

Шаг 4) Теперь у узла 5 есть дочерний узел 17,9. Это не поддерживает свойство максимальной кучи. Итак, 5 будет заменено на 17.

Создайте пирамидальную сортировку с примером

Шаг 5) Узел 10 будет заменен на 60, затем заменен на 17. Процесс будет выглядеть следующим образом.

Создайте пирамидальную сортировку с примером

Создайте пирамидальную сортировку с примером

Шаг 6) До шага 5 мы создали максимальную кучу. Каждый родительский узел больше своих дочерних узлов. Корневой узел имеет максимальное значение (60).

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

Этот процесс называется «извлечь максимум». Поскольку 60 — это максимальный узел, мы зафиксируем его позицию на нулевом индексе и создадим кучу без узла 0.

Создайте пирамидальную сортировку с примером

Создайте пирамидальную сортировку с примером

Шаг 7) Поскольку 60 удалено, следующим максимальным значением будет 45. Мы снова выполним процесс «Извлечение максимума» из узла 45.

На этот раз мы получим 45 и заменим корневой узел его преемником 17.

Нам нужно выступить»Извлечь Макса», пока все элементы не будут отсортированы.

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

Создайте пирамидальную сортировку с примером

Что такое двоичная куча?

Двоичная куча — это своего рода полная бинарное дерево структура данных. В такой древовидной структуре родительский узел либо больше, либо меньше дочерних узлов. Если родительский узел меньше, то куча называется «Минимальной кучей», а если родительский узел больше, куча называется «Максимальной кучей».

Вот примеры минимальной кучи и максимальной кучи.

Минимальная куча и максимальная куча
Минимальная куча и максимальная куча

Если на приведенном выше рисунке вы заметили «Минимальную кучу», родительский узел всегда меньше своих дочерних узлов. В голове дерева мы можем найти наименьшее значение 10.

Аналогично, для «Максимальной кучи» родительский узел всегда больше дочерних узлов. Максимальный элемент присутствует в головном узле для «Максимальной кучи».

Что такое «Heapify»?

«Heapify» — это принцип кучи, который обеспечивает положение узла. В Heapify максимальная куча всегда поддерживает связь с родительским и дочерним узлами, и родительский узел будет больше, чем дочерние узлы.

Например, если добавляется новый узел, нам нужно изменить форму кучи. Однако нам может потребоваться изменить или поменять местами узлы или переупорядочить массив. Этот процесс изменения формы кучи называется «кучей».

Вот пример того, как работает heapify:

Добавление нового узла и Heapify
Добавление нового узла и heapify

Вот шаги для heapify:

Шаг 1) Добавлен узел 65 как правый дочерний элемент узла 60.

Шаг 2) Проверьте, больше ли вновь добавленный узел родительского.

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

Как построить кучу

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

Допустим, массив содержит всего n элементов. Если «i»-й индекс является родительским узлом, то левый узел будет находиться по индексу (2и+1), и правый узел будет по индексу (2и+2). Мы предполагаем, что индекс массива начинается с 0.

Используя это, давайте сохраним максимальную кучу в виде массива:

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

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

Вот шаги для создания максимальной кучи:

Шаг 1) Начните с листового узла.

Шаг 2) Найдите максимум между родителем и детьми.

Шаг 3) Поменяйте местами узлы, если дочерний узел имеет большее значение, чем родительский.

Шаг 4) Поднимитесь на один уровень выше.

Шаг 5) Выполните шаги 2,3,4, пока не достигнем индекса 0 или не отсортируем все дерево.

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

def heapify():
  input→ array, size, i
  largest = i
  left = 2*i + 1
  right = 2*i + 2
if left<n and array[largest ] < array[left]:
  largest = left
if right<n and array[largest ] < array[right]:
  largest = right
If largest not equals i:
  swap(array[i],array[largest])
  heapify(array,n,largest)

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

Вот псевдокод алгоритма сортировки кучей:

Heapify(numbers as an array, n as integer, i as integer):
  largest = i
  left = 2i+1
  right= 2i+2
if(left<=n) and (numbers[i]<numbers[left])
  largest=left
if(right<=n) and (numbers[i]<numbers[right])
  largest=right
if(largest  != i)
  swap(numbers[i], numbers[largest])
  Heapify(numbers,n,largest)
HeapSort(numbers as an array):
  n= numbers.size()
for i in range n/2 to 1
  Heapify(numbers,n,i)
for i in range n to 2
  Swap numbers[i] with numbers[1]
  Heapify(numbers,i,0)

Пример кода сортировки кучи в C++

#include <iostream>
using namespace std;
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
void heapify(int numbers[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && numbers[left] < numbers[largest])
    {
        largest = left;
    }
    if (right < n && numbers[right] < numbers[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
	//uncomment the following line to see details in output
        //cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
        swap(numbers[i], numbers[largest]);
        heapify(numbers, n, largest);
    }
}
void heapSort(int numbers[], int n)
{
    for (int i = n/2 - 1; i >= 0; i--)
    {
        heapify(numbers, n, i);
//uncomment the following line to see details in output
 //cout<<"Heapify:\t";
  //display(numbers,n);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        swap(numbers[0], numbers[i]);
        heapify(numbers, i, 0);
    }
}
int main()
{
    int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    cout<<"Initial Array:\t";
    display(numbers,size);
    heapSort(numbers, size);
    cout<<"Sorted Array (descending order):\t";
    display(numbers, size);
}

Вывод:

Initial Array:  10      5       7       9       4       11      45      17      60
Sorted Array (descending order):  60      45      17      11      10      9       7       5       4

Пример кода сортировки кучи в Python

def display(arr):
    for i in range(len(arr)):
    print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
    largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
    largest = left
if right < n and numbers[right] < numbers[largest]:
    largest = right
if largest != i:
    numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
    for i in range(n //2,-1,-1):
        heapify(items, n, i) for i in range(n - 1, -1, -1):
        items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)

Вывод:

Initial List:   10      5       7       9       4       11      45      17      60
After HeapSort: 60      45      17      11      10      9       7       5       4

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

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

  1. лучший случай
  2. Средний случай
  3. Худший случай

Куча реализована в виде полного двоичного дерева. Итак, на нижнем уровне бинарного дерева будет максимальное количество узлов. Если нижний уровень имеет n узлов, то верхний уровень будет иметь n/2 узлов.

Анализ временной и пространственной сложности

В этом примере уровень 3 содержит четыре элемента, уровень 2 — два элемента, а уровень 1 — один элемент. Если всего элементов n, высота или общий уровень будет равна Журнал2(П). Таким образом, вставка одного элемента может занять максимум итераций Log(n).

Когда мы хотим взять максимальное значение из кучи, мы просто берем корневой узел. Затем снова запустите heapify. Каждая куча занимает Журнал2(П) время. Извлечение максимума занимает время O(1).

лучший Case Time Complexity для алгоритма Heap Sort

Когда все элементы массива уже отсортированы, для построения кучи потребуется время O(n). Потому что, если список отсортирован, вставка элемента займет постоянное время, равное O (1).

Таким образом, для создания максимальной или минимальной кучи в лучшем случае потребуется время O(n).

Средняя сложность случая для алгоритма пирамидальной сортировки

Вставка элемента или извлечение максимального значения требует времени O(log(n)) . Таким образом, средняя временная сложность алгоритма сортировки кучи равна О(п лог(п)).

Наихудшая временная сложность алгоритма пирамидальной сортировки

Как и в среднем случае, в худшем случае мы можем выполнить heapify n раз. Каждая heapify будет стоить O(log(n)) времени. Таким образом, наихудшая временная сложность будет равна О(п лог(п)).

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

Сортировка кучей — это алгоритм, разработанный на месте. Это означает, что для выполнения задачи не требуется никакой дополнительной или временной памяти. Если мы увидим реализацию, то заметим, что мы использовали swap() для выполнения обмена узлами. Никакого другого списка или массива не требовалось. Итак, пространственная сложность равна O(1).