Пирамидалық сұрыптау

Презентация қосу

М.Өтемісов атындағы Батыс Қазақстан Университеті

Пирамидалық
сұрыптау

Орындаған:Қанат Ә.Қ
Тексерген :Оқытушы ,магистр Дошев
Г. А.
Пирамидалық
сұрыптау
Пирамидалық әдісті ,Джон Уильямс 1964
жылы ұсынған, содан кейін Роберт Флойд
жетілдірген.Бұл сұрыптауды
жақсартудағы идея O (N) күрделілігі бар
сызықтық таңдаудан ағаштағы
сұрыптауға ауысу болып табылады, оның
көмегімен таңдау процесі туралы көбірек
ақпаратты сақтауға және пайдалануға
және күрделілікті O (log2N) дейін
төмендетуге болады.
Түсініктеме. Жоғарыда көрсетілген
күрделіліктің бағалары тұтастай алғанда
бүкіл сұрыптауға қолданылмайды , тек
оның бір кезеңіне массивтің қандай да
Пирамидалық әдіске
мысал
Алдымен спорт түрлерін
қарастырайық. Сегіз қатысушы арасында
жарыс спорттың қандай-да бір түрінен
(шахмат, теннис және т.б.) өткізіледі
Қатысушылардың әрқайсысы бәрімен
кездескен кезде чемпионатты өткізуге
болады , бірақ бұл уақытты қажет
етеді .Кубок жүйесіндегі жарыстарды
ұйымдастырудың қарапайым және
жылдам тәсілі бар. Қатысушылар қандай
да бір қағида бойынша жұптарға
Пирамдалық
Пирамидалық ағаш
ағаш – бұл кез-
келген кіші ағаштың түбірінің кілті
оның екі шыңының пернелерінен
үлкенірек толық екілік ағаш .
Р.Флойд ұсынған ағаштан таңдау
арқылы сұрыптауды тиімді жүзеге
асыру әдетте үйінді ағаш немесе
жай үйінді деп аталатын екілік
ағаштың ерекше түріне
негізделген Бұл ағаш кейде
сұрыптау ағашы деп аталады
Пирамидалық ағаш
Пирамида -(Үйме) – бұл келесі
талаптарды қанағаттандыратын k
биіктіктегі екілік ағаш :
«Пирамида қасиеті»
орындалады:
1 әр элемент ата-анадан кіші
немесе оған тең
,2 ағаштың тамыры -
массивтің максималды Мысал тереңдігі 4
үйіндіден
элементі
Пирамидалық ағаш
Пирамиданы бейнелеу үшін сізге арнайы
мәліметтер құрылымын құрудың қажеті
жоқ - оны сұрыптау үшін тікелей
массивте сақтауға болады

► ағаштың түбірі [0] -де, a [i]
элементінің сол және оң жақ
сәйкесінше
[2i + 1] және a [2i + 2] -де
сақталады. Мұнда n жиымы
берілген нөмірлеу 0-ден n-1-ге
дейінгі элементтер
Пирамидалық
ағаш

70 Түбірінің кілті оның 65 және 60
түйіндерінің пернелерінен үлкен. 65 сол
жақ кіші ағаштың кілті 28 және 45
пернелерінен, сондай-ақ оң жақ 60
ағашы балаларының 54 және 43
пернелерінен үлкенірек.Бейнеленген
ағаш үйінді болып табылады Кему реті
бойынша сұрыптау үшін кез-келген кіші
Назарларыңызға
рахмет!

Ұқсас жұмыстар

Массивтерді сұрыптау!

Бір өлшемді массивтерді сұрыптау

Массивтерді сұраптау әдістері

ЖЫЛДАМ СҰРЫПТАУ АЛГОРИТМІ

Жоғары жүйке әрекеті және оның баланың өсіп - дамуы барысында қалыптасуы

Дөңгелек диаграмма

Жүйке жүйесінің морфологиялық субстраты рефлекторлық доға

Маңдай үлесіндегі қыртыста орналасқан, функциональды орталықтар

Платиналық пирамида

Жүйке жүйесінің гистогенезі

Пәндер