Toshkent Davlat Iqtisodiyot Universiteti To’rtkul fakulteti

Ustuvor navbatlarni piramida orqali qurish

O’chirishni esa quyidagicha amalga oshirish mumkin: piramidaning yuqorisiga uning eng oxirgi elementini joylashtirish va u uchun down() amalini bajarish. O’chirishning murakkabligi O(logN) ga teng.
int dequeue() {
if (size == 0)
/* hatolikni qayta ishlash – yechib olish uchun element mavjud emas */
swap(a[0], a[--size]);
down(0);
return a[size];
}

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.
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

		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 dagi ustuvor navbatlar uchun metodlar to’plami oddiy navbatlar uchun ham deyarli butunlay o’xshash: