\input style
%%172 
\proof 呋� ����������� ����� $n-1$ ���������, �� �������� �� ������� ���� 
��� ��������, ��� ������� �� ���� ���������� �� ������ ��������, 
�������������� �� �� ��������. 񋅄���������, �� ��� � �� ������, 
������� �� ���� ���� ��������� ������, �, ������, �� ������ ���������� ��������.
\proofend

򀊈� �������, ������� ������, � ������� ������������ ���������� �������, 
������ �������� �� ����� ��� �� $n-1$ �����. ����� �� ���, ��� ��� ���� 
������� ����������, ���������� �� $n$ ��������� �������, ����� ����� 
��������� ����� ������� $n^2$? � �������, ����� M ��������� ������ � 
\emph{�������} ���� ������; ��� ����������� ������� ����� 
������������ ����������� ����� ����������. 퀏�����, � ���.~8 ��������,
 ��� ������������ ������� ��������� ���������~S ���������� ��������� ����� ���������.

���������� 16 �����, �������������� � 1-� ������ � ����.~1. � �� 
�������� ���������� ����� ��� ����������� 
�������---������� ��� ����� �� ������ ������ �� ������ �����. 퀗��� ����� � 
����������� �����������, �������� ������ ������, � ������ �������������� � ������
$$
512, 908, 653, 765;
$$
����� ���������� �� ���� ������� ��������� 908 � ����� ���������� �� 
���� �����. ����� �������� ������ �� �������� �������, ���������� 
����������� ������� ��������� ��� �������� ������, ���������� 908; 
���������� �� $\{170, 897, 275\}$ ����� 897, � ����� ���������� �����
$$
512, 897, 653, 765
$$
��� 897. ����������, ��� ���� ����� �������� ������ �� �������� �������, 
���������� ���������� �� $\{170, 275\}$, � ����� ���������� ��
$$
512, 275, 653, 765
$$
� �. �. ꀆ��� �����, ����� �������, ������� �� ����� 6 �������������� 
���������. ⎎���, ���� $N$---������ �������, �� ����� ��������� ���� �� 
$\sqrt N$ ����� �� $\sqrt N$ ��������� � ������;
����� �����, ����� �������, ������� �� ����� ��� $\sqrt{N}-1$ ��������� 
������ ������ ����� ���������� �������� ���� $\sqrt{N}-1$ ��������� ����� 
"������� �����". ���� ����� ������� �������� "������������ �����"; ����� 
����� ������ ��� ���� ���� $O(N\sqrt{N})$, ��� ����������� �����, ��� $O(N^2)$.

셒�� ������������� ������ ������� ����������� 
�.~X.~������� [{\sl JACM\/}, {\bf 3} (1956), 152--154]; �� ������, ��� ��� 
���� ����� .��������, ������� � ���������� ����� ����������� ������, 
������ ��������� ������� � �. �. 퀏�����, ����� �����������
%%173
������ ������� � ���, ����� ��������� ���� �� $\root 3\of N$ ������� �����,
 ������ �� ������� �������� �� $\root 3\of N$ ����� ����� �� $\root 3\of 
N$ �������; ����� ������ ��������������� $N\root 3\of N$. 呋� ������� 
��� ���� �� �� ������� ����������, �� �� ������ � ����, ��� ����� ������ 
"����� $n$-� �������", ���������� �� ��������� ��������� ������. ␅�� 
������ ����� ������ ��������������� $N \log N$; �� ����� �������� ��� 
\dfn{������� �� ������}.
\section ⛁�� �� ������. ����� ���������� ����������� ������ �� ������ 
����� ����� ����������, ���� ��������������� ��������� � �������� 
"�������� � ����������". ����������, ��������, ���������� ������������ 
�� ����������� �������, ���������� �� ���.~22. 䆈� ��������� 䎍�, � 
䆎 ��������� 䆅��; ����� � ��������� ���� 䆎 ���������� � 䆈�� � �. �.

� ���.~22 ��������, ��� 䆎---������� ����� ������ �����������, � ��� 
����, ����� ���������� ���, ������������� $8-1=7$ ������ (�. �. ���������).
 䈊 ����� �� ����������� ����� ������ �� ���� �������: ����� �� 
�����������, � ������� ������� 䆎, ������� ���� ������������ � ������ 
���� 䆅��, ��� �� ��������� ������ �� ���� �������. ⒎���� ������ ����� 
����������, �������� 䆅�� ������� � 䆈���, � ���������� ����� �����---� 
䈊��; ����� ��� �������������� ����� ��������� ��� ����������� ������� �� 
���� ������, ������ �� ���� ����������� ���, ������� �� ��������� �� 
���������� ���.

⎎��� ����� "�������" ������, ������������ � ����� ������, � �������� ��� 
����������� ������ �������. �������� ����� ������� ������ ��������, 
��� ������������� ������ �� ���� ��������� ������ ������ ���������, � 
������ �� �������� � �����, ���� ����� ��������� ����������� � 
������� ������� ������. 䋟 ����� ����� �������� ���� ���� ����, � ������, 
��� ��� ��� ������ ���������� �� ���� ������ ���������� ����� $\lceil 
\log_2 N\rceil$) �������������� ���������. 񓌌�����
%%174
\picture{���. 23. ��� ���������� ����������� ������ �� ������...}
%% 175
����� ���������� ����� ���������� ����������� ������ �������� 
��������������� $N\log N$.

