Heap Data Structure

To'p (Heap) ma'lumotlar tuzilmasi — to'p xossasini (heap property) qanoatlantiruvchi to'liq ikkilik daraxt (complete binary tree) hisoblanadi. Unda ixtiyoriy tugun:

• har doim o'zining bola tugun(lar)idan katta bo'ladi va ildiz tugunning kaliti barcha tugunlar orasida eng kattasi hisoblanadi. Bu xossa maksimal to'p xossasi (max-heap property) deb ataladi.
• har doim o'zining bola tugun(lar)idan kichik bo'ladi va ildiz tugunning kaliti barcha tugunlar orasida eng kichigi hisoblanadi. Bu xossa minimal to'p xossasi (min-heap property) deb ataladi.

Maksimal to'p (Max-heap)

Minimal to'p (Min-heap)

Ushbu turdagi ma'lumotlar tuzilmasi ikkilik to'p (binary heap) deb ham yuritiladi.

To'p amallari

Quyida to'p ustida bajariladigan asosiy amallar va ularning algoritmlari keltirilgan.

Heapify

Heapify — ikkilik daraxtdan to'p ma'lumotlar tuzilmasini yaratish yoki to'p xossasini qayta tiklash jarayonidir. U Min-Heap yoki Max-Heap hosil qilish uchun ishlatiladi.

1. Kirish massivi quyidagicha berilgan bo'lsin:

Boshlang'ich massiv

2. Massiv elementlaridan to'liq ikkilik daraxt (complete binary tree) quramiz:

To'liq ikkilik daraxt

3. Barg bo'lmagan birinchi tugundan boshlaymiz; uning indeksi n/2 - 1 formula orqali topiladi:

Barg bo'lmagan birinchi tugundan boshlash

4. Joriy element indeksini i eng katta (largest) deb belgilaymiz.
5. Chap bolaning indeksi 2i + 1, o'ng bolaning indeksi esa 2i + 2 formula orqali topiladi:
   • Agar leftChild joriy elementdan (array[i]) katta bo'lsa, leftChildIndexni largest deb belgilaymiz.
   • Agar rightChild array[largest] elementidan katta bo'lsa, rightChildIndexni largest deb belgilaymiz.
6. largest bilan joriy elementni almashtiramiz (swap):

Zarur bo'lsa elementlarni almashtirish (swap)

7. Quyi daraxtlar ham to'p xossasiga keltirilgunga qadar 3–7 bosqichlarni takrorlaymiz.

Heapify algoritmi

Heapify(array, size, i)
  set i as largest
  leftChild = 2i + 1
  rightChild = 2i + 2
  
  if leftChild < size and array[leftChild] > array[largest]
    set leftChild as largest
  if rightChild < size and array[rightChild] > array[largest]
    set rightChild as largest

  if largest != i
    swap array[i] and array[largest]
    Heapify(array, size, largest)

Max-Heap yaratish uchun:

MaxHeap(array, size)
  loop from the first index of non-leaf node (size/2 - 1) down to zero
    call Heapify(array, size, i)

Min-Heap uchun esa barcha tugunlarda chap va o'ng bola ota tugundan katta bo'lishi talab etiladi.

To'pga element qo'shish

Max-Heap ga yangi element qo'shish algoritmi:

Agar to'pda tugun bo'lmasa:
  newNode yarating.
Aks holda (tugunlar mavjud bo'lsa):
  newNode ni daraxtning oxiriga (chapdan o'ngga eng oxirgi barg qilib) joylashtiring.
  
massivni to'p xossasiga keltiring (heapify).

Bosqichlar:

1. Yangi elementni daraxtning oxiriga qo'shing:

Elementni oxiriga qo'shish

2. Daraxtni heapify qiling (to'p xossasini tiklang):

Massivni heapify qilish

Min-Heap uchun ushbu algoritm ota tugun doimo yangi qo'shilgan tugundan kichik bo'lishini ta'minlash sharti bilan moslashtiriladi.

To'pdan element o'chirish

Max-Heap dan element o'chirish algoritmi:

Agar nodeToBeDeleted oxirgi barg tugun bo'lsa:
  tugunni o'chiring
Aks holda:
  nodeToBeDeleted ni eng oxirgi barg tugun (lastLeafNode) bilan almashtiring
  nodeToBeDeleted ni o'chiring
  
massivni heapify qiling

Bosqichlar:

1. O'chirilishi kerak bo'lgan elementni tanlang:

O'chirilishi kerak bo'lgan elementni tanlash

2. Uni eng oxirgi element bilan almashtiring (swap):

Oxirgi element bilan almashtirish

3. Oxirgi elementni olib tashlang:

Oxirgi elementni olib tashlash

4. Daraxtni to'p xossasiga keltirish uchun heapify qiling:

Massivni heapify qilish

Min-Heap uchun ushbu algoritm har ikkala bola tugun joriy tugundan katta bo'lishini ta'minlash sharti bilan moslashtiriladi.

Ko'rish — Peek

Peek amali Max-Heap dan maksimal elementni yoki Min-Heap dan minimal elementni daraxtdan o'chirmasdan qaytaradi.

Max-Heap va Min-Heap uchun:

return rootNode

Massiv ko'rinishidagi to'pda ildiz har doim 0-indeksda bo'lgani sababli, u array[0] qiymatini qaytaradi va bu O(1) vaqt oladi.

Extract-Max/Min amali

Extract-Max amali Max-Heap dan eng katta qiymatga ega tugunni (ildizni) o'chirib, uning qiymatini qaytaradi. Extract-Min amali esa Min-Heap dan eng kichik qiymatga ega tugunni (ildizni) o'chirib, uning qiymatini qaytaradi. Ildiz olib tashlangach, to'p xossasini tiklash uchun heapify bajariladi (O(log n)).

Dasturiy namunalar: Go, Python, Java, C va C++

// Go tilida Max-Heap ma'lumotlar tuzilmasi
package main

import "fmt"

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
	}

	if largest != i {
		arr[i], arr[largest] = arr[largest], arr[i]
		heapify(arr, n, largest)
	}
}

func insert(arr *[]int, newNum int) {
	*arr = append(*arr, newNum)
	current := len(*arr) - 1

	// Bubble up - yuqoriga ko'tarish
	for current > 0 {
		parent := (current - 1) / 2
		if (*arr)[current] > (*arr)[parent] {
			(*arr)[current], (*arr)[parent] = (*arr)[parent], (*arr)[current]
			current = parent
		} else {
			break
		}
	}
}

func deleteNode(arr *[]int, num int) {
	size := len(*arr)
	i := 0
	for i = 0; i < size; i++ {
		if (*arr)[i] == num {
			break
		}
	}
	if i == size {
		return
	}

	// Oxirgi element bilan almashtirish
	(*arr)[i], (*arr)[size-1] = (*arr)[size-1], (*arr)[i]
	*arr = (*arr)[:size-1]
	size = len(*arr)

	// Joriy indeksdan boshlab heapify qilish
	if i < size {
		heapify(*arr, size, i)
	}
}

func printArray(arr []int) {
	for _, num := range arr {
		fmt.Printf("%d ", num)
	}
	fmt.Println()
}

func main() {
	var heapTree []int

	insert(&heapTree, 3)
	insert(&heapTree, 4)
	insert(&heapTree, 9)
	insert(&heapTree, 5)
	insert(&heapTree, 2)

	fmt.Print("Max-Heap massivi: ")
	printArray(heapTree)

	deleteNode(&heapTree, 4)
	fmt.Print("Element o'chirilgandan so'ng: ")
	printArray(heapTree)
}

To'p ma'lumotlar tuzilmasining qo'llanilishi

• Prioritetli navbat (Priority Queue) — prioritetli navbatni samarali amalga oshirishda to'pdan keng foydalaniladi.
• Dijkstra algoritmi — grafda manbadan barcha tugunlargacha bo'lgan eng qisqa yo'lni topish algoritmi.
• Heap Sort (To'p usulida saralash) — O(n log n) vaqt murakkabligiga ega bo'lgan samarali saralash algoritmi.