Қазақстан республикасының бiлiм және ғылым министрлiгi

1 2 3 4 5

Алгоритмнің идеясын жазбалайық.

Пирамида — екілік ағаш, мұнда әр элементтің мәні астында тұрған элементтің мәнінен үлкен немесе оған тең болады.
Ағашты кез келген элементтермен толықтырып, оны пирамидаға айналдырып жеңіл түрде сұрыптауға болады.
Пирамиданың ең үлкен мәні пирамиданың ең жоғары сатысынды тұрады.
Шыңдағы, яғни, ең улкен элементті, алып тастаймызда нәтижеде шығатын массивтың ең соңына қоямыз.
Шыңдағы элементтің орнына ең төменгі сатыдағы элементті қоямыз.
Пирамиданы қалыптастырамыз (жаңадан сұрыптаймыз).
Қалған элементтердің ішіндегі ең үлкен элементті тағыда пирамиданың шыңына қоямыз. Тағыда оны алыпт тастаймызда массивтің соңғы элементтің алдынғы позициясына қоямыз

........

Пирамида қосымша орын алусыз бастапқы массивте сақталады. Пирамидының көлемі кішірее бере, ол массивтің кішірек бөлігіне ие бола береді, ал нәтиже пирамидадан бос қалған орындарға массивтың аяғынан бастап жазыла береді.

Сурет 1. Екілік ағаштың мысалысы:

Толықтырылған екілік ағаш деп келесі қасиеттері бар ағашты есептейміз:

Ағаштың барлық парақтық элементтері төменгі немесе жоғарғы сатыларда орналасады;
Сатыдағы барлық парақтар сатыны сол жақтан бастап толтырады;
Барлық сатылар элементтермен толық түрде толықтырылады.

Сол жақтан оң жаққа қарай толықтырылған ағаш:

Сурет 2. Толықтырылған ағаштың ішіндегі элементтерінің нумерациясы

Түйіннің атасының номері мұнда :

Достарыңызбен бөлісу:

1 2 3 4 5