\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