Рубрики

Программа C ++ для сортировки кучи

Сортировка кучи — это метод сортировки на основе сравнения, основанный на структуре данных двоичной кучи. Это похоже на сортировку выбора, где мы сначала находим максимальный элемент и помещаем максимальный элемент в конец. Мы повторяем тот же процесс для оставшегося элемента.

// C ++ программа для реализации Heap Sort
#include <iostream>

using namespace std;

  
// Для подкачки поддерева с корневым узлом i, который
// индекс в arr []. п размер кучи

void heapify(int arr[], int n, int i)

{

    int largest = i; // Инициализируем наибольшее как root

    int l = 2 * i + 1; // left = 2 * i + 1

    int r = 2 * i + 2; // right = 2 * i + 2

  

    // Если левый дочерний объект больше корневого

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

        largest = l;

  

    // Если правый ребенок больше, чем самый большой

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

        largest = r;

  

    // Если самый большой не root

    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]);

  

        // вызвать max heapify для уменьшенной кучи

        heapify(arr, i, 0);

    }

}

  
/ * Утилита для печати массива размером n * /

void printArray(int arr[], int n)

{

    for (int i = 0; i < n; ++i)

        cout << arr[i] << " ";

    cout << "\n";

}

  
// Драйвер программы

int main()

{

    int arr[] = { 12, 11, 13, 5, 6, 7 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    heapSort(arr, n);

  

    cout << "Sorted array is \n";

    printArray(arr, n);

}

Выход:

Sorted array is 
5 6 7 11 12 13

Пожалуйста, обратитесь к полной статье по сортировке кучи для более подробной информации!

Рекомендуемые посты:

Программа C ++ для сортировки кучи

0.00 (0%) 0 votes