Пирамидалық сұрыптау: үйінді құрылымы, алгоритм және күрделілік талдауы

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

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

Орындаған:Қанат Ә. Қ

Тексерген :Оқытушы, магистр Дошева Г. А.

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

Пирамидалық әдісті, Джон Уильямс 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 пернелерінен үлкенірек. Бейнеленген ағаш үйінді болып табылады Кему реті бойынша сұрыптау үшін кез-келген кіші ағаштың түбірінің кілті оның кіші болатын үйместің тағы бір нұсқасы қолданылады.