Интуитивное понимание heapsort?

Ответ 1

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

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

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

                                    73                          
                                 7      12          
                               2   4  9   10    
                             1          

Было бы {73,7,12,2,4,9,10,1}

Первая часть требует двух шагов:

• Убедитесь, что у каждого node есть двое детей (если у вас недостаточно узлов для этого, как в приведенном выше дереве.
• Убедитесь, что каждый node больше (или меньше, если сортировка сначала), чем его дети.

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

Чтобы создать мою кучу выше, я добавлю 10 первых - это единственный node, поэтому ничего не делать. Добавьте 12, когда он находится слева:

    10
  12

Это удовлетворяет 1, но не 2, поэтому я поменяю их:

    12
  10

Добавить 7 - ничего не делать

    12
  10  7

Добавить 73

          12
       10     7
    73

10 < 73, поэтому их нужно поменять:

          12
       73     7
    10

12 < 73, поэтому их нужно поменять:

          73
       12     7
    10

Добавить 2 - ничего не делать

          73
       12     7
    10   2

Добавить 4 - ничего не делать

          73
       12     7
    10   2  4

Добавить 9

          73
       12     7
    10   2  4   9

7 < 9 - своп

          73
       12     9
    10   2  4   7

Добавить 1 - ничего не делать

          73
       12     9
    10   2  4   7
  1

У нас есть куча: D

Теперь вы просто удаляете каждый элемент сверху, каждый раз заменяя последний элемент на вершину дерева, а затем повторно балансируя дерево:

Возьмите 73 - положите 1 на место

          1
       12     9
    10   2  4   7

1 < 12 - замените их

          12
        1    9
    10   2  4   7

1 < 10 - замените их

          12
       10     9
     1   2  4   7

Возьмите 12 прочь - замените на 7

          7
       10     9
     1   2  4   

7 < 10 - обменять их

          10
       7     9
     1   2  4   

Возьмите 10 выкл. - замените на 4

          4
       7     9
    1   2  

4 < 7 - своп

          7
       4     9
    1   2  

7 < 9 - своп

          9
       4     7
    1   2 

Возьмите 9 выкл. - замените на 2

          2
       4     7
    1   

2 < 4 - обменять их

          4
       2     7
    1  

4 < 7 - обменять их

          7
       2     4
    1  

Возьмите 7 выкл. - замените на 1

          1
       2     4

1 < 4 - обменять их

          4
       2     1

Возьмите 4 - замените на 1

          1
       2

1 < 2 - обменять их

          2
       1

Возьмите 2 - замените на 1

          1

Возьмите 1

Отсортированный список вуаля.

Ответ 2

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

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

• Вставить, который вставляет элемент в кучу и
• Delete-Max, который удаляет и возвращает самый большой элемент кучи.

На очень высоком уровне алгоритм работает следующим образом:

• Вставить каждый элемент массива в новую двоичную кучу.
• Для я = n до 1:
  • Вызов Удалить-Макс в куче, чтобы получить самый большой элемент кучи назад.
  • Введите этот элемент в положение i.

Сортирует массив, потому что элементы, возвращаемые Удалить-Макс, находятся в порядке убывания. После удаления всех элементов массив затем сортируется.

Сортировка кучи эффективна, потому что операции Вставить и Удалить-Макс в куче работают в режиме O (log n), что означает, что n вставок и удалений может быть выполняется в куче в O (n log n) времени. Более точный анализ может быть использован, чтобы показать, что на самом деле он принимает время & theta; (n log n) независимо от входного массива.

Как правило, сортировка кучи использует две основные оптимизации. Во-первых, куча обычно создается внутри массива, обрабатывая сам массив как сжатое представление кучи. Если вы посмотрите на реализацию heapsort, вы обычно увидите необычное использование индексов массива на основе умножения и деления на два; эти обращения работают, потому что они обрабатывают массив как сжатую структуру данных. В результате для этого алгоритма требуется только O (1) вспомогательное пространство для хранения.

Во-вторых, вместо того, чтобы накапливать кучу по одному элементу за раз, куча обычно строится с использованием специализированного алгоритма, который выполняется во времени & Theta; (n) до постройте кучу на месте. Интересно, что в некоторых случаях это приводит к тому, что код легче читать, поскольку код можно повторно использовать, но сам алгоритм становится немного сложнее понять и проанализировать.

Иногда вы увидите, что heapsort сделан с тернарной кучей. Преимущество этого заключается в том, что в среднем оно немного быстрее, но если вы обнаружите, что реализация heapsort с использованием этого, не зная, что вы смотрите на него, может быть довольно сложной для чтения. Другие алгоритмы также используют одну и ту же общую структуру, но более сложную структуру кучи. Smoothsort использует гораздо более сложную кучу для получения наилучшего поведения O (n) при сохранении использования O (1) и O ( n log n) худшее поведение. Сорт тополя похож на smoothsort, но с использованием пространства O (log n) и немного лучшей производительностью. Можно даже подумать о классических алгоритмах сортировки, таких как сортировка сортировки и сортировка вставки как варианты сортировки кучи.

Как только у вас будет лучшее понимание heapsort, вы можете захотеть изучить алгоритм introsort, который объединяет quicksort, heapsort, и сортировку вставки для создания чрезвычайно быстрого алгоритма сортировки, который сочетает в себе силу быстрой сортировки (быстрая сортировка в среднем), heapsort (превосходное поведение в худшем случае) и сортировка вставки (быстрая сортировка для небольших массивов). Introsort - это то, что используется во многих реализациях функции С++ std::sort, и не очень сложно реализовать себя, когда у вас есть рабочий сервер.

Надеюсь, это поможет!

Ответ 3

Предположим, что у вас есть специальная структура данных (называемая кучей), которая позволяет вам хранить список чисел и позволяет вам извлекать и удалять наименьшее число в O(lg n).

Вы видите, как это приводит к очень простому алгоритму сортировки?

Жесткая часть (на самом деле это не так сложно) реализует кучу.

Ответ 4

Я помню, как мой профессор по анализу алгоритмов сказал нам, что алгоритм сортировки кучи работает как куча гравия:

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

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

Это более или менее простой способ узнать, как работает сортировка кучи.

Ответ 5

Возможно, интерактивная трассировка поможет вам лучше понять алгоритм. Вот демон .

Ответ 6

Я посмотрю, как я отвечаю на это, потому что мое объяснение сортировки кучи и какая куча будет немного...

... мм, ужасно.

Во всяком случае, во-первых, нам лучше проверить, что такое куча:

Как взято из Wikipedia, куча:

В информатике куча представляет собой специализированную древовидную структуру данных, которая удовлетворяет свойству кучи: если B является дочерним node A, тогда клавиша (A) ≥ (B). Это означает, что элемент с наибольшим ключом всегда находится в корне node, и поэтому такая куча иногда называется max-heap. (В противном случае, если сравнение отменено, наименьший элемент всегда находится в корне node, что приводит к мини-куче.)

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

Теперь сортировка кучи - это алгоритм сортировки O (n lg (n)). Вы можете немного прочитать об этом здесь и здесь. Это в значительной степени работает, поместив все элементы того, что вы пытаетесь сортировать в кучу, а затем построите отсортированный массив от самого большого элемента до самого маленького. Вы будете продолжать реструктурировать кучу, и поскольку самый большой элемент находится наверху (корневой) кучи во все времена, вы можете просто продолжать использовать этот элемент и помещать его в конец отсортированного массива. (То есть вы построите отсортированный массив в обратном порядке)

Почему этот алгоритм O (n lg (n))? Поскольку все операции над кучей - это O (lg (n)), и в результате вы будете выполнять n операций, в результате чего общее время работы O (n lg (n)).

Я надеюсь, что моя страшная просьба помогла вам! Это немного многословие; извините за это...

Ответ 7

Сортировка кучи включает простейшую логику с временной сложностью O (nlogn) и сложностью пространства O (1)

 public class HeapSort {

public static void main(String[] args) {
     Integer [] a={12,32,33,8,54,34,35,26,43,88,45};

     HeapS(a,a.length-1);

    System.out.println(Arrays.asList(a));

}

private static void HeapS(Integer[] a, int l) {


    if(l<=0)
        return;

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

        int index=a[2*i+1]>a[2*i+2]?2*i+1:2*i+2;
        if(a[index]>a[i]){
            int temp=a[index];
            a[index]=a[i];
            a[i]=temp;
        }

    }
    int temp=a[l];
    a[l]=a[0];
    a[0]=temp;

    HeapS(a,l-1);

  }
}