«Мәліметтерді өңдеудің құрылымдары мен алгоритмдері»
жүктеу/скачать 1,51 Mb.
|
- Бұл бет үшін навигация:
- Пирамида
- Массивті пирамидаѓа т‰рлендіру
- Пирамидаға элемент қосу 1.
Дәріс 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 деген ұрпағымен орын ауысады. 
Нәтижелік тармақ осы пирамида болады. Пирамидаға элемент қосу 1. Жаңа элемент тізімнің соңынан қосылады: 
2. Егер жаңа элемент өзінің ата-анасына қарағанда кіші мәнге ие болса, онда түйіннің орнын ауыстырамыз. 
3. Жаңа ата-ана бала ретінде қарастырылады да одан да ата-ана үшін пирамидада шарт тексеріледі. 
4. Осы процесс ата-ананың жолын қайталап, жаңа элементтен кіші ата-ананы кезіктіргенде немесе түбірлі түйінге келгенде тоқтайды. Элементтерді пирамидадан өшіру Мәліметтер қанашанда тармақтың түбірінен өшіріледі. 
Түбірлік түйінді өшіріп, оны соңғы түйінмен алмастыру. Егер жаңа түбірлік түйін өзінің ұрпақтарының кез келгенінен үлкен болса, онда оны өзінің кіші ұрпақтарымен орын ауыстыру керек.  
3. Кіші ұрпақтар бойынша жүргізілетін осы жол элемент ата-ана ретінде дұрыс позицияға келгенше немесе тізімнің соңына жеткенше далғасады. жүктеу/скачать 1,51 Mb. Достарыңызбен бөлісу:
|