� ���.~23 ���������� ����������� ������ �� ������ ������������ ���� 16 
�����. 瀌����, ��� ��� ����, ����� �����, ���� ��������� ��������� 
������� "$-\infty$", ���������� �������, ������ ������ ����, ����������� � 
�����. ���� ���� ������������ � ���������������� �������� ��������� 
��� �������, ����������� ������� �����, � �� ��� ����. ��� �������, ��� 
���������� ������ ��� $N$ �������� �������, $N-1$ ����-���������� � $N$ 
��������� �������. (����������, ���� �����
\picture{���. 24.  ������� ������������� ������� ���������� � 
����������. ꀆ��� ����������� �� ���� ������� ���������������� � ��������.}
���� �� ����� ��� �� ����, �� �� ����� ��������� ��������� ������ � 
����������� ������.)

����� ������� �� ������������� ������������������, ������� �� ���������� 
��������, � ���� ����� ������� �������� ������ �� ��� ���, ���� �� �� 
��������� � ������� �� ������ ���� �� ���������, ��� ������� ���.~10 �� 
�������� ��� ��� �������� �����.

� �� ����������� ������ �� ������, ���������, �� ��������, 
�.~�.~���������� [A Programming Language (Wiley, 1962), 223--227], 
��������� ������������� ����������, ��������� ������� ����������� 
"������������ ������": ����� ���������� ����� �� ������ ������ ����������� 
�����, �� �� ������ ������ ��� ����� �� ����� �������� �� "$-\infty$"; 
����� �� ���������� ������������ ����� � ������ ������������ �� ������,
 �� ��� ����� �������� �������, ������� � ����� ������ ��� ����� ������ 
���������, �� ��� ������� ����� (� ������ ���������� �� ���� ������, 
������������� ��� ���). ⛏����� ��� �������� ������� ���, ������� 
��������, ������ �� ���.~23(�) � ���.~24.

ꎋ� ����� ������ ��������� ����� �������, ����� ���������� ���������� 
�� "����������" �������, ���������� �� ���.~23, � "����������": ��������� 
�������, �����������
%% 176
� �����, ������������ ����� ���������� �� ��� ��������, ������������ ����� 
���������� �� �������� ���������� � �. �. ���� �������� �������� �� 
������� �� ������ �� ����������� �������, ������� �� ������������� ������� ����������.

�������� ������ �������, ��� � ����������� ������ ���� ������ 
�����������---�� ��������� �������� ������ ��������� $-\infty$ �~$-\infty$. 
(������ ���������� �������, �� �� ����� ������� ������� ���������� 
����� ���������� �� $-\infty$, � ��� ���������� ������ ����� �� ������ 
������ ����������� �������������� ������ ����� �� ����� ��������� $-\infty$.)
\picture{���. 25. ������������� ������������� ������ ��� 
������� ��������� ������.}

� ���.~23 �~24 ���������� \emph{������ �������� �������} � 16 ��������� 
������ (��. � �.~2.3.4.5); ����� ������� ������ ������� � 
���������������� ������� ������, ��� �������� �� ���.~25. 瀌����, ��� 
����� ���� ����� $k$ �������� ���� $\lfloor k/2\rfloor$ , � ��� ��������� 
�������� ���� $2k$ � $2k+1$. ��� �������� ��� ���� ������������ 
����������� ������, ��������� �������� ����������� ����� ������������ ���� 
�� ���� $k$ � ����� $2k$ �~$2k+1$, ��� ����� �� ���� $k$ � ����� $k\oplus 
1$ 
�~$\lfloor k/2\rfloor$. (焅�� ����� $k\oplus 1$ ���������� ����� $k+1$ 
��� $k-1$ � ����������� ��  ����, �������� �� $k$ ������ ��� ��������.)

� ��� ��� � ����� �������� ������ �� ������ � ��� ��� ���� ���� 
��������������, ��� $N$ ���� ������� 2; � ���������������� ����� 
�������� � ������������ ��������� $N$, ��� ��� ������ �������� ������ � 
$N$ ��������� ������ �������� ��������� ��� ������ N. 

 � ������� ������ � ��������� �������: ������ �� � ���������� ������ 
�������� ������ ��� "$-\infty$"? � ������ ��, ���� �� �������, ���� �� 
��� ������������ ����������, ��������� �� ���.~24, ������� ����������� � 
������� 1--16
%%177
������� ��������� ������ ��� ������ ����������� "���", ���������� 
$-\infty$? ��������, ����� ������ � ������, ��� ��� ���� � 
���������������� ���������, ������ �� ������ ����������� $-\infty$, �� � 
���������� ����������� ����������� $N$ ������� �� ��� �� ����� ��� 
��������������� ������� ������. ��� �������� � ��� ������ ������� 
��������� ����������. 僎 ����� �.~�.~�.~󈋜��� [{\sl CACM\/}, {\bf 7} 
(1964), 347--348] �������� ���� �������� "�������������-�����������" ("heapsort").

