Сортировка с помощью d-кучи

Реализация алгоритма сортировки с помощью d-кучи (см. [1], [2]) массива a длины n осуществляется процедурой SORT_D(a, n). При этом после выполнения последней итерации цикла while массив a упорядочен по невозрастанию, а после исполнения  цикла for упорядочивается по неубыванию.

В данной задаче массивом ключей d-кучи является массив a. Предполагаем, что d-куча реализуется на массиве key[1..n] ключей.

Реализация основных операций для работы с d-кучами. Функция minchild(i, key, n, d) позволяет для i-го узла n-элементной d-кучи с массивом ключей key находить его непосредственного потомка с минимальным ключом. Если у i-го узла нет потомков, то minchild(i, key, n, d) = i. Данная функция использует функции first_child(n, d, i), last_child(n, d, i), father(n, d, i), выдающие номера первого потомка, последнего потомка и родителя узла i n-элементной d-кучи соответственно. Значение father(n, d, 1) = 1, и если у i-го узла нет потомков, то first_child(n, d, i) = 0, last_child(n, d, i) = 0.

  • Ф-я сортировки массива key
<span style="color: #0000ff;">void sort_d ()</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">N_d = N - 1 ;</span>
<span style="color: #0000ff;">create_queue() ;</span>
<span style="color: #0000ff;"> </span>
<span style="color: #0000ff;">while (N_d &gt;= 0)</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">delete_min() ;</span>
<span style="color: #0000ff;">}</span>
<span style="color: #0000ff;">};</span>

create_queue() ; – ОБРАЗОВАТЬ_ОЧЕРЕДЬ

delete_min() ; – УДАЛИТЬ_МИНИМАЛЬНЫЙ

N – количество элементов массива

<span style="color: #0000ff;">void create_queue ()</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">for (int i = N_d; i &gt;= 0; --i)</span>
<span style="color: #0000ff;">inbedding (i) ;</span>
<span style="color: #0000ff;">};</span>
<span style="color: #0000ff;">void delete_min ()</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">int key0 = key[0],temp0 ;</span>
<span style="color: #0000ff;">key[0] = key[N_d] ;</span>
<span style="color: #0000ff;">key[N_d] = key0 ;</span>
<span style="color: #0000ff;">--N_d ;</span>
<span style="color: #0000ff;">if(N_d &gt;= 0) inbedding(0) ;</span>
<span style="color: #0000ff;">};</span>

inbedding (i) ; – ПОГРУЖЕНИЕ

void inbedding (int i)

{

int temp0, temp1 ;

int c = min_child (i) ;

while ((c != 0)&&(key[c] < key[i]))

{

temp1 = key[i] ;

key[i] = key[c] ;

key[c] = temp1 ;

i = c ;

c = min_child(c) ;

}

};

int last_child(int i)

{

int k = first_child(i) ;

if (k == i) return i ;

else if ((k + d – 1) <= N_d) return (k + d – 1) ;

else return N_d ;

};

int first_child(int i)

{

int k = i * d + 1 ;

if (k > N_d) return i ;

else return k ;

};

int min_child (int i)

{

int kf = first_child(i) ;

int kl ;

int min_key ;

int min_ch ;

if (kf == 0) return 0 ;

else

{

kl = last_child(i) ;

min_key = key[kf] ;

min_ch = kf ;

for (int j = kf ; j <= kl ; ++j)

if (key[j] < min_key)

{

min_key = key[j] ;

min_ch = j ;

}

}

return min_ch ;

};

Оставить комментарий

Вы должны быть зарегистрированы чтобы комментировать.