|
Referat bajardi: 739-22 guruh talabasi Axmedov Izzatilla Qabul qildi: farg’ona-2024
|
| bet | 4/7 | | Sana | 13.06.2024 | | Hajmi | 208,96 Kb. | | #263487 | | Turi | Referat |
Bog'liq 1. Stack. queue.priority queue.O’chirish operatsiyasi
Maksimal ustuvor elementni o’chirish kabi amalga oshiriladi
Uni oxirgi element bilan almashtiring.
Oxirgi elementni o'chiring.
Heapify Again, ya’ni yangi daraxtni uyumga aylantirish.
Yuqori operatsiya
Maksimal ustuvor element rootNode sifatida mavjud bo’ladi. Shunday qilib, rootNode-ni qaytaring.
Pseudo kod
// arr will store the element’s of the priority queue
void heapify(int arr[], int size, int i)
{
largest = i
leftChild = 2*I + 1
rightChild = 2*I + 1
if( leftChild < size and arr[i] < arr[leftChild])
largest = leftChild
if( rightChild < size and arr[largest] < arr[rightChild])
largest = rightChild
if( largest != i)
{
swap(arr[i],arr[largest])
heapify(arr,n,largest)
}
}
// This will return the size of the priority queue
int enqueue(int arr[], int size, int num) {
if(size == 0) {
arr.append(num)
}
else {
arr.append(num);
for ( I = size/2-1 to 0 )
heapify(arr,size,i)
}
return size + 1
}
// This will return the size of the priority queue
int dequeue(int arr[], int size)
{
swap(arr[0],arr[size-1])
size = size - 1 // decreasing the size
for( I = size/2 -1 to 0 )
heapify(arr,size,i)
}
// return top priority element
int top(){
return arr[0]
}
Priority Queue ilovalari
CPU rejalashtirish
Voqealarga asoslangan simulyatsiya.
Aida A* qidiruv algoritmi.
Huffman kodlash yordamida ma’lumotlarni siqish.
Statistika (ketma-ketlikda eng katta M qiymatlarini saqlang).
Uyda yechish uchun tavsiya etilgan muammolar
K eng kichik summali juftliklar
Sürgülü oyna maksimal
K tartiblangan roʻyxatini birlashtirish
Minimal to'pni maksimal to'pga aylantiring
Baxtli kodlash! Algoritmlardan zavqlaning.
Ack va navbat o’rtasidagi farq
Stack va Queue ma'lumotlar tuzilmalari o'rtasidagi asosiy farq shundaki, Stack LIFO ga, navbat esa FIFO ma'lumotlar strukturasi turiga amal qiladi. LIFO oxirgi kiruvchi birinchi chiqishni bildiradi. Bu shuni anglatadiki, biz ma'lumotlarni Stackga qo'yganimizda, u birinchi navbatda oxirgi yozuvni qayta ishlaydi. Aksincha, FIFO birinchi kiruvchi birinchi chiqadi degan ma'noni anglatadi. Bu shuni anglatadiki, biz ma'lumotlarni Navbatga qo'yganimizda, u birinchi bo'lib birinchi yozuvni qayta ishlaydi. Keling, ular orasidagi farqni batafsilroq tushunaylik.
Stack Data Strukturasi nima?
Stack-ga ma’lumotlar strukturasining chiziqli shakli sifatida murojaat qilishingiz mumkin. Bunda foydalanuvchi roʻyxatning faqat bir tomonidagi elementlarni oʻchirishi va kiritishi mumkin. U yuqori deb nomlanadi . Ma’lumotlar stek tuzilmasi “Oxirgi kirish, birinchi chiqish” (LIFO) tamoyiliga amal qiladi va unga amal qiladi. Bu oxirgi kiritilgan element birinchi bo'lib chiqishini bildiradi.
Elementni stekga kiritish jarayoni surish operatsiyasi deb nomlanadi. Bu erda elementlarni o’chirish pop operatsiyasi sifatida tanilgan. Foydalanuvchi ko’rsatgich (yuqori) yordamida stekdagi ro’yxatning oxirgi funksiyasi/elementini kuzatishi mumkin.
Navbatdagi ma’lumotlar tuzilmasi nima?
Navbatga ma’lumotlar strukturasining chiziqli shakli sifatida ham murojaat qilishingiz mumkin. Bunda foydalanuvchi ro’yxatning faqat bir tomonidagi elementlarni kiritishi mumkin. U orqa tomon sifatida tanilgan. Bundan tashqari, ushbu elementlarni boshqa tomondan o’chirish mumkin – old tomondan. Ushbu turdagi ma’lumotlar strukturasi birinchi kir, birinchi chiqadi (FIFO) tamoyilini amalga oshiradi va unga amal qiladi. Bu ro’yxatga kiritilgan birinchi element birinchi bo’lib chiqishini anglatadi.
Elementni navbatga kiritish jarayoni navbat operatsiyasi deb nomlanadi. Bu erda elementni o’chirish jarayoni dequeue operatsiyasi deb nomlanadi. Foydalanuvchi har doim ikkita ko’rsatgichni navbatda ushlab turishi mumkin. Old ko’rsatgich hali ham ro’yxatda bo’lgan birinchi kiritilgan elementga ishora qiladi. Ikkinchi ko’rsatkich ro’yxatdagi oxirgi kiritilgan elementga ishora qiluvchi orqa tomondir.
|
| |