\section ���������� ����������.  ᓄ�� �������� ���� ������ $K_1$, 
$K_2$, \dots, $K_N$ "���������", ����
$$
K_{\lfloor j/2\rfloor}\ge K_j \rem{ ��� $1\le \lfloor j/2\rfloor<j\le N$.}
\eqno(3)
$$
� ���� ������ $K_1\ge K_2$, $K_1\ge K_3$, $K_2\ge K_4$ � �.�.; ������ ��� 
������� ����������� �� ���.~24. � ���� �������, � ���������, ��� 
���������� ���� ����������� "�� ������� ��������":
$$
K_1=\max(K_1, K_2, \ldots, K_N).
\eqno(4)
$$
呋� �� �� ������ ���-������ ������������� ������������ �������� ���� � 
��������, �� ��� ��������� ������������ ��������� ���������� ����� ���� �� 
��������������� "����������" ���������� ������, �������� ���, ������� 
������� ����.

����������� ������ � ������ ���������� �������� ��������� �.~�.~􋎉� 
[{\sl CACM\/}, {\bf 7} (1964), 701]. �� ��� ������� ����������� ���� 
����� �������, ���
$$
K_{\lfloor j/2\rfloor}\ge K_j \rem{ ��� $l < \lfloor j/2\rfloor<j\le N$,}
\eqno(5)
$$
��� $l$---��������� ����� $\ge1$. (� �������� ����� ��� ������� ����������� 
"�������������" ��� $l=\floor{N/2}$, ��������� �� ���� ������ $j$ �� 
������������� ������� $\floor{N/2}<\floor{j/2}<j\le N$.) 
텒����� ������, ���, ������� ���� ��������� � ������ � ���� $l$, 
������������� ����, ����� �������������� ����������� (5) � �� ������, 
����� $\floor{j/2}=l$. 񋅄���������, ����� ��������� $l$ �� �������, ���� � 
����� ������ �� ����� ���������� ������� (3). ��� ���� 󈋜���� � 􋎉�� 
�������� � �������� ���������, ������� ����������� ������������ ��������.

\alg H.(���������� ����������.) 瀏��� $R_1$, \dots, 
$R_N$ ��������������� �� ��� �� �����; ����� ���������� ���������� �� 
����� ����� �����������: $K_1\le \ldots \le K_N$. 񍀗��� 
���� ��������������� � ��������, ����� ���� ������� �������� ����������� 
����������� � ������������ �� ���� ������������� �����. �����������, 
��� $N\ge2$.
\st[퀗������ ���������.] 󑒀������ $l\asg\floor{N/2}+1$, $r\asg N$.
\st[󌅍����� $l$ ���~$r$.] 呋�. $l>1$, �� ���������� $l\asg l-1$, $R\asg 
R_l$, $K\asg K_l$. (呋�  $l>1$, ��� ��������, ��� ����������
%% 178
������� �������������� ��������� ����� � ��������; ���� �� $l= 1$, �� ��� 
������, ��� ����� $K_1$, $K_2$, \dots, $K_r$ ��� �������� ��������.) � 
��������� ������ ���������� $R\asg R_r$, $K\asg K_r$, $R_r\asg R_1$  � 
$r\asg r-1$; ���� � ���������� ���������, ��� $r=1$, �� ���������� 
$R_1\asg R$ � ��������� ������ ���������.

\st[���������� � "�������������".] 󑒀������ $j\asg l$. 
(� ����� �������
$$
K_\floor{j/2}\ge K_j \rem{��� $l<\floor{j/2}<j\le r$,}
\eqno(6)
$$
� ������ $R_k$, $r<k\le N$, �������� ���� ������������� �����. ���� 
\stp{3}--\stp{8} ���������� ���������� "�������������"; ��
\picture{���. 26. ���������� ����������; ��������� ������� �������� "�������������".}
�������� ������������ ��������� $R_l\asg R$ � ����������� ������������ 
������� $R_l$, \dots, $R_r$ ����� �������, ����� ������� (6) ����������� � 
��� $\floor{j/2}=l$.)

\st[��������� ����.] 󑒀������ $i\asg j$ � $j\asg 2j$. (� ����������� 
����� $i = \floor{j/2}$.) 呋� $j< r$, �� ������� � ���� \stp{5};
���� $j=r$, �� ������� � ���� \stp{6}; ���� �� $j>r$, �� ������� � ���� \stp{8}.

\st[퀉�� "��������" ����.] 呋� $K_j<K_{j+1}$, �� ����������
$j\asg j+1$.

\st[ᎋ��� $K$?] 呋� $K\ge K_j$, �� ������� � ���� \stp{8}. 
\st[���� ��� �����.] 󑒀������ $R_i\asg R_j$ � ������������
� ���� \stp{4}.

\st[瀍���� $R$.] 󑒀������ $R_i\asg R$. (� ���� �������� 
"�������������", ������� � ���� \stp{�}, �������������.) ⎇��������� 
� ���� \stp{2}.
\algend
%%179
\bye



