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

Question

В школе в настоящее время мы изучаем алгоритмы сортировки на Java, и я получил для домашней работы сортировку кучи. Я читал, я пытался узнать как можно больше, но, похоже, я просто не могу понять концепцию.

Я не прошу вас написать мне программу на Java, если бы вы просто объяснили мне как просто, как работает сортировка кучи.

Answer 1

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

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

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

                                    73                          
                                 7      12          
                               2   4  9   10    
                             1          

будет {73,7,12,2,4,9,10,1}

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

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

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

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

    10
  12

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

    12
  10

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

    12
  10  7

Добавить 73

          12
       10     7
    73

10 <73, поэтому нужно поменять местами: </p>

          12
       73     7
    10

12 <73, поэтому нужно поменять местами: </p>

          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 - своп </p>

          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 - поменяйте местами </p>

          12
        1    9
    10   2  4   7

1 <10 - так что поменяйте местами </p>

          12
       10     9
     1   2  4   7

Снять 12 - заменить на 7

          7
       10     9
     1   2  4   

7 <10 - поменяйте местами </p>

          10
       7     9
     1   2  4   

Снимите 10 - замените на 4

          4
       7     9
    1   2  

4 <7 - своп </p>

          7
       4     9
    1   2  

7 <9 - своп </p>

          9
       4     7
    1   2 

Снять 9 - заменить на 2

          2
       4     7
    1   

2 <4 - поменяйте местами </p>

          4
       2     7
    1  

4 <7 - поменяйте местами </p>

          7
       2     4
    1  

Снимите 7 - замените на 1

          1
       2     4

1 <4 - поменять их местами </p>

          4
       2     1

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

          1
       2

1 <2 - поменяйте местами </p>

          2
       1

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

          1

Взять 1

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

Answer 2

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

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

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

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

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

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

Сортировка кучи эффективна, поскольку обе операции Insert и Delete-Max в куче выполняются одновременноO (log n) время, означающее, что n вставок и удалений может быть выполнено в куче за O (n log n) времени. Более точный анализ можно использовать, чтобы показать, что на самом деле это занимает Θ (n log n) времени независимо от входного массива.

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

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

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

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

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

Answer 3

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

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

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

Answer 4

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

... э-э, ужасно .

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

Как взято из Википедия , куча:

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

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

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

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

Надеюсь, моя ужасная напыщенная речь помогла вам!Это немного многословно;прости за это ...

Answer 5

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

Answer 6

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

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

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

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

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

  }
}