Priority Queue

Prioritetli navbat (Priority queue) — bu har bir elementga uning ustuvorlik darajasi (priority value) biriktirilgan maxsus turdagi navbatdir. Elementlarga ularning ustuvorligi asosida xizmat ko'rsatiladi. Ya'ni, yuqoriroq ustuvorlikka ega bo'lgan elementlarga birinchi bo'lib xizmat ko'rsatiladi.

Biroq, agar ustuvorlik darajasi bir xil bo'lgan elementlar kelsa, ularga navbatdagi kelish tartibiga ko'ra xizmat ko'rsatiladi.

Assigning Priority Value

Ustuvorlik qiymatini belgilash:

Odatda, ustuvorlikni belgilash uchun elementning o'z qiymati hisobga olinadi. Masalan:

• Eng katta qiymatga ega element eng yuqori ustuvorlikka ega element deb hisoblanishi mumkin.
• Boshqa hollarda esa eng kichik qiymatga ega element eng yuqori ustuvorlikka ega deb qabul qilinishi mumkin.
• Shuningdek, ehtiyojga qarab ustuvorliklarni ixtiyoriy mezonlar asosida ham belgilashimiz mumkin.

Prioritetli navbat va Oddiy navbat o'rtasidagi farq

Oddiy navbatda birinchi kirgan birinchi chiqadi (FIFO — First In First Out) qoidasi amal qiladi. Prioritetli navbatda esa elementlar ularning ustuvorligi asosida navbatdan chiqariladi. Eng yuqori ustuvorlikka ega element birinchi bo'lib o'chiriladi.

Prioritetli navbatni amalga oshirish

Prioritetli navbatni massiv (array), bog'langan ro'yxat (linked list), to'p (heap) ma'lumotlar tuzilmasi yoki ikkilik qidiruv daraxti (binary search tree) yordamida amalga oshirish mumkin. Ushbu ma'lumotlar tuzilmalari orasida to'p (heap) ma'lumotlar tuzilmasi prioritetli navbatni eng samarali tarzda amalga oshirish imkonini beradi.

