Heap Sort Algorithm

Uyjumli saralash (Heap Sort) — bu kompyuter dasturlashida keng tarqalgan va juda samarali saralash algoritmidir. Heap sort algoritmini tushunish uchun ikkita asosiy ma'lumot tuzilmasi — massivlar va daraxtlar haqida bilim talab etiladi.

Saralanadigan boshlang'ich sonlar to'plami massivda saqlanadi (masalan, [10, 3, 76, 34, 23, 32]) va saralangandan so'ng [3, 10, 23, 32, 34, 76] ko'rinishiga keladi.

Heap sort massiv elementlarini uyjum (Heap) deb ataluvchi to'liq binar daraxt (complete binary tree) ko'rinishida tasavvur qilish orqali ishlaydi.

[!TIP] Talab: Ushbu mavzuni o'rganishdan oldin To'liq binar daraxt (Complete Binary Tree) va Heap ma'lumotlar tuzilmasi bilan tanishib chiqish juda muhim.

Massiv indekslari va daraxt elementlari o'rtasidagi bog'liqlik

To'liq binar daraxt qiziqarli xususiyatga ega: uning har qanday tugunining bolalari va ota tugunini massiv indekslari orqali matematik ravishda oson topish mumkin.

Agar massivdagi biror elementning indeksi i bo'lsa:

• Uning chap bolasi (left child): 2 * i + 1 indeksda joylashadi.
• Uning o'ng bolasi (right child): 2 * i + 2 indeksda joylashadi.
• Uning ota tuguni (parent): pastki butun qismi olingan (i - 1) / 2 indeksda joylashadi.

Massiv indekslari va uyjum (heap) tugunlari o'rtasidagi bog'liqlik

Buni tekshirib ko'raylik:

1 ning chap bolasi (indeks 0):
= (2 * 0 + 1) indeksdagi element = 1-indeksdagi element = 12

1 ning o'ng bolasi:
= (2 * 0 + 2) indeksdagi element = 2-indeksdagi element = 9

Xuddi shuningdek, 12 ning chap bolasi (indeks 1):
= (2 * 1 + 1) indeksdagi element = 3-indeksdagi element = 5

12 ning o'ng bolasi:
= (2 * 1 + 2) indeksdagi element = 4-indeksdagi element = 6

Uyjum ma'lumotlar tuzilmasi nima?

Uyjum — bu maxsus qoidalarga bo'ysunuvchi to'liq binar daraxtdir:

• Max-Heap (Maksimal uyjum): Har qanday tugunning qiymati uning bola tugunlari qiymatidan katta yoki teng bo'ladi (parent >= children). Demak, ildizdagi element eng katta qiymatga ega.
• Min-Heap (Minimal uyjum): Har qanday tugunning qiymati uning bola tugunlari qiymatidan kichik yoki teng bo'ladi (parent <= children). Demak, ildizdagi element eng kichik qiymatga ega.

Max-Heap va Min-Heap tuzilmalari

Daraxtni qanday qilib uyjumga aylantirish mumkin?

Har qanday ixtiyoriy daraxtni Max-Heap holatiga keltirish jarayoni Heapify deb ataladi.

1. Agar tugunning bolalari bo'lmasa (barg tugun bo'lsa), u avtomatik ravishda uyjum hisoblanadi:

Barg tugunlar uchun Heapify qilish shart emas

2. Agar tugunning bolalari allaqachon Max-Heap bo'lsa, ota tugunni bolalari bilan taqqoslab, eng kattasi bilan o'rnini almashtiramiz:

Ota tugunni eng katta bola bilan almashtirish

3. Agar ildiz element pastga tushganda uning yangi ostki shoxlari ham buzilsa, ushbu jarayon pastga qarab rekursiv davom ettiriladi:

Ildiz element pastga tushirilganda Heapify qayta bajariladi

Build Max-Heap

Max-Heap hosil qilish:

Ixtiyoriy massivdan Max-Heap qurish uchun birinchi barg bo'lmagan tugundan boshlab (indeksi n/2 - 1) ildizgacha (0-indeksgacha) har bir tugun ustida heapify chaqiriladi:

Max-Heap qurish bosqichlari

Quyi tugundan boshlash

Ketma-ket yuqoriga qarab heapify qilish

To'liq Max-Heap qurildi

Uyjumli saralash algoritmining ishlashi

Max-Heap qurilgandan so'ng, eng katta element doimo ildizda (0-indeksda) turadi:

1. Ildizdagi eng katta elementni massivning oxirgi elementi bilan almashtiramiz (swap).
2. Massivning ko'rilayotgan qismini 1 taga qisqartiramiz (oxiriga tushgan eng katta element endi o'z o'rnida).
3. Yangi ildiz element ustida heapify chaqirib, qolgan daraxtni yana Max-Heap holatiga keltiramiz.
4. Bu jarayon daraxtda faqat bitta element qolguniga qadar takrorlanadi.

Uyjumli saralashning to'liq ishlash jarayoni

Dasturiy namunalar

// Go tilida Heap Sort algoritmi
package main

import "fmt"

func heapify(arr []int, n int, i int) {
	largest := i
	left := 2*i + 1
	right := 2*i + 2

	// Chap bola ota tugundan katta bo'lsa
	if left < n && arr[left] > arr[largest] {
		largest = left
	}

	// O'ng bola hozirgi eng kattasidan katta bo'lsa
	if right < n && arr[right] > arr[largest] {
		largest = right
	}

	// Agar eng kattasi ota tugun bo'lmasa, almashtiramiz
	if largest != i {
		arr[i], arr[largest] = arr[largest], arr[i]
		// Buzilgan ostki daraxtni qayta heapify qilamiz
		heapify(arr, n, largest)
	}
}

func heapSort(arr []int) {
	n := len(arr)

	// 1-qadam: Max-Heap qurish
	for i := n/2 - 1; i >= 0; i-- {
		heapify(arr, n, i)
	}

	// 2-qadam: Elementlarni bittalab ajratib olib saralash
	for i := n - 1; i > 0; i-- {
		// Ildizni oxirgi element bilan almashtirish
		arr[0], arr[i] = arr[i], arr[0]

		// Qisqargan heap ustida heapify chaqirish
		heapify(arr, i, 0)
	}
}

func main() {
	data := []int{1, 12, 9, 5, 6, 10}
	fmt.Println("Dastlabki massiv:", data)

	heapSort(data)

	fmt.Println("Saralangan massiv:", data)
}

Uyjumli saralashning murakkabligi

Vaqt murakkabligi

• Barcha holatlarda (Best, Worst, Average): O(n log n)
  • Daraxt balandligi log n bo'lgani sababli, bitta element ustida heapify bajarish O(log n) vaqt oladi.
  • Barcha n ta element uchun bu amal bajarilganda, umumiy vaqt kafolatlangan O(n log n) bo'ladi.

Xotira murakkabligi

• Xotira murakkabligi O(1) ga teng, chunki saralash massivning o'zida amalga oshiriladi (in-place).
• Heap sort beqaror (unstable) saralash algoritmidir.

Uyjumli saralashning qo'llanilishi

• Xotira o'ta cheklangan va kafolatlangan O(n log n) tezlik talab qilinadigan tizimlarda (Quicksortning O(n^2) yomon holatidan va Merge sortning O(n) xotira sarfidan xalos bo'lish uchun).
• Prioritetli navbat (Priority Queue) tuzilmalarini amalga oshirishda.