Рубрики

Java-программа для сортировки кучи

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

Джава

// Java-программа для реализации Heap Sort

public class HeapSort

{

    public void sort(int arr[])

    {

        int n = arr.length;

  

        // Строим кучу (переставляем массив)

        for (int i = n / 2 - 1; i >= 0; i--)

            heapify(arr, n, i);

  

        // один за другим извлекаем элемент из кучи

        for (int i=n-1; i>=0; i--)

        {

            // Переместить текущий корень в конец

            int temp = arr[0];

            arr[0] = arr[i];

            arr[i] = temp;

  

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

            heapify(arr, i, 0);

        }

    }

  

    // Для подкачки поддерева с корневым узлом 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)

        {

            int swap = arr[i];

            arr[i] = arr[largest];

            arr[largest] = swap;

  

            // Рекурсивно накапливаем поврежденное поддерево

            heapify(arr, n, largest);

        }

    }

  

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

    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[] = {12, 11, 13, 5, 6, 7};

        int n = arr.length;

  

        HeapSort ob = new HeapSort();

        ob.sort(arr);

  

        System.out.println("Sorted array is");

        printArray(arr);

    }

}

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

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

Java-программа для сортировки кучи

0.00 (0%) 0 votes