Shu sababli, ushbu darsda prioritetli navbatni yaratish uchun to'p (heap) ma'lumotlar tuzilmasidan foydalanamiz. Quyidagi amallarda max-heap (maksimal to'p) qo'llaniladi. Agar bu haqida batafsil ma'lumot olmoqchi bo'lsangiz, max-heap va min-heap bo'limiga qarang.

Prioritetli navbatning turli usullarda amalga oshirilishining taqqoslama tahlili quyidagicha:

Prioritetli navbat amallari

Prioritetli navbatning asosiy amallari: element qo'shish (inserting), o'chirish (removing) va elementni ko'rish (peeking).

Prioritetli navbatni o'rganishdan oldin ikkilik to'p qanday ishlashini yaxshiroq tushunish uchun heap data structure darsini ko'rib chiqishingiz tavsiya etiladi.

1. Insert

Element qo'shish (Insert):

Prioritetli navbatga (max-heap) element qo'shish quyidagi bosqichlarda bajariladi:

1. Yangi elementni daraxtning oxiriga qo'shish.

2. Daraxtni Heapify qilish (to'p xossasini qayta tiklash).

Prioritetli navbatga (max-heap) element qo'shish algoritmi:

Agar hech qanday tugun bo'lmasa,
  yangiTugun (newNode) yaratish.
aks holda (tugun allaqachon mavjud bo'lsa)
  yangiTugunni oxiriga qo'shish (chapdan o'ngga eng oxirgi tugun).

massivni heapify qilish (to'p xossasini qayta tiklash)

Min Heap uchun yuqoridagi algoritm o'zgartiriladi: bunda ota tugun (parentNode) har doim yangi tugun (newNode)dan kichik bo'lishi ta'minlanadi.

2. Delete

Element o'chirish (Delete):

Prioritetli navbatdan (max-heap) elementni o'chirish quyidagi bosqichlarda bajariladi:

1. O'chirilishi kerak bo'lgan elementni tanlash.

2. Uni eng oxirgi barg tugun elementi bilan almashtirish (swap).

3. Oxirgi barg elementni o'chirish (olib tashlash).

4. Daraxtni heapify qilish.

Prioritetli navbatdan (max-heap) element o'chirish algoritmi:

Agar o'chiriladiganTugun bargTugun (leafNode) bo'lsa
  tugunni o'chirish
aks holda o'chiriladiganTugunni oxirgiBargTugun (lastLeafNode) bilan almashtirish
  o'chiriladiganTugunni o'chirish

massivni heapify qilish

Min Heap uchun yuqoridagi algoritm o'zgartiriladi: bunda har ikkala bola tugunlar (childNodes) ham joriy tugun (currentNode)dan katta bo'lishi ta'minlanadi.

3. Peek

Elementni ko'rish (Peek):

Peek amali tugunni o'chirmasdan turib, Max Heap dan maksimal elementni yoki Min Heap dan minimal elementni qaytaradi.

Max Heap va Min Heap ning ikkalasi uchun ham:

ildizTugunni (rootNode) qaytarish

4. Extract-Max/Min amali

Extract-Max amali Max Heap dan maksimal qiymatli tugunni o'chirib, o'sha qiymatni qaytaradi. Extract-Min amali esa Min Heap dan minimal qiymatli tugunni o'chirib, o'sha qiymatni qaytaradi.

Prioritetli navbatning Go, Python, Java, C va C++ tillaridagi dasturiy kodi

// Priority Queue implementation in Go
package main

import "fmt"

// Daraxtni to'p (heap) holatiga keltirish funksiyasi
func heapify(arr *[]int, n int, i int) {
	largest := i
	l := 2*i + 1
	r := 2*i + 2

	if l < n && (*arr)[l] > (*arr)[largest] {
		largest = l
	}
	if r < n && (*arr)[r] > (*arr)[largest] {
		largest = r
	}

	// Agar ildiz eng kattasi bo'lmasa, almashtiramiz va heapify qilishni davom ettiramiz
	if largest != i {
		(*arr)[i], (*arr)[largest] = (*arr)[largest], (*arr)[i]
		heapify(arr, n, largest)
	}
}

// Daraxtga yangi element qo'shish funksiyasi
func insert(arr *[]int, newNum int) {
	*arr = append(*arr, newNum)
	size := len(*arr)
	for i := size/2 - 1; i >= 0; i-- {
		heapify(arr, size, i)
	}
}

// Daraxtdan elementni o'chirish funksiyasi
func deleteNode(arr *[]int, num int) {
	size := len(*arr)
	i := 0
	for i = 0; i < size; i++ {
		if num == (*arr)[i] {
			break
		}
	}
	if i == size {
		return
	}

	(*arr)[i], (*arr)[size-1] = (*arr)[size-1], (*arr)[i]
	*arr = (*arr)[:size-1]

	for j := len(*arr)/2 - 1; j >= 0; j-- {
		heapify(arr, len(*arr), j)
	}
}

// Massivni chop etish funksiyasi
func printArray(arr []int) {
	for _, val := range arr {
		fmt.Printf("%d ", val)
	}
	fmt.Println()
}

func main() {
	var arr []int
	insert(&arr, 3)
	insert(&arr, 4)
	insert(&arr, 9)
	insert(&arr, 5)
	insert(&arr, 2)

	fmt.Print("Max-Heap array: ")
	printArray(arr)

	deleteNode(&arr, 4)
	fmt.Print("After deleting an element: ")
	printArray(arr)
}

Prioritetli navbatning qo'llanilishi

Prioritetli navbat quyidagi sohalarda keng qo'llaniladi:

• Dijkstra algoritmida (eng qisqa yo'lni topish)
• Stack ma'lumotlar tuzilmasini amalga oshirishda
• Operatsion tizimlarda yuklamani taqsimlash (load balancing) va uzilishlarni qayta ishlash (interrupt handling) uchun
• Huffman kodlash orqali ma'lumotlarni siqish (data compression) algoritmlarida
• Heap sort (To'p saralash) algoritmida