Рубрики

Пирамидальная сортировка

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

Что такое бинарная куча ?
Давайте сначала определим полное двоичное дерево. Полное двоичное дерево — это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, полностью заполнен, а все узлы расположены как можно левее (Source Wikipedia )

Двоичная куча — это полное двоичное дерево, в котором элементы хранятся в особом порядке, так что значение в родительском узле больше (или меньше) значений в его двух дочерних узлах. Первый называется max heap, а второй называется min heap. Куча может быть представлена двоичным деревом или массивом.

Почему представление на основе массива для двоичной кучи?
Поскольку двоичная куча — это полное двоичное дерево, ее можно легко представить в виде массива, а представление на основе массива является эффективным с точки зрения пространства. Если родительский узел хранится в индексе I, левый дочерний элемент может быть вычислен как 2 * I + 1, а правый дочерний элемент — как 2 * I + 2 (при условии, что индексирование начинается с 0).

Алгоритм сортировки кучи для сортировки по возрастанию:
1. Постройте максимальную кучу из входных данных.
2. В этот момент самый большой элемент хранится в корне кучи. Замените его на последний элемент кучи, а затем уменьшите размер кучи на 1. Наконец, наведите корень дерева.
3. Повторите вышеуказанные шаги, пока размер кучи больше 1.

Как построить кучу?
Процедура heapify может быть применена к узлу, только если его дочерние узлы heapified. Таким образом, heapification должен быть выполнен в порядке снизу вверх.

Давайте разберемся с помощью примера:

Input data: 4, 10, 3, 5, 1
         4(0)
        /   \
     10(1)   3(2)
    /   \
 5(3)    1(4)

The numbers in bracket represent the indices in the array 
representation of data.

Applying heapify procedure to index 1:
         4(0)
        /   \
    10(1)    3(2)
    /   \
5(3)    1(4)

Applying heapify procedure to index 0:
        10(0)
        /  \
     5(1)  3(2)
    /   \
 4(3)    1(4)
The heapify procedure calls itself recursively to build heap
 in top down manner.

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

}

Джава

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

    }

}

питон

# Python программа для реализации кучи Sort

  
# Куча поддерева с корнем в индексе i.
# n - размер кучи

def heapify(arr, n, i):

    largest = i # Инициализировать крупнейших как корень

    l = 2 * i + 1     # left = 2 * i + 1

    r = 2 * i + 2     # right = 2 * i + 2

  

    # Посмотрим, существует ли левый потомок root

    # больше корня

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

        largest = l

  

    # Посмотрим, существует ли правый потомок root

    # больше корня

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

        largest = r

  

    # Сменить root, если нужно

    if largest != i:

        arr[i],arr[largest] = arr[largest],arr[i] # обмен

  

        # Помочь корень.

        heapify(arr, n, largest)

  
# Основная функция для сортировки массива заданного размера

def heapSort(arr):

    n = len(arr)

  

    # Построить maxheap.

    for i in range(n, -1, -1):

        heapify(arr, n, i)

  

    # Один за другим элементы извлечения

    for i in range(n-1, 0, -1):

        arr[i], arr[0] = arr[0], arr[i] # обмен

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

# Этот код предоставлен Мохитом Кумрой

C #

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

using System;

  

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)

            Console.Write(arr[i]+" ");

        Console.Read();

    }

  

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

    public static void Main()

    {

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

        int n = arr.Length;

  

        HeapSort ob = new HeapSort();

        ob.sort(arr);

  

        Console.WriteLine("Sorted array is");

        printArray(arr);

    }

}

  
// Этот код добавлен
// Аканкша Рай (Abby_akku)

PHP

<?php

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

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

function heapify(&$arr, $n, $i)

{

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

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

    $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[$i] = $arr[$largest];

        $arr[$largest] = $swap;

  

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

        heapify($arr, $n, $largest);

    }

}

  
// основная функция для сортировки в куче

function heapSort(&$arr, $n)

{

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

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

        heapify($arr, $n, $i);

  

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

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

    {

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

        $temp = $arr[0];

            $arr[0] = $arr[$i];

            $arr[$i] = $temp;

  

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

        heapify($arr, $i, 0);

    }

}

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

function printArray(&$arr, $n)

{

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

        echo ($arr[$i]." ") ; 

          

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

    $arr = array(12, 11, 13, 5, 6, 7);

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

  

    heapSort($arr, $n);

  

    echo 'Sorted array is ' . "\n";

      

    printArray($arr , $n);

  
// Этот код предоставлен Shivi_Aggarwal
?>


Выход:

Sorted array is
5 6 7 11 12 13

Вот предыдущий код C для справки.

Примечания:
Сортировка кучи — это алгоритм на месте.
Его типичная реализация не стабильна, но может быть сделана стабильной (см. Это )

Сложность времени: Сложность времени heapify — O (Logn). Временная сложность createAndBuildHeap () равна O (n), а общая временная сложность сортировки кучи — O (nLogn).

Приложения HeapSort
1. Сортировать почти отсортированный (или отсортированный по K) массив
2. k самых больших (или самых маленьких) элементов в массиве

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

Фотосъёмка:





Тест на кучу сортировки

Другие алгоритмы сортировки на GeeksforGeeks / GeeksQuiz:
QuickSort , выбор сортировки , Bubble Сортировка , вставка Сортировка , Merge Сортировка , Heap Сортировка , QuickSort , Radix Сортировка , Counting Сортировка , Ковш Сортировка , ShellSort , расческа Сортировать , Pigeonhole Сортировка

Практика кодирования для сортировки.

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

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

Пирамидальная сортировка

0.00 (0%) 0 votes