Блог

В алгоритме сортировки кучи

 n=m
for k:= m div 2 down to 0
    downheap(k);
repeat
    t:=a[0]
    a[0]:=a[n-1]
    a[n-1]:=t
    n—
    downheap(0);
until n <= 0  
  

Может кто-нибудь, пожалуйста, объясните мне, что делается в строках

     n=m
    for k:= m div 2 down to 0
        downheap(k);  
  

Я думаю, что это процесс построения кучи, но что подразумевается под for k:= m div 2 down to 0

Также n — количество элементов.Итак, в представлении массива последний элемент хранится в [n-1]? Но зачем это делать для n> = 0. Разве мы не можем закончить при n> 0. Потому что первый элемент сортируется автоматически?

 n=m
for k:= m div 2 down to 0
    downheap(k);
  

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

 [5, 3, 2, 4, 1]
  

Или в виде дерева:

      5
  3     2
4   1
  

Длина равна 5, поэтому мы хотим начать с индекса 2 (предположим, что массив кучи на основе 1). downheap затем посмотрим на помеченный узел 3 и сравним его с наименьшим дочерним элементом. Поскольку 1 меньше 3, мы меняем местами элементы, дающие:

      5
  1     2
4   3
  

Поскольку мы достигли конечного уровня, мы закончили с этим элементом. Переходим к первому пункту, 5 . Он меньше 1 , поэтому мы меняем элементы местами:

      1
  5     2
4   3
  

Но элемент 5 по-прежнему больше, чем его дочерние элементы, поэтому мы делаем другой обмен:

      1
  3     2
4   5
  

И мы закончили. У вас есть допустимая куча.

Полезно сделать это вручную (с помощью карандаша и бумаги), чтобы создать большую кучу — скажем, 10 элементов. Это даст вам очень хорошее представление о том, как работает алгоритм.

Для целей построения кучи таким образом, не имеет значения, начинаются ли индексы массива с 0 или 1. Если массив основан на 0, то в конечном итоге вы выполняете один дополнительный вызов downheap , но это ничего не дает, потому что узел, который вы пытаетесь переместить вниз, уже является конечным узлом. Так что это немного неэффективно (один дополнительный вызов downheap ), но не вредно.

Однако важно, чтобы, если ваш корневой узел имеет индекс 1, вы останавливали цикл с n > 0 помощью, а не n >= 0 . В последнем случае вы вполне можете добавить фиктивное значение в свою кучу и удалить элемент, который должен быть там.

 for k:= m div 2 down to 0
  

Похоже, это псевдокод для:

 for(int k = m/2; k >= 0; k--)
  

Или, возможно

 for(int k = m/2; k > 0; k--)
  

В зависимости от того, включено значение «до 0» или нет.

Также n — количество элементов?

Изначально да, но он уменьшается в строке n- .

Разве мы не можем закончить при n> 0. Потому что первый элемент автоматически сортируется?

Да, это фактически то, что происходит. Как только N становится равным нулю n- , он проходит большую часть пути через тело цикла, поэтому единственное, что выполняется после этого и до until n <= 0 завершения, это downheap(0);