\input style
%% 181
$7A+14B+4C+20N-2D+15\lfloor N/2 \rfloor -28$ RAVNO, TAKIM OBRAZOM, V 
SREDNEM PRIMERNO $16N \log_2 N+0.2N$ EDINIC.

gLYADYA NA TABL.~2, TRUDNO POVERITX V TO, CHTO PIRAMIDALXNAYA SORTIROVKA TAK 
UZH |FFEKTIVNA: BOLXSHIE KLYUCHI PEREMESHCHAYUTSYA VLEVO PREZHDE, CHEM MY USPEVAEM 
OTLOZHITX IH VPRAVO! eTO I V SAMOM DELE STRANNYJ SPOSOB SORTIROVKI PRI 
MALYH $N$. vREMYA SORTIROVKI 16 KLYUCHEJ IZ TABL.~2 RAVNO $1068u$, TOGDA KAK 
OBYCHNYJ METOD PROSTYH VSTAVOK (PROGRAMMA 5.2.1S) TREBUET VSEGO 
$514u$. pRI SORTIROVKE PROSTYM VYBOROM (PROGRAMMA S) TREBUETSYA $853u$.

pRI BOLXSHIH $N$ PROGRAMMA H BOLEE |FFEKTIVNA. nAPRASHIVAETSYA SRAVNENIE S 
SORTIROVKOJ METODOM shELLA S UBYVAYUSHCHIM SHAGOM (PROGRAMMA 5.2.1D) I BYSTROJ 
SORTIROVKOJ hOARA (PROGRAMMA 5.2.2Q), TAK KAK VO VSEH TREH PROGRAMMAH 
SORTIROVKA PROIZVODITSYA PUTEM SRAVNENIYA KLYUCHEJ, PRICHEM 
VSPOMOGATELXNOJ PAMYATI ISPOLXZUETSYA MALO ILI ONA NE ISPOLXZUETSYA VOVSE. 
pRI $N=1000$ SREDNIE VREMENA RABOTY RAVNY PRIBLIZITELXNO
$$
\eqalign{
160000u & \hbox{ DLYA PIRAMIDALXNOJ SORTIROVKI;}\cr
130000u & \hbox{ DLYA SORTIROVKI METODOM shELLA;}\cr
  80000u  &\hbox{ DLYA BYSTROJ SORTIROVKI.}\cr
}
$$
(\MIX---TIPICHNYJ PREDSTAVITELX BOLXSHINSTVA SOVREMENNYH VYCHISLITELXNYH 
MASHIN, NO, RAZUMEETSYA, NA KONKRETNYH MASHINAH POLUCHATSYA NESKOLXKO INYE 
OTNOSITELXNYE VELICHINY.) s ROSTOM $N$ PIRAMIDALXNAYA SORTIROVKA PREVZOJDET 
PO SKOROSTI METOD shELLA, NO ASIMPTOTICHESKAYA FORMULA $16N\log_2 N \approx  
23.08N\ln N$ NIKOGDA NE STANET LUCHSHE VYRAZHENIYA DLYA BYSTROJ SORTIROVKI 
$12.67N \ln N$. mODIFIKACIYA PIRAMIDALXNOJ SORTIROVKI, OBSUZHDAEMAYA V 
UPR.~18, USKORIT PROCESS NA MNOGIH VYCHISLITELXNYH MASHINAH, NO DAZHE S |TIM 
USOVERSHENSTVOVANIEM PIRAMIDALXNAYA SORTIROVKA NE DOSTIGNET SKOROSTI BYSTROJ SORTIROVKI.

