Ustuvor navbatlarni piramida orqali qurish stl da ustuvor navbatlar Piramidaviy saralash

STL da ustuvor navbatlar

C++ ning standart shablonlar kutubxonasida priority_queue shabloni mavjud. Undan foydalanish uchun sarlavha fayli vas td nomlari maydonini qo’shishi lozim.

#include

#include

using namespace std;

int main() {

priority_queue pq;

q.push(1);

q.push(3);

q.push(2);

while (!s.empty()) {

cout << q.top() << ' ';

q.pop();

}

return 0; //natija "3 2 1 "

}

Navbat elementlarini tartiblash kamayish bo’yicha amalga oshiriladi; solishtirish amali sifatida jimlik bo’yicha < operatori qo’llaniladi. Boshqa solishtirish funksiyalarini qo’llash uchun uni navbat konstruktorida uchinchi parameter sifatida (ikkinchi parameter – bazaviy konteyner turi, jimlik bo’yicha vector) keltirish talab qilinadi. Masalan, std::priority_queue< int, std::vector, std::greater > keltirilgan holda, eng yuqori deb minimal prioritet hisoblangan navbatga ega bo’linadi (greater funksional obyekti sarlavha faylida e’lon qilingan).

STL dagi ustuvor navbatlar uchun metodlar to’plami oddiy navbatlar uchun ham deyarli butunlay o’xshash:

		priority_queue()	— konstruktor;
	void	push(const T& x)	— navbatga element qo’shish. Elementning ustuvorligi uning qiymati orqali belgilanadi;
	void	pop()	— maksimal ustunlikdagi elementni o’chirish. E’tibor qarating, o’chirilayotgan element qiymati qaytarilmaydi;
	T&	top()	— maksimal ustunlikdagi element qiymatini olish. Bu metod elementni o’chirishni amalga oshirmaydi;
	bool	empty()	— ustuvor navbatni bo’shlikka tekshirish;
	size_t	size()	— ustuvor navbatning elementlari sonini olish. Metod belgilarsiz butun son qaytaradi.

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.