Toshkent Davlat Iqtisodiyot Universiteti To’rtkul fakulteti

STL

STL da ustuvor navbatlar tasodifiy kirishli (vector yoki deque) ketma-ket konteyner shabloniga asoslangan va ichki strukturani qo’llab-quvvatlash uchun sarlavha faylida belgilangan piramidalar bilan ishlash protseduralaridan foydalanadi.

Ularning har biri elementlar diapazonini ko’rsatuchi (qoidaga asosan bu konteynerdagi barcha elementlarni o’z ichiga olgan begin() va end() ) It ga mustaqil kirishga ega juft iteratorlarni qabul qiladi.

Jimlik bo’yicha barcha protseduralarda solishtirish uchun <; operatori qo’llaniladi, xususiy funksional obyektni uchinchi parameter qilib berish mumkin.

	void	make_heap(It first, It last)	— piramidani [first, last) elementlar diapazonida yaratish;
	void	push_heap(It first, It last)	— element qo’shish, [fist,last-1) piramidaga lastdan oldingi elementni qo’shish, shunday qilib [fist,last) ning butun diapazoni piramidaga aylanadi
	void	pop_heap(It first, It last)	— maksimal ustunlikdagi elementni (boshidan first ko’rsatayotgan) oxirga ko’chirib o’tirish va piramidani qolgan elementlardan [first, last-1) diapazonida tashkil qilish;
	void	sort_heap(It first, It last)	— [first,last) piramidani tartiblangan intervalda tashkil qilish. Protsedura chaqirilgandan so’ng diapazon piramida bo’lmay qoladi.

Piramidaviy saralash

• Piramidaviy saralash (ing. heapsort) – tanlash orqali saralashning takomillashtirilgan varsiyasi. Oddiy tanlash orqali saralash N marta berilgan massivdan kichik element yechib olinadi va munosib joyga joylashtirilishga asoslangan. Agar kichik elementni tanlash uchun ketma-ket qidirishdan foydalanilsa, u holda har safar butun massiv ko’rib chiqiladi. Bu esa har bir iteratsiyaga O(N) murakkablik beradi va umumiy murakkablik O(N2) ga teng bo’ladi.
• Kichik elementni izlashda ketma-ket qidiruv o’rniga piramidadan foydalanish mumkin, u har bir qadamda minimal elementni O(1) bilan yechib olishni va O(logN) bilan qayta tiklanishni beradi. Bundan kelib chiqadiki, umumiy murakkablik O(NlogN) ga teng bo’ladi. Piramidaning aralashtirmaslik uchun o’zini har bir qadamda maksimal elementni yechib olib va uni oxiriga qo’shish mumkin. Piramidani berilgan bo’sh bo’lmagan massivda hosil qilishni ikkita usuli mavjud

Piramidaviy saralash

Piramidaviy saralashning xususiyatlari:

• Murakkablik O(NlogN);
• Tanlash orqali saralash kabi qo’shimcha hotira talab qilmaydi, misol uchun surish orqali saralashdan farqli ravishta;
• Tanlash orqali saralash kabi barqaror emas (masalan, sonlar kalit hisoblangan [1-a,1-b] massiv, saralashdan so’ng [1-b,1-a] ko’rinishiga ega bo’ladi);
• Tanlash orqali saralash kabi moslashuvchan emas.