s DRUGOJ STORONY, BYSTRAYA SORTIROVKA |FFEKTIVNA LISHX V SREDNEM; V 
NAIHUDSHEM SLUCHAE EE VREMYA RABOTY PROPORCIONALXNO $N^2$. pIRAMIDALXNAYA ZHE 
SORTIROVKA OBLADAET TEM INTERESNYM SVOJSTVOM, CHTO DLYA NEE NAIHUDSHIJ 
SLUCHAJ NE NAMNOGO HUZHE SREDNEGO. vSEGDA VYPOLNYAYUTSYA NERAVENSTVA
$$
A\le 1.5 N, \quad B \le N \lfloor \log_2 N \rfloor, 
\quad C\le N\lfloor \log_2 N\rfloor;
\eqno (8)
$$
TAKIM OBRAZOM, NEZAVISIMO OT RASPREDELENIYA ISHODNYH DANNYH VYPOLNENIE 
PROGRAMMY H NE ZAJMET BOLEE 
$18N \lfloor \log_2 N\rfloor+38N$
EDINIC VREMENI. pIRAMIDALXNAYA SORTIROVKA---PERVYJ IZ RASSMOTRENNYH NAMI DO 
SIH POR METODOV SORTIROVKI, VREMYA RABOTY KOTOROGO \emph{ZAVEDOMO} IMEET 
PORYADOK $N\log N$. sORTIROVKA POSREDSTVOM SLIYANIJ, KOTORAYA BUDET 
OBSUZHDATXSYA NIZHE, V P.~5.2.4, TOZHE OBLADAET |TIM SVOJSTVOM, NO ONA TREBUET 
BOLXSHE PAMYATI.

%% 182

\section nAIBOLXSHIJ IZ VKLYUCHENNYH---PERVYM ISKLYUCHAETSYA. 
v GL. 2 MY
VIDELI, CHTO LINEJNYE SPISKI CHASTO MOZHNO OSMYSLENNO RASKLASSIFICIROVATX 
PO HARAKTERU PROIZVODIMYH NAD NIMI OPERACIJ VKLYUCHENIYA I ISKLYUCHENIYA. 
\emph{sTEK} VEDET SEBYA PO PRINCIPU "POSLEDNIM VKLYUCHAETSYA---PERVYM 
ISKLYUCHAETSYA" V TOM SMYSLE, CHTO PRI KAZHDOM ISKLYUCHENII UDALYAETSYA SAMYJ 
MOLODOJ |LEMENT SPISKA (|LEMENT, KOTORYJ BYL VSTAVLEN POZZHE VSEH DRUGIH 
|LEMENTOV, PRISUTSTVUYUSHCHIH V DANNYJ MOMENT V SPISKE). pROSTAYA 
\emph{OCHEREDX} VEDET SEBYA PO PRINCIPU "PERVYM VKLYUCHAETSYA---PERVYM 
ISKLYUCHAETSYA" V TOM SMYSLE, CHTO PRI KAZHDOM ISKLYUCHENII UDALYAETSYA SAMYJ 
STARSHIJ IZ IMEYUSHCHIHSYA |LEMENTOV. v BOLEE SLOZHNYH SITUACIYAH, TAKIH, KAK 
MODELIROVANIE LIFTA V P.~2.2.5, TREBUETSYA SPISOK TIPA "NAIMENXSHIJ IZ 
VKLYUCHENNYH---PERVYM ISKLYUCHAETSYA", GDE PRI KAZHDOM ISKLYUCHENII UDALYAETSYA 
|LEMENT, IMEYUSHCHIJ NAIMENXSHIJ KLYUCH. tAKOJ SPISOK MOZHNO 
NAZVATX \dfn{PRIORITETNOJ OCHEREDXYU}, TAK KAK KLYUCH KAZHDOGO |LEMENTA 
OTRAZHAET EGO OTNOSITELXNUYU SPOSOBNOSTX BYSTRO POKINUTX 
SPISOK. sORTIROVKA POSREDSTVOM VYBORA---CHASTNYJ SLUCHAJ PRIORITETNOJ OCHEREDI, 
NAD KOTOROJ PROIZVODITSYA SNACHALA $N$ OPERACIJ VSTAVKI, A ZATEM $N$ 
OPERACIJ UDALENIYA.

pRIORITETNYE OCHEREDI VOZNIKAYUT V SAMYH RAZNOOBRAZNYH PRILOZHENIYAH. nAPRIMER,
 V NEKOTORYH CHISLENNYH ITERATIVNYH SHEMAH POVTORYAETSYA VYBOR |LEMENTA, 
IMEYUSHCHEGO NAIBOLXSHEE (ILI NAIMENXSHEE) ZNACHENIE NEKOTOROGO PROVEROCHNOGO 
KRITERIYA; PARAMETRY VYBRANNOGO |LEMENTA IZMENYAYUTSYA, I ON SNOVA 
VSTAVLYAETSYA V SPISOK S NOVYM PROVEROCHNYM ZNACHENIEM,- SOOTVETSTVUYUSHCHIM NOVYM 
ZNACHENIYAM PARAMETROV. pRIORITETNYE OCHEREDI CHASTO ISPOLXZUYUTSYA V 
OPERACIONNYH SISTEMAH PRI PLANIROVANII ZADANIJ. dRUGIE TIPICHNYE 
PRIMENENIYA PRIORITETNYH OCHEREDEJ UPOMINAYUTSYA V UPR.~15, 29 I~36; KROME 
TOGO, MNOGO PRIMEROV VSTRETITSYA V POSLEDUYUSHCHIH GLAVAH.

kAK ZHE REALIZOVATX PRIORITETNUYU OCHEREDX? oDIN IZ OCHEVIDNYH 
SPOSOBOV---PODDERZHIVATX OTSORTIROVANNYJ SPISOK |LEMENTOV, UPORYADOCHENNYH PO. 
KLYUCHAM. tOGDA VKLYUCHENIE NOVOGO |LEMENTA, PO SUSHCHESTVU, SVODITSYA K ZADACHE, 
RASSMOTRENNOJ NAMI PRI IZUCHENII SORTIROVKI VSTAVKAMI V P.~5.2.1. pRI 
DRUGOM, ESHCHE BOLEE OCHEVIDNOM SPOSOBE RABOTY S PRIORITETNOJ OCHEREDXYU 
|LEMENTY V SPISKE HRANYATSYA V PROIZVOLXNOM PORYADKE, I TOGDA DLYA 
VYBORA NUZHNOGO |LEMENTA, PRIHODITSYA OSUSHCHESTVLYATX POISK NAIBOLXSHEGO (ILI 
NAIMENXSHEGO) KLYUCHA KAZHDYJ RAZ, KOGDA NEOBHODIMO PROIZVESTI ISKLYUCHENIE. v 
OBOIH |TIH OCHEVIDNYH PODHODAH NEPRIYATNOSTX SOSTOIT V TOM, CHTO TREBUETSYA 
PORYADKA $N$ SHAGOV DLYA VYPOLNENIYA LIBO OPERACII VSTAVKI, LIBO OPERACII 
UDALENIYA, ESLI V SPISKE SODERZHITSYA $N$ |LEMENTOV, T. E. PRI BOLXSHIH $N$ 
|TI OPERACII ZANIMAYUT SLISHKOM MNOGO VREMENI.

v SVOEJ STATXE O PIRAMIDALXNOJ SORTIROVKE uILXYAME UKAZAL
%% 183
NA TO, CHTO PIRAMIDY IDEALXNO PODHODYAT DLYA PRILOZHENIJ S BOLXSHIMI 
PRIORITETNYMI OCHEREDYAMI, TAK KAK |LEMENT MOZHNO VSTAVITX V PIRAMIDU ILI 
UDALITX IZ NEE ZA $O(\log N)$ SHAGOV; K TOMU ZHE VSE |LEMENTY PIRAMIDY 
KOMPAKTNO RASPOLAGAYUTSYA V POSLEDOVATELXNYH YACHEJKAH PAMYATI. fAZA VYBORA V 
ALGORITME H---|TO POSLEDOVATELXNOSTX SHAGOV UDALENIYA V PROCESSE TIPA 
\emph{NAIBOLXSHIJ IZ VKLYUCHENNYH---PERVYM ISKLYUCHAETSYA}: CHTOBY ISKLYUCHITX 
NAIBOLXSHIJ |LEMENT $K_1$ MY UDALYAEM EGO I "PROTASKIVAEM" |LEMENT $K_N$ V 
NOVOJ PIRAMIDE IZ $N-1$ |LEMENTOV. (eSLI NUZHEN ALGORITM TIPA 
\emph{NAIMENXSHIJ IZ VKLYUCHENNYH---PERVYM ISKLYUCHAETSYA}, KAK PRI MODELIROVANII 
LIFTA, TO, OCHEVIDNO, MOZHNO IZMENITX OPREDELENIE PIRAMIDY, ZAMENIV V (3) 
ZNAK "$\ge$" NA "$\le$"; DLYA UDOBSTVA MY BUDEM RASSMATRIVATX ZDESX LISHX 
SLUCHAJ "NAIBOLXSHIJ IZ VKLYUCHENNYH---PERVYM ISKLYUCHAETSYA".) vOOBSHCHE, ESLI 
TREBUETSYA ISKLYUCHITX NAIBOLXSHIJ |LEMENT, A ZATEM VSTAVITX NOVYJ |LEMENT 
$x$, TO MOZHNO VYPOLNITX PROCEDURU PROTASKIVANIYA S $l=1$, $r=N$ I $K=x$. 
eSLI ZHE NEOBHODIMO VSTAVITX |LEMENT BEZ PREDVARITELXNOGO ISKLYUCHENIYA, TO 
MOZHNO VOSPOLXZOVATXSYA "VOSHODYASHCHEJ" PROCEDUROJ IZ UPR. 16.

\section sVYAZANNOE PREDSTAVLENIE PRIORITETNYH OCHEREDEJ. 
eFFEKTIVNYJ SPOSOB PREDSTAVLENIYA PRIORITETNYH OCHEREDEJ V VIDE 
SVYAZANNYH BINARNYH DEREVXEV PREDLOZHIL V 1971~G. kLARK~e.~kR|JN. eGO METOD 
TREBUET NALICHIYA V KAZHDOJ ZAPISI DVUH POLEJ SVYAZI I KOROTKOGO POLYA 
SCHETCHIKA, NO PO SRAVNENIYU S PIRAMIDAMI ON OBLADAET SLEDUYUSHCHIMI PREIMUSHCHESTVAMI:
\enumerate
\li eSLI S PRIORITETNOJ OCHEREDXYU RABOTAYUT KAK SO STEKOM, TO OPERACII 
VKLYUCHENIYA I ISKLYUCHENIYA BOLEE |FFEKTIVNY (ONI ZANIMAYUT FIKSIROVANNOE VREMYA, 
NE ZAVISYASHCHEE OT DLINY OCHEREDI).

\li zAPISI NIKOGDA NE PEREMESHCHAYUTSYA, IZMENYAYUTSYA TOLXKO UKAZATELI.

\li  mOZHNO SLITX DVE NEPERESEKAYUSHCHIESYA PRIORITETNYE OCHEREDI, SODERZHASHCHIE V 
OBSHCHEJ SLOZHNOSTI $N$ |LEMENTOV, V ODNU VSEGO ZA $O (\log N)$ SHAGOV.
\enumend

sLEGKA VIDOIZMENENNYJ METOD kR|JNA PROILLYUSTRIROVAN NA RIS.~27, NA KOTOROM 
POKAZAN OSOBYJ TIP STRUKTURY BINARNOGO DEREVA. kAZHDYJ UZEL SODERZHIT POLE 
|KEY|, POLE |DIST| I DVA POLYA SVYAZI---|LEFT| I |RIGHT|. pOLE |DIST| VSEGDA 
USTANAVLIVAETSYA RAVNYM DLINE KRATCHAJSHEGO PUTI OT |TOGO UZLA DO 
KONCEVOGO UZLA (T. E. DO PUSTOGO UZLA $\NULL$) DEREVA. eSLI SCHITATX, 
CHTO $|DIST|(\NULL) = 0$ I~$|KEY|(\NULL) =-\infty$, TO POLYA |KEY| I~|DIST| 
V |TOM DEREVE UDOVLETVORYAYUT SLEDUYUSHCHIM SOOTNOSHENIYAM:
$$
\displaylines{
\hfill|KEY| (|r|)\ge  |KEY| (|LEFT| (|P|)), |KEY| (|P|) \ge |KEY| (|RIGHT| 
(|P|));     \hfill\llap{(9)}\cr
\hfill|DIST| (|P|)=1+\min (|DIST| (|LEFT| (|P|)), |DIST| (|RIGHT| (|P|))); 
\hfill\llap{(10)}\cr
\hfill|DIST| (|LEFT| (|P|)) \ge  |DIST| (|RIGHT| (|P|)).\hfill\llap{(11)}\cr
}
$$
%%184
sOOTNOSHENIE (9) ANALOGICHNO USLOVIYU PIRAMIDY (3) I SLUZHIT GARANTIEJ TOGO, 
CHTO V KORNE DEREVA NAHODITSYA NAIBOLXSHIJ KLYUCH, A SOOTNOSHENIE (10)---|TO 
PROSTO OPREDELENIE POLYA |DIST|, SFORMULIROVANNOE VYSHE. sOOTNOSHENIE (11) 
PREDSTAVLYAET SOBOJ INTERESNOE NOVSHESTVO: IZ NEGO SLEDUET, CHTO KRATCHAJSHIJ 
PUTX K KONCEVOMU UZLU VSEGDA MOZHNO POLUCHITX, DVIGAYASX VPRAVO. mY
\picture{rIS. 27. pRIORITETNAYA OCHEREDX, PREDSTAVLENNAYA V VIDE 
LEVOSTORONNEGO DEREVA.}
BUDEM NAZYVATX BINARNOE DEREVO S |TIM SVOJSTVOM LEVOSTORONNIM DEREVOM, 
POSKOLXKU ONO, KAK PRAVILO, SILXNO "TYANETSYA" VLEVO.

iZ |TIH OPREDELENIJ YASNO, CHTO RAVENSTVO $|DlST|(|P|)=n$ PODRAZUMEVAET 
SUSHCHESTVOVANIE PO KRAJNEJ MERE $2^n$ KONCEVYH UZLOV NIZHE |P|; V PROTIVNOM 
SLUCHAE NASHELSYA BY BOLEE, KOROTKIJ PUTX OT |P| DO KONCEVOGO UZLA. tAKIM 
OBRAZOM, ESLI V LEVOSTORONNEM DEREVE IMEETSYA $N$ UZLOV, TO PUTX, VEDUSHCHIJ 
IZ KORNYA VNIZ PO NAPRAVLENIYU VPRAVO, SODERZHIT NE BOLEE CHEM $\lfloor 
\log_2(N+1)\rfloor$ UZLOV. nOVYJ UZEL MOZHNO VSTAVITX V PRIORITETNUYU 
OCHEREDX, PROJDYA PO |TOMU PUTI (SM. UPR.~32); SLEDOVATELXNO, V 
HUDSHEM SLUCHAE NEOBHODIMO VSEGO $O(\log N)$ SHAGOV. nAILUCHSHIJ SLUCHAJ
%%185
DOSTIGAETSYA, KOGDA DEREVO LINEJNO (VSE SVYAZI |RIGHT| RAVNY $\NULL$), A 
NAIHUDSHIJ SLUCHAJ DOSTIGAETSYA, KOGDA DEREVO ABSOLYUTNO SBALANSIROVANO.

chTOBY UDALITX UZEL IZ KORNYA, NUZHNO PROSTO SLITX DVA EGO PODDEREVA. 
oPERACIYA SLIYANIYA DVUH NEPERESEKAYUSHCHIHSYA LEVOSTORONNIH DEREVXEV, NA 
KOTORYE SSYLAYUTSYA UKAZATELI |P| I~|Q|, PO SVOEJ IDEE PROSTA: ESLI 
$|KEY|(|P|)\ge |KEY| (|Q|)$, TO BEREM V KACHESTVE KORNYA |P| I SLIVAEM |Q| S 
PRAVYM PODDEREVOM |P|; PRI |TOM IZMENITSYA $|DIST|(|P|)$, a $|LEFT|(|r|)$ 
MENYAETSYA MESTAMI S $|RIGHT|(|P|)$, ESLI |TO NEOBHODIMO. nETRUDNO SOSTAVITX 
PODROBNOE OPISANIE |TOGO PROCESSA (SM. UPR.~32).

\section sRAVNENIE METODOV RABOTY S PRIORITETNYMI OCHEREDYAMI. eSLI CHISLO 
UZLOV $N$ MALO, TO DLYA PODDERZHANIYA PRIORITETNOJ OCHEREDI LUCHSHE VSEGO 
PRIMENYATX ODIN IZ PROSTYH METODOV S ISPOLXZOVANIEM LINEJNYH SPISKOV. 
eSLI ZHE $N$ VELIKO, TO, OCHEVIDNO, GORAZDO BOLEE BYSTRYM BUDET METOD, VREMYA 
RABOTY KOTOROGO PORYADKA $\log N$. pO|TOMU BOLXSHIE PRIORITETNYE OCHEREDI OBYCHNO
PREDSTAVLYAYUT V VIDE PIRAMID ILI LEVOSTORONNIH DEREVXEV. v P.~6.2.3 MY 
OBSUDIM ESHCHE ODIN SPOSOB PREDSTAVLENIYA LINEJNYH SPISKOV V VIDE 
\emph{SBALANSIROVANNYH DEREVXEV}, KOTORYJ PRIVODIT K TRETXEMU METODU, 
PRIGODNOMU DLYA PREDSTAVLENIYA PRIORITETNYH OCHEREDEJ, S VREMENEM RABOTY 
PORYADKA $\log N$. pO|TOMU UMESTNO SRAVNITX |TI TRI METODA.

mY VIDELI, CHTO OPERACII NAD LEVOSTORONNIMI DEREVXYAMI V CELOM NESKOLXKO 
BYSTREE, CHEM OPERACII NAD PIRAMIDAMI, NO PIRAMIDY ZANIMAYUT MENXSHE PAMYATI. 
sBALANSIROVANNYE DEREVXYA ZANIMAYUT PRIMERNO STOLXKO ZHE PAMYATI, SKOLXKO 
LEVOSTORONNIE DEREVXYA (BYTX MOZHET, CHUTX MENXSHE); OPERACII NAD NIMI 
MEDLENNEE, CHEM NAD PIRAMIDAMI, A PROGRAMMIROVANIE SLOZHNEE, NO STRUKTURA 
SBALANSIROVANNYH DEREVXEV V NEKOTORYH OTNOSHENIYAH SUSHCHESTVENNO BOLEE GIBKAYA. 
rABOTAYA S PIRAMIDAMI, NE TAK PROSTO PREDSKAZATX, CHTO PROIZOJDET S 
|LEMENTAMI, ESLI U NIH RAVNYE KLYUCHI; NELXZYA GARANTIROVATX, CHTO |LEMENTY S 
RAVNYMI KLYUCHAMI BUDUT OBRABATYVATXSYA PO PRINCIPU "POSLEDNIM 
VKLYUCHAETSYA--- PERVYM ISKLYUCHAETSYA" ILI "PERVYM VKLYUCHAETSYA---PERVYM 
ISKLYUCHAETSYA", ESLI TOLXKO KLYUCH NE RASSHIREN I NE SODERZHIT 
DOPOLNITELXNOGO POLYA "PORYADKOVYJ NOMER VSTAVKI", I TOGDA RAVNYH KLYUCHEJ 
PROSTO NET. s DRUGOJ STORONY, ESLI PRIMENYATX SBALANSIROVANNYE DEREVXYA, 
MOZHNO LEGKO OGOVORITX TVERDYE USLOVIYA
OTNOSITELXNO RAVNYH KLYUCHEJ. mOZHNO TAKZHE VYPOLNYATX TAKIE DEJSTVIYA, KAK 
"VSTAVITX $x$ NEPOSREDSTVENNO PERED (ILI POSLE) $y$". sBALANSIROVANNYE 
DEREVXYA SIMMETRICHNY, TAK CHTO V LYUBOJ MOMENT MOZHNO ISKLYUCHITX LIBO 
NAIBOLXSHIJ, LIBO NAIMENXSHIJ |LEMENT,
V TO VREMYA KAK LEVOSTORONNIE DEREVXYA I PIRAMIDY DOLZHNY BYTX
TAK ILI INACHE ORIENTIROVANY. (sM. TEM NE MENEE UPR.~31, V KOTOROM
%% 186
\picture{rIS. 28. tAK VYGLYADIT PIRAMIDA...}
%%187
POKAZANO, KAK STROITX \emph{SIMMETRICHNYE} PIRAMIDY.) 
sBALANSIROVANNYE DEREVXYA MOZHNO ISPOLXZOVATX KAK DLYA POISKA, TAK I DLYA 
SORTIROVKI; I IZ SBALANSIROVANNOGO DEREVA MOZHNO DOVOLXNO BYSTRO UDALYATX 
POSLEDOVATELXNYE BLOKI |LEMENTOV. nO DVA SBALANSIROVANNYH DEREVA NELXZYA 
SLITX MENEE CHEM ZA $O(N)$ SHAGOV, V TO VREMYA KAK DVA LEVOSTORONNIH DEREVA 
MOZHNO SLITX VSEGO ZA $O (\log N)$ SHAGOV.

iTAK, PIRAMIDY NAIBOLEE |KONOMNY S TOCHKI ZRENIYA PAMYATI;
LEVOSTORONNIE DEREVXYA HOROSHI TEM, CHTO MOZHNO BYSTRO SLITX DVE 
NEPERESEKAYUSHCHIESYA PRIORITETNYE OCHEREDI; I, ESLI NUZHNO, ZA UMERENNOE 
VOZNAGRAZHDENIE MOZHNO POLUCHITX TU GIBKOSTX, KAKUYU PREDOSTAVLYAYUT 
SBALANSIROVANNYE DEREVXYA.

\section * aNALIZ PIRAMIDALXNOJ SORTIROVKI. aLGORITM H DO SIH POR NE BYL 
POLNOSTXYU PROANALIZIROVAN, NO NEKOTORYE EGO SVOJSTVA MOZHNO VYVESTI BEZ 
OSOBOGO TRUDA. pO|TOMU MY ZAVERSHIM |TOT PUNKT DOVOLXNO PODROBNYM 
ISSLEDOVANIEM, KASAYUSHCHIMSYA PIRAMID.

nA RIS. 28 POKAZANA FORMA PIRAMIDY IZ 26 |LEMENTOV;
KAZHDYJ UZEL POMECHEN DVOICHNYM CHISLOM, SOOTVETSTVUYUSHCHIM EGO INDEKSU V 
PIRAMIDE. zVEZDOCHKAMI V |TOJ DIAGRAMME POMECHENY
TAK NAZYVAEMYE \dfn{OSOBYE UZLY}, KOTORYE LEZHAT NA PUTI OT~1 K~$N$.

oDNA IZ NAIBOLEE VAZHNYH HARAKTERISTIK PIRAMIDY---NABOR RAZMEROV EE 
PODDEREVXEV. nAPRIMER, NA RIS.~28 RAZMERY PODDEREVXEV S KORNYAMI V UZLAH 
1,2, \dots, 26 RAVNY SOOTVETSTVENNO
$$
26^*, 15,10^*, 7, 7, 6^*, 3, 3, 3, 3, 3, 3, 2^*, 1,1,1,1,1,1,1,1,1,1,1,1, 1^*.
\eqno (12)
$$
zVEZDOCHKAMI OTMECHENY \dfn{OSOBYE PODDEREVXYA} S KORNYAMI V OSOBYH UZLAH; V 
UPR.~20 POKAZANO, CHTO ESLI $N$ IMEET DVOICHNOE PREDSTAVLENIE
$$
N=(b_n b_{n-1} \ldots b_1 b_0)_2, \qquad n=\lfloor\log_2 N\rfloor,
\eqno (13)
$$
TO RAZMERY OSOBYH PODDEREVXEV RAVNY
$$
(1 b_{n-1}\ldots b_1 b_0)_2, (1 b_{n-2}\ldots b_1 b_0)_2, \ldots,
(1 b_1 b_0)_2, (1 b_0)_2, (1)_2.
\eqno(14)
$$
(nEOSOBYE PODDEREVXYA VSEGDA ABSOLYUTNO SBALANSIROVANY, TAK CHTO IH RAZMERY 
VSEGDA IMEYUT VID $2^k-1$. v UPR.~21 POKAZANO, CHTO SREDI NEOSOBYH 
PODDEREVXEV IMEETSYA ROVNO
$$
\matrix{
\hbox{$\lfloor(N-1)/2 \rfloor$ RAZMERA  1,} &  & 
\hbox{$\lfloor(N-2)/4\rfloor$ RAZMERA 3,}\hfill\cr
\hbox{$\lfloor(N-4)/8\rfloor$ RAZMERA 7,} & \ldots  & 
\hbox{$\lfloor(N-2^{n-1})/2^n\rfloor$ RAZMERA $(2^n-1)$,}\hfill\cr
}
\eqno(15)
$$
nAPRIMER, NA RIS.~28 IZOBRAZHENO DVENADCATX NEOSOBYH PODDEREVXEV 
RAZMERA~1, SHESTX PODDEREVXEV RAZMERA~3, 
DVA---RAZMERA~7 I ODNO---RAZMERA~15.
%%188

\bye