\input style \chapnotrue \chapno=5 \subchno=2 \subsubchno=2 \subsubchap{Янпрхпнбйю оняпедярбнл бшанпю} Еые ндмн бюфмне яелеиярбн лернднб янпрхпнбйх нямнбюмн мю хдее лмнцнйпюрмнцн бшанпю. Бепнърмн, опняреиьюъ янпрхпнбйю оняпедярбнл бшанпю ябндхряъ й якедсчыелс: \medskip \item{i)} Мюирх мюхлемэьхи йкчв; оепеякюрэ яннрберярбсчысч гюохяэ б накюярэ бшбндю х гюлемхрэ йкчв гмювемхел "$\infty$" (йнрнпне он опедонкнфемхч анкэье кчанцн пеюкэмнцн йкчвю). \item{ii)} Онбрнпхрэ ьюц (i). Мю щрнр пюг асдер бшапюм йкчв, мюхлемэьхи хг нярюбьхуяъ, рюй йюй пюмее мюхлемэьхи йкчв ашк гюлемем мю $\infty$. \item{iii)} Онбрнпърэ ьюц (i) дн реу онп, онйю ме асдср бшапюмш $N$ гюохяеи. \medskip \noindent Гюлерхл, врн щрнр лернд рпеасер мюкхвхъ бяеу хяундмшу щкелемрнб дн мювюкю янпрхпнбйх, ю щкелемрш бшбндю нм онпнфдюер онякеднбюрекэмн, ндхм гю дпсцхл. Йюпрхмю, он ясыеярбс, опнрхбнонкнфмю лерндс бярюбнй, б йнрнпнл хяундмше щкелемрш днкфмш онярсоюрэ онякеднбюрекэмн, мн бокнрэ дн гюбепьемхъ янпрхпнбйх мхвецн ме хгбеярмн на нйнмвюрекэмнл бшбнде. Пъд бшвхякхрекэмшу люьхм (мюопхлеп, люьхмш я жхйкхвеяйни аюпюаюммни оюлърэч) хлеер бярпнеммсч йнлюмдс "мюирх мюхлемэьхи щкелемр", йнрнпюъ бшонкмъеряъ я анкэьни яйнпнярэч. Мю рюйху люьхмюу янпрхпнбйю сйюгюммшл лернднл нянаеммн опхбкейюрекэмю, еякх рнкэйн $N$ ме якхьйнл бекхйн. Нохяюммши лернд рпеасер $N-1$ япюбмемхи йюфдши пюг, йнцдю бшахпюеряъ нвепедмюъ гюохяэ; нм рюйфе рпеасер нрдекэмни накюярх бшбндю б оюлърх. Хлееряъ нвебхдмши яоняна меяйнкэйн онопюбхрэ яхрсюжхч, хгаефюб опх щрнл хяонкэгнбюмхъ $\infty$: бшапюммне гмювемхе лнфмн гюохяшбюрэ б яннрберярбсчысч онгхжхч, ю гюохяэ, йнрнпюъ ее гюмхлюкю, оепемняхрэ мю леярн бшапюммни. Рнцдю щрс онгхжхч ме мсфмн пюяялюрпхбюрэ бмнбэ опх онякедсчыху бшанпюу. Мю щрни хдее нямнбюм мюь оепбши юкцнпхрл янпрхпнбйх оняпедярбнл бшанпю. \alg S.(Янпрхпнбйю оняпедярбнл опнярнцн бшанпю.) Гюохях $R_1$,~\dots, $R_N$ оепепюглеыючряъ мю рнл фе леяре. Оняке гюбепьемхъ янпрхпнбйх ху йкчвх асдср сонпъднвемш: $K_1\le \ldots\le K_N$. Янпрхпнбйю нямнбюмю мю нохяюммнл бшье лернде, еякх ме явхрюрэ рнцн, врн анкее, сднамн, нйюгшбюеряъ, бшахпюрэ ямювюкю \emph{мюханкэьхи} щкелемр, гюрел брнпни он бекхвхме х р. д. \st[Жхйк он $j$.] Бшонкмхрэ ьюцх \stp{2} х \stp{3} опх $j=N$, $N-1$, \dots, 2. %% 170 \st[Мюирх~$\max(K_1,~\ldots, K_j)$.] Мюирх мюханкэьхи хг йкчвеи~$K_j$, $K_{j-1}$,~\dots, $K_1$; осярэ щрн асдер~$K_i$. \st[Онлемърэ леярюлх я~$R_j$.] Бгюхлнгюлемхрэ гюохях~$R_i\xchg R_j$. (Реоепэ гюохях~$R_j$,~\dots, $R_N$ гюмхлючр ябнх нйнмвюрекэмше онгхжхх.) \algend \picture{Пхя. ~21. Янпрхпнбйю опняршл бшанпнл.} Б рюак.~1 онйюгюмн деиярбхе щрнцн юкцнпхрлю мю ьеярмюджюрэ йкчвеи, бшапюммшу мюлх дкъ опхлепнб; щкелемрш, оперемдсчыхе мю рн, врнаш нйюгюрэяъ люйяхлюкэмшлх бн бпелъ онхяйю б ьюце~S2, бшдекемш фхпмшл ьпхтрнл. {\catcode`\!=\active\def!#1.{{\bf #1}} \htable{Рюакхжю 1}% {Янпрхпнбйю оняпедярбнл опнярнцн бшанпю}% {\strut\hfil$#$\hfil\bskip&&\bskip\hfil$#$\hfil\bskip\cr 503 & 087 & 512 & 061 &!908.& 170 &!897.& 275 & 653 & 426 & 154 & 509 & 612 & 677 &!765.&!703.\cr 503 & 087 & 512 & 061 & 703 & 170 &!897.& 275 & 653 & 426 & 154 & 509 & 612 & 677 &!765.& 908 \cr 503 & 087 & 512 & 061 & 703 & 170 &!765.& 275 & 653 & 426 & 154 & 509 & 612 &!677.& 897 & 908 \cr 503 & 087 & 512 & 061 &!703.& 170 &!677.& 275 &!653.& 426 & 154 & 509 &!612.& 765 & 897 & 908 \cr 503 & 087 & 512 & 061 & 612 & 170 &!677.& 275 &!653.& 426 & 154 &!509.& 703 & 765 & 897 & 908 \cr 503 & 087 & 512 & 061 & 612 & 170 & 509 & 275 &!653.&!426.&!154.& 677 & 703 & 765 & 897 & 908 \cr \ldots\cr 061 &!087.& 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr }} Яннрберярбсчыюъ \MIX-опнцпюллю днбнкэмн опнярю. \prog S.(Янпрхпнбйю оняпедярбнл опнярнцн бшанпю.) Йюй х б опедшдсыху опнцпюллюу щрни цкюбш, гюохях, мюундъыхеяъ б ъвеийюу нр~$|INPUT|+1$ дн~$|INPUT|+N$, янпрхпсчряъ мю рнл фе леяре он йкчвс, гюмхлючыелс онкмне якнбн. Гмювемхъ пецхярпнб: $|rA|\equiv \hbox{рейсыхи люйяхлсл}$, $|rI1|\equiv j-1$, $|rI2|\equiv k$ (хмдейя опх онхяйе), $|rI3|\equiv i$. Опедонкюцюеряъ, врн~$N\ge 2$. \code START & ENT1 & N-1 & 1 & S1. Жхйк он~$j$. $j\asg N$. 2H & ENT2 & 0,1 & N-1 & S2. Мюирх~$\max(K_1, \ldots, K_j)$. $k\asg j-1$. & ENT3 & 1,1 & N-1 & $i\asg j$. & LDA & INPUT,3 & N-1 & $|rA|\asg K_i$. 8H & CMPA & INPUT,2 & A & JGE & *+3 & A & Оепеунд, еякх~$K_i\ge K_k$. & ENT3 & 0,2 & B & Б опнрхбмнл яксвюе сярюмнбхрэ~$i\asg k$, %% 171 & LDA & INPUT, 3 & B & $|rA|\asg K_i$. & DEC2 & 1 & A & $k\asg k-1$. & J2P & 8B & A & Онбрнпхрэ, еякх~$k>0$. & LDX & INPUT+1,1& N-1 & S3. Онлемърэ леярюлх я~$R_j$. & STX & INPUT,3 & N-1 & $R_i\asg R_j$. & STA & INPUT+1,1& N-1 & $R_j\asg |rA|$. & DEC1 & 1 & N-1 & J1P & 2B & N-1 & $N\ge j \ge 2$. \endcode \progend Бпелъ пюанрш щрни опнцпюллш гюбхяхр нр вхякю щкелемрнб~$N$, вхякю япюбмемхи~$A$ х вхякю "опюбнярнпнммху люйяхлслнб"~$B$. Мерпсдмн бхдерэ, врн мегюбхяхлн нр гмювемхи хяундмшу йкчвеи $$ A=\perm{N}{2}={1\over 2}N(N-1). \eqno(1) $$ Якеднбюрекэмн, оепелеммни ъбкъеряъ рнкэйн бекхвхмю~$B$. Меялнрпъ мю бяч аегшяйсямнярэ опнярнцн бшанпю, ме рюй кецйн опнхгбеярх рнвмши юмюкхг бекхвхмш~$B$. Б соп. я~3 он~6 онйюгюмн, врн $$ B=(\min 0, \ave (N+1)H_n-2N, \max \floor{N^2/4}); \eqno(2) $$ б щрнл яксвюе нянаеммн хмрепеямшл нйюгшбюеряъ люйяхлюкэмне гмювемхе (ярюмдюпрмне нрйкнмемхе бекхвхмш~$B$ дн яху онп ме нопедекемн). Рюйхл напюгнл, япедмее бпелъ пюанрш опнцпюллш~S пюбмн $2.5N^2+3(N+1)H_N+3.5N-11$~едхмхж, р.~е.\ нмю кхьэ мелмнцхл ледкеммее опняршу бярюбнй (опнцпюллю~5.2.1S). Хмрепеямн япюбмхрэ юкцнпхрл~S я янпрхпнбйни лернднл осгшпэйю (юкцнпхрл~5.2.2Б), рюй йюй лернд осгшпэйю лнфмн пюяялюрпхбюрэ йюй юкцнпхрл бшанпю, б йнрнпнл хмнцдю бшахпюеряъ анкее ндмнцн щкелемрю гю пюг. Он щрни опхвхме опх янпрхпнбйе лернднл осгшпэйю опнхгбндхряъ лемэье япюбмемхи, вел опх опнярнл бшанпе, х нмю, йюй лнфер онйюгюрэяъ, опедонврхрекэмее. Мн б деиярбхрекэмнярх опнцпюллю~5.2.2Б анкее вел бдбне ледкеммее опнцпюллш~S! Янпрхпнбйю лернднл осгшпэйю опнхцпшбюер хг-гю рнцн, врн б меи бшонкмъеряъ якхьйнл лмнцн налемнб, б рн бпелъ йюй опх янпрхпнбйе опняршл бшанпнл опнхгбндхряъ нвемэ люкн оепеяшкнй дюммшу. \section Сянбепьемярбнбюмхъ опнярнцн бшанпю. Ясыеярбсер кх йюйни-мхасдэ яоняна сксвьхрэ лернд бшанпю, хяонкэгселши б юкцнпхрле~S? Бнгэлел й опхлепс онхяй люйяхлслю б ьюце~S2: бнглнфем кх ясыеярбеммн анкее ашярпши яоняна мюунфдемхъ люйяхлслю? Нрбер мю щрнр бнопня---\emph{мер!} \proclaim Келлю~M. Б кчанл юкцнпхрле мюунфдемхъ люйяхлслю хг $n$~щкелемрнб, нямнбюммнл мю япюбмемхх оюп щкелемрнб, менаундхлн бшонкмхрэ он йпюимеи лепе $n-1$~япюбмемхи. %%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\rfloor1$, рн сярюмнбхрэ $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}r$, рн оепеирх й ьюцс \stp{8}. \st[Мюирх "анкэьецн" яшмю.] Еякх $K_j