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

Content

Сортировка кучей - популярный и эффективный алгоритм сортировки в компьютерном программировании. Чтобы научиться писать алгоритм сортировки кучей, требуется знание двух типов структур данных - массивов и деревьев.

Например, начальный набор чисел, которые мы хотим отсортировать, хранится в массиве [10, 3, 76, 34, 23, 32], и после сортировки мы получаем отсортированный массив [3,10,23,32,34,76].

Сортировка кучей работает путем визуализации элементов массива как особого вида полного двоичного дерева, называемого кучей.

Что такое бинарное дерево? Какие виды бинарных деревьев существуют?

Бинарное дерево - это структура данных дерева, в которой каждый родительский узел может иметь не более двух дочерних элементов.

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

Идеальное бинарное дерево похоже на полное бинарное дерево, но с двумя основными отличиями:

  1. Каждый уровень должен быть полностью заполнен.
  2. Все элементы листа должны наклоняться влево.

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

Как создать полное бинарное дерево из несортированного списка (массива)?
  • Выберите первый элемент списка, чтобы он быть корневым узлом. (Первый уровень - 1 элемент).
  • Поместите второй элемент в качестве левого дочернего элемента корневого узла, а третий элемент - в качестве правого дочернего элемента. (Второй уровень - 2 элемента).
  • Поместите следующие два элемента в качестве дочерних элементов левого узла второго уровня. Снова, поместите следующие два элемента как дочерние элементы правого узла второго уровня (3-й уровень - 4 элемента).
  • Продолжайте повторять, пока не дойдете до последнего элемента.

Связь между индексами массива и элементами дерева

Полное бинарное дерево обладает интересным свойством, которое мы можем использовать для поиска дочерних элементов и родителей любого узла.
Если индекс любого элемента в массиве равен i, элемент в индексе 2i + 1 станет левым потомком, а элемент в индексе 2i + 2 станет правым потомком. Кроме того, родительский элемент любого элемента с индексом i задается нижней границей (i-1) / 2.

Проверим это:

Left child of 1 (index 0)
= element in (2*0+1) index 
= element in 1 index 
= 12


Right child of 1
= element in (2*0+2) index
= element in 2 index 
= 9

Similarly,
Left child of 12 (index 1)
= element in (2*1+1) index
= element in 3 index
= 5

Right child of 12
= element in (2*1+2) index
= element in 4 index
= 6

Также подтвердим, что правила верны для нахождения родителя любого узла:

Parent of 9 (position 2) 
= (2-1)/2 
= ½ 
= 0.5
~ 0 index 
= 1

Parent of 12 (position 1) 
= (1-1)/2 
= 0 index 
= 1

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

Что такое структура данных кучи?

Куча - это специальная древовидная структура данных. Говорят, что двоичное дерево следует структуре данных кучи, если

  • это полное бинарное дерево;
  • все узлы в дереве следуют тому свойству, что они больше своих потомков, то есть самый большой элемент находится в корне, и оба его потомка меньше, чем корень, и так далее. Такая куча называется убывающая куча (Max-Heap). Если вместо этого все узлы меньше своих потомков, это называется возрастающая куча (Min-Heap).



Слева на рисунке убывающая куча, справа - возрастающая куча.

Как выстроить дерево

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

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

heapify(array)
    Root = array[0]
    Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2])
    if(Root != Largest)
          Swap(Root, Largest)

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

Теперь давайте подумаем о другом сценарии, в котором существует более одного уровня.

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

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

Мы можем объединить оба эти условия в одну функцию heapify следующим образом:

void heapify(int arr[], int n, int i)
{
   int largest = i;
   int l = 2*i + 1;
   int r = 2*i + 2;

   if (l < n && arr[l] > arr[largest])
     largest = l;

   if (right < n && arr[r] > arr[largest])
     largest = r;

   if (largest != i)
   {
     swap(arr[i], arr[largest]);

     // Recursively heapify the affected sub-tree
     heapify(arr, n, largest);
   }
}

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

Сборка убывающей кучи

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

В случае полного дерева первый индекс неконечного узла определяется как n / 2 - 1. Все остальные узлы после этого являются листовыми узлами и, следовательно, не нуждаются в куче.

Мы можем выстроить убывающую кучу так:

// Build heap (rearrange array)
   for (int i = n / 2 - 1; i >= 0; i--)
     heapify(arr, n, i);

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

Процедуры для Heapsort
  1. Поскольку дерево удовлетворяет свойству убывающей, самый большой элемент сохраняется в корневом узле.
  2. Удалите корневой элемент и поместите в конец массива (n-я позиция). Поместите последний элемент дерева (кучу) в свободное место.
  3. Уменьшите размер кучи на 1 и снова укрупните корневой элемент, чтобы у вас был самый большой элемент в корне.
  4. Процесс повторяется до тех пор, пока все элементы списка не будут отсортированы.

Код выглядит так:

for (int i=n-1; i>=0; i--)
   {
     // Переместить текущий корень в конец
     swap(arr[0], arr[i]);

     // вызовите максимальный heapify на уменьшенной куче
     heapify(arr, i, 0);
   }
Представление

Сортировка кучи имеет O (nlogn) временные сложности для всех случаев (лучший случай, средний случай и худший случай). В чем же причина? Высота полного бинарного дерева, содержащего n элементов, равна log (n).

Как мы видели ранее, чтобы полностью накапливать элемент, чьи поддеревья уже являются убывабщими кучами, нам нужно продолжать сравнивать элемент с его левым и правым потомками и толкать его вниз, пока он не достигнет точки, где оба его потомка меньше его.

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

На этапе build_max_heap мы делаем это для n / 2 элементов, поэтому сложность шага build_heap в наихудшем случае равна n / 2 * log (n) ~ nlogn.

На этапе сортировки мы обмениваем корневой элемент с последним элементом и подкачиваем корневой элемент. Для каждого элемента это снова занимает большое время, поскольку нам, возможно, придется перенести этот элемент от корня до листа. Поскольку мы повторяем операцию n раз, шаг heap_sort также nlogn.

Кроме того, поскольку шаги build_max_heap и heap_sort выполняются один за другим, алгоритмическая сложность не умножается и остается в порядке nlogn.

Также выполняется сортировка в O (1) пространстве сложности. По сравнению с быстрой сортировкой, в худшем случае (O (nlogn)). Быстрая сортировка имеет сложность O (n ^ 2) для худшего случая. Но в других случаях быстрая сортировка выполняется достаточно быстро. Introsort - это альтернатива heapsort, которая сочетает в себе quicksort и heapsort для сохранения преимуществ, таких как скорость heapsort в худшем случае и средняя скорость quicksort.

Применение сортировки кучей

Системы, связанные с безопасностью, и встроенные системы, такие как ядро ​​Linux, используют сортировку кучей из-за верхней границы O (n log n) времени работы Heapsort и постоянной верхней границы O (1) его вспомогательного хранилища.

Хотя сортировка кучей имеет O (n log n) временную сложность даже для наихудшего случая, у нее нет больше приложений (по сравнению с другими алгоритмами сортировки, такими как быстрая сортировка, сортировка слиянием). Тем не менее, его базовая структура данных, куча, может быть эффективно использована, если мы хотим извлечь наименьший (или наибольший) из списка элементов без дополнительных затрат на сохранение оставшихся элементов в отсортированном порядке. Например, приоритетные очереди.

Реализация сортировки кучи на разных языках программирования

Реализация C ++

// C++ program for implementation of Heap Sort
#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i)
{
   // Find largest among root, left child and right child
   int largest = i;
   int l = 2*i + 1;
   int r = 2*i + 2;

   if (l < n && arr[l] > arr[largest])
     largest = l;

   if (right < n && arr[r] > arr[largest])
     largest = r;

   // Swap and continue heapifying if root is not largest
   if (largest != i)
   {
     swap(arr[i], arr[largest]);
     heapify(arr, n, largest);
   }
}

// main function to do heap sort
void heapSort(int arr[], int n)
{
   // Build max heap
   for (int i = n / 2 - 1; i >= 0; i--)
     heapify(arr, n, i);

   // Heap sort
   for (int i=n-1; i>=0; i--)
   {
     swap(arr[0], arr[i]);

     // Heapify root element to get highest element at root again
     heapify(arr, i, 0);
   }
}

void printArray(int arr[], int n)
{
   for (int i=0; i<n; ++i)
     cout << arr[i] << " ";
   cout << "\n";
}

int main()
{
   int arr[] = {1,12,9,5,6,10};
   int n = sizeof(arr)/sizeof(arr[0]);
   heapSort(arr, n);

   cout << "Sorted array is \n";
   printArray(arr, n);
}

Реализация на Java

// Java program for implementation of Heap Sort
public class HeapSort
{   

    public void sort(int arr[])
    {
        int n = arr.length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
          heapify(arr, n, i);
        }


        // Heap sort
        for (int i=n-1; i>=0; i--)
        {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Heapify root element
            heapify(arr, i, 0);
        }
    }

    void heapify(int arr[], int n, int i)
    {
        // Find largest among root, left child and right child
        int largest = i; 
        int l = 2*i + 1; 
        int r = 2*i + 2;  

        if (l < n && arr[l] > arr[largest])
            largest = l;

        if (r < n && arr[r] > arr[largest])
            largest = r;

        // Swap and continue heapifying if root is not largest
        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i < n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }

    public static void main(String args[])
    {
        int arr[] = {1,12,9,5,6,10};

        HeapSort hs = new HeapSort();
        hs.sort(arr);

        System.out.println("Sorted array is");
        printArray(arr);
    }
}

Реализация на Python (Python 3)

def heapify(arr, n, i):
    # Find largest among root and children
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2 

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    # If root is not largest, swap with largest and continue heapifying
    if largest != i:
        arr[i],arr[largest] = arr[largest],arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)

    # Build max heap
    for i in range(n, 0, -1):
        heapify(arr, n, i)


    for i in range(n-1, 0, -1):
        # swap
        arr[i], arr[0] = arr[0], arr[i]  

        #heapify root element
        heapify(arr, i, 0)


arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
    print ("%d" %arr[i])
We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.

Comments

Only authorized users can post comments.
Please, Log in or Sign up
How to become an author?

Contribute to the evolution of the EVILEG community.

Learn how to become a site author.

Learn it
Donate

Good day, Dear Users!!!

I am Evgenii Legotckoi, developer of EVILEG. And it is my hobby project, which helps to learn programming another programmers and developers

If the site helped you, and you want also support the development of the site, than you can donate by following ways

PayPalYandex.Money
Timeweb

Let me recommend you the excellent hosting on which EVILEG is located.

For many years, Timeweb has been proving his stability.

For projects on Django I recommend VDS hosting

View Hosting Timeweb
MN
May 25, 2020, 11:33 a.m.
Mitja Nagibin

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:50points,
  • Rating points-4
f
May 25, 2020, 5:05 a.m.
falcon

C++ - Test 001. The first program and data types

  • Result:66points,
  • Rating points-1
jm
May 25, 2020, 3:30 a.m.
just maks

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:80points,
  • Rating points4
Last comments
May 26, 2020, 6:51 a.m.
Evgenij Legotskoj

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

У вас база данных не открылась Исправьте путь к базе данных на свой корректный в следующих методах void DataBase::connectToDataBase() bool DataBase::openDataBase()
T1
T1
May 26, 2020, 6:22 a.m.
Tima 1

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

полностью повторил структору проекта. В форму дабавил tableView. Но при запуске получаю форму только с пустым tableView. Можете подсказать в чем пробелма?
May 26, 2020, 6:02 a.m.
Evgenij Legotskoj

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

Потому что это файл который нужно создать, а не библиотека. В статье есть содержание этого файла. Добавляйте в проект. Копируйте содержимое из статьи.
T1
May 26, 2020, 6 a.m.
Tima 1

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

не удается подключиить библеотеку include "database.h" выдает ошибку. Можете помочь?
Now discuss on the forum
May 26, 2020, 8:48 a.m.
Vladislav Melenchuk

Templatetags из GenericForeign

all() got an unexpected keyword argument 'content_type'
May 26, 2020, 5:16 a.m.
BlinCT

Отсутствие драйвера SQLite в пакете Qt 4 на Linux

Вот честно непонимаю почему до сих пор используют qt4, там же столько всего отсутствует, много фишек и возможностей нету там. То есть используя такое старье приходится много писать самому а не и…
DK
May 26, 2020, 2:24 a.m.
Dzhon Kofi

Disable autoscroll

такие естественные решения все перепробовал. Получилось вчера так: const int maximumScroll = ui->_samples->verticalScrollBar()->maximum();const int sliderPos = ui->_samp…
May 26, 2020, 12:43 a.m.
Ruslan Polupan

Посоветуйте новичку (базы данных и Qt, что учить)

Без БД сейчас практически никуда. Поэтому SQL надо знать. SQLite самы простой вариант, но имхо лучще начать с бд клиент-сервер. Настроить сервер. Подключаться клиентом. Просто это помогает понят…
EJ
May 25, 2020, 2:42 p.m.
Esteban José María

Компиляция пустого проекта Qt Android

qt 5.12.8 BUILD SUCCESSFUL in 42s 28 actionable tasks: 28 executed Android package built successfully in 68.251 ms. Ну, буду разбираться по-тихоньку. :)
About
Services
© EVILEG 2015-2020
Recommend hosting TIMEWEB