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

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

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

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

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

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

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

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

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

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

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

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

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

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

Шаг 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. Процесс будет выглядеть следующим образом:wing.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Что такое «Онapify»?

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

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

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

Добавляем новый узел и онapify
Добавляем новый узел и онapify

Вот шаги для негоapify:

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

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

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

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

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

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

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

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

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

Вот шаги, чтобы онapify максимальная куча:

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

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

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

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

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

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

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

Время и пространствоplexанализ эффективности пирамидальной сортировки

Время пришлоplexity и Space complexность, которую мы можем проанализировать для сортировки кучи. На время комplexу нас есть фоллоwing случаи:

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

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

Время и пространствоplexАнализ города

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

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

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

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

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

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

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

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

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

Космическая связьplexность для алгоритма пирамидальной сортировки

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