Введение в сортировку кучи в C ++
Heapsort является одним из методов сортировки на основе сравнения и является частью сортировки выбора. Где сортировка определена как расположение наборов данных в некотором определенном порядке, используя уникальное значение, известное как ключевой элемент в данном списке. Термин сортировка был введен, когда люди узнали о важности поиска любого элемента в любом данном наборе информации, в противном случае было бы очень трудно найти любую запись, если она неупорядочена и не отсортирована.
Существует много разных методов, связанных с сортировкой, каждая из которых имеет свою эффективность в течение времени, необходимого для сортировки данных и потребности в памяти. Это пузырьковая сортировка, вставка, выборка, быстрая сортировка, объединение и куча.
Что такое кучная сортировка?
Heapsort - это подход сортировки, основанный на структуре данных двоичной кучи, подобной сортировке выбора, когда мы сначала получаем максимальный фрагмент набора данных, помещаем его в конец и продолжаем для остальных элементов.
Heapsort, как следует из названия. Сначала он строит кучу элементов данных из данного несортированного массива, а затем проверяет наибольший элемент и помещает его в конец частично отсортированного массива. Он снова восстанавливает кучу, ищет следующий по величине фрагмент записи и помещает его в следующий пустой слот с конца полусортированного набора записей. Этот процесс повторяется до тех пор, пока в куче не останется ни одного элемента. Этот метод требует двух массивов: один для хранения кучи, а другой для отсортированного массива.
Алгоритм сортировки кучи в C ++
- Сначала выберите root в качестве элемента с повышенными правами из заданного информационного набора элементов, чтобы создать максимальную кучу.
- Восстановите кучу, поместив или поменяв корень с последним элементом.
- Размер кучи теперь будет уменьшаться на 1.
- Затем мы снова создаем кучу с оставшимися элементами и продолжаем, пока размер кучи не уменьшится до 1.
Пример сортировки кучи в C ++
Этот метод использует двоичную кучу, которая построена с использованием полного двоичного дерева, где корневой узел больше, чем его два дочерних узла.
Рассмотрим данный массив наборов данных.
Пойдем по алгоритму. Он говорит, чтобы выбрать самый высокий элемент в качестве корня и построить максимальную кучу.
1. Первая итерация
Теперь массив будет иметь вид:
Теперь отсортированный массив будет иметь вид:
Размер кучи будет уменьшен на 1, теперь 6-1 = 5.
2. Вторая итерация
Так что теперь куча выглядит так:
Массив имеет вид:
Сортированный массив будет:
Размер кучи будет уменьшен на 1, теперь 5-1 = 4.
3. Третья итерация
Новая куча выглядит так:
Массив имеет вид:
Сортированный массив будет:
Размер кучи будет уменьшен на 1, теперь 4-1 = 3.
4. Четвертая итерация
Новая куча выглядит так:
Массив имеет вид:
Сортированный массив будет:
Размер кучи будет уменьшен на 1, теперь 3-1 = 2.
5. Пятая итерация
Новая куча выглядит так:
Массив имеет вид:
Сортированный массив будет:
Размер кучи будет уменьшен на 1, теперь 2-1 = 1.
6. Последняя итерация
Новая куча выглядит так:
Массив имеет:
4
Исходя из алгоритма, мы выполнили все шаги, пока размер кучи не стал равен 1. Итак, теперь у нас есть отсортированный массив:
Поэтому отсортированный массив максимальной кучи находится в порядке возрастания. Если нам нужно отсортировать массив в порядке убывания, выполните описанные выше шаги с минимальной кучей.
Программа C ++ для сортировки кучи приведена ниже:
#include
using namespace std;
void heapify(int arr(), int n, int i)
(
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l arr(largest))
largest = l;
if (r arr(largest))
largest = r;
if (largest != i) (
swap(arr(i), arr(largest));
heapify(arr, n, largest);
)
)
void heapSort(int arr(), int n)
(
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--)
(
swap(arr(0), arr(i));
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() = ( 5, 18, 4, 13, 10, 7);
int n = sizeof(arr) / sizeof(arr(0));
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
)
Выход:
Вывод
Heapsort - это метод сравнения, основанный на улучшении сортировки выбора. Сортировка кучи использует выбор самого высокого или самого низкого элемента в данном массиве для сортировки в порядке возрастания или убывания соответственно с максимальной или минимальной кучей. Выполняйте этот процесс, пока мы не получим его в качестве размера кучи. Этот метод сортировки также используется, чтобы найти самый большой и самый низкий элемент в массиве. Метод сортировки кучи более эффективен и быстрее, чем метод сортировки выбора.
Рекомендуемые статьи
Это руководство по сортировке кучи в C ++. Здесь мы обсудим, что такое сортировка кучи в c ++, работает с ее алгоритмом и примером. Вы также можете посмотреть следующие статьи, чтобы узнать больше
- Сортировка кучи в C
- Сортировка кучи в Java
- Перегрузка в C ++
- Указатели в C ++
- Перегрузка в Java