Ustuvor navbatlarni piramida orqali qurish stl da ustuvor navbatlar Piramidaviy saralash

Laboratoriya mashg’uloti №6. Piramida ustida bajariladigan amallar.

Reja:

1. 
   Ustuvor navbatlarni piramida orqali qurish
   
2. 
   STL da ustuvor navbatlar
   
3. 
   Piramidaviy saralash
   

Nazariy qism

Ustuvor navbatlarni piramida orqali qurish

Piramidaning muhim jihatlaridan biri bu, unda saqlanayotgan qiymatlarning maksimali uning tepasida joylashgan bo’ladi. Yuqorida keltirilgan faktlar bilan, ya’ni piramidani qayta tiklashning up() va down() amallari keltirilgandek piramidaning balandligidan oshmaydigan almashtirishlarni amalga oshiradi, bu esa ustuvor navbatlarni samarali qo’llashga imkon beradi.

Eng avvalo, bu qo’llash elementni tuzilmasini (chunki element faqat prioritetni emas balki qiymatni ham saqlaydi) tavsiflashni va piramida shakllantiriladigan massivni e’lon qilishni talab qiladi. Piramidani qayta tiklash amallari .priority maydonini solishtirishi lozim. Navbatning elementlari sonini saqlash uchun alohida size o’zgaruvchisi ajratiladi, konstruktorda unga 0 qiymati o’zlashtiriladi.

static const int MAX_SIZE = 100;

struct Elem {

int val;

int priority;

Elem(int v = 0, int p = 0) {

val = v;

priority = p;

}

} a[MAX_SIZE];

int size;

Element qo’shish a[size] yacheykasida amalga oshiriladi. Chunki qo’shish amalga oshirilgandan so’ng piramidaning asosiy xususiyati buzilishi mumkin, shuning uchun qo’shimcha ravishta up() protsedurasini chaqirish talab etiladi. Qo’shish amalining umumiy murakkabligi O(logN) ga teng.

void enqueue(int value, int priority) {

if (size + 1 == MAX_SIZE)

/* navbatni to’ldirishdagi hatolikni qayta ishlash */

a[size++] = Elem(value, priority);

up(size - 1);

}

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];

}

Quyida ustuvor navbatning qo’llanilishi bo’yicha to’liq kod keltirilgan. Navbat elementlarining to’lib ketishi yoki bo’sh navbatdan element yechib olishga urunishlar assert konstruksiyasi bilan beriladi (sarlavha fayli yoki ).

class PriorityQueue {
static const int MAX_SIZE = 100;

struct Elem {

int val;

int priority;

Elem(int v = 0, int p = 0) {

val = v;

priority = p;

}

} a[MAX_SIZE];

int size;
void up(int i) {

while (i != 0 && a[i].priority > a[(i - 1) / 2].priority) {

swap(a[i], a[(i - 1) / 2]);

i = (i - 1) / 2;

}

}
void down(int i) {

while (i < size / 2) {

int maxI = 2 * i + 1;

if (2 * i + 2 < size && a[2 * i + 2].priority > a[2 * i + 1].priority)

maxI = 2 * i + 2;

if (a[i].priority >= a[maxI].priority)

return;

swap(a[i], a[maxI]);

i = maxI;

}

}
public:

PriorityQueue() {

size = 0;

}
void enqueue(int value, int priority) {

assert(size + 1 < MAX_SIZE);

a[size++] = Elem(value, priority);

up(size - 1);

}
int dequeue() {

assert(size > 0);

swap(a[0], a[--size]);

down(0);

return a[size];

}
bool isEmpty() {

return size == 0;

}

};

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.

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(N²) 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:

• 
  Boshidan oxirigacha ko’rib chiqib, ketma-ket ravishta har bir element uchun up() (odatda ustuvor navbatni massivning har bir elementiga enqueue() amalini qo’llagan holda qurishga o’xshash) amalini qo’llab. Murakkablik O(NlogN);
  
• 
  Piramidani “pastdan yuqoriga” tarzida qurish, down() protsedurasini barcha element uchun chaqirgan holda massivning oxiridan boshigacha ko’rib chiqib. down() ni yaproqlar uchun chaqirish hech qanday o’zgarishga olib kelmaydi, shuning uchun siklni (size/2-1) dan boshlasa ham bo’ladi. Bir qancha manbalarda, shuningdek T. Kormenning “Алгоритмы: построение и анализ” kitobida ham ushbu metodning murakkabligi O(N) gacha kamayishi ko’rsatilgan.
  

down() funksiyasi unga parametrlar orqali berilgan a[] va size qiymatlaridan foydalansin. U holda piramidaviy saralash quyidagi ko’rinishga ega bo’ladi:

void heapsort(int a[], int size) {

for (int i = size / 2 - 1; i >= 0; i--)

down(a, size, i);

for (int i = 0; i < size; i++) {

swap(a[0], a[size - 1 - i];

down(a, size - i, 0);

}

}

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.