Турнирлік с±рыптау
Бинарлыќ тармаќтар шешімдер ќабылдау термаќтары ретінде кµп ќолданылады. Мысалы, спорттыќ турнирді алайыќ. М±нда єрбір ішкі т‰йін екі ойыншыныњ кездеріндегі жењімпазѓа сєйкес келеді.
Турнирлыќ m, n элементтен m массивті с±рыптауѓа ќолданылуы м‰мкін. Турнирлыќ с±рыптауды келесі мысалда ќарастырайыќ:
A[8]=(35, 25, 50, 20, 15, 45, 10, 40)
Осы массивті µсу ретімен с±рыптау ќажет.
1. Массив элементтері бинарлыќ тармаќ к дењгейінде болады. М±ндаѓы: 2k>=n n – массив элементтер саны. Б±л жаѓдайда 23=8, яѓни k=3 болады.
2. Ата-аналыќ т‰йінге ж±птарѓа элементтердіњ кішісі орналасады, ењ соњѓы салыстыру нєтижесінде массивтіњ ењ кіші элементі 0-дењгейіне (тамырына) т‰седі.
3.
-
10
Б
ір
элемент алынып тасталады.
4.
-
10
15
5
.
-
10
15
20
25
35
40
45
50
Осы процесс барлыќ жапыраќтары алынып тасталѓанша ж‰ргізіліп ж‰ре береді. Ењ соњѓы т‰йін (ењ ‰лкен элемент) барлыѓын ‰нсіз келісім бойынша шыѓады.
Дәріс 14.
Пирамидалар
Мақсаты: Пирамидалар, негізгі түсініктерін беру. Пирамидаларда түрлендірулер жүргізу, амалдар қолдану.
Пирамида дегеніміз – дењгейлер бойынша т‰йінтік реттілігі бар бинарлыќ тармаќ. Пирамидаларды максимальды пирамидалар жєне минимальды пирамидалар деп бµледі.
Максимальды пирамида – ата-аналыќ т‰йін µзініњ балаларыныњ єрќайсыснан ‰лкен немесе тењ болады. Т‰бірде ењ ‰лкен элемент жатады.
Минимальды пирамида – ата-аналыќ т‰йін µзініњ балаларыныњ єрќайсысынан кіші немесе тењ болады. Ал т‰бірде ењ кіші элемент жатады.
Мысалѓа, минимальды пирамидаѓа:
М
ысалѓа,
максимальды пирамидаѓа:
Пирамидалар клиентке минимальды элементке тура кіру жаѓдайында ќолданылады. Пирамида тізім болып табылады. Онда мєліметтер бинарлыќ тармаќ т‰рінде саќталады. Пирамидаларды µњдейтін барлыќ алгоритмдер µздері тармаќты жањартып, пирамидалыќ реттеуді ж‰зеге асырып отырулады ќажет.
Массивті пирамидаѓа т‰рлендіру
Пирамиданыњ соњѓы элементініњ индексі n-1-ге тењ. Оныњ ата-анасыныњ индексі n-2-ге тењ. Жєне ол пирамидалардыњ соњѓы жапыраќтыќ емес т‰йін болып табылады. Осы индекс массивті т‰рлендіру ‰шін бастапќы индекс болып табылады. Мынадай б‰тін санды массив берілсін:
А(10)=(9,12,17,30,50,20,60,65,4,19)
Оны пирамида т‰рінде былай жазамыз:
9
12
17
60
30
50
20
65
4
19
М±ндай жапыраќтардыњ индекстары 5,6,7,8,9 болады. Ата-анасының индекстары – 0,1,2,3,4.
қарастырамыз.
А(4)=50 ата-анасы өзінің А(9)=19 деген ұрпағынн үлкен болып табылады. Сондықтан А(9) бен А(4) орындарын ауыстырамыз:
А(3)=30 ата-анасы А(8)=4 деген өзінің ұрпағынан үлкен. Сондықтан А(3) пен А(8) орындарын ауыстырамыз. (егер екі ұрпақтың екеуі де кіші болса, ең кіші баласымен орын аыстырамыз).
Екі деңгейдегі А(2)=17 ата-анасы пирамиданың шартн қанағаттандырады. Сондықтан ауыстырулар жүргізілмейді. Ал А(1)=12 өзінің А(3)=4 деген баласынан үлкен болып тұр. Сондықтан олардың орындарын ауыстырамыз:
Осы процесс түбірлік түйінде аяқталады. А(0)=9 ата –анасы өзінің А(1)=4 деген ұрпағымен орын ауысады.
Нәтижелік тармақ осы пирамида болады.