Brodala-Okasaki uyumi
![Heapsortning afzalliklari:
Samaradorlik - Uyma tartibini bajarish uchun zarur bo'lgan vaqt
logarifmik ravishda oshadi, boshqa algoritmlar esa saralanadigan elementlar
soni ortishi bilan eksponent ravishda sekinlashishi mumkin. Ushbu tartiblash
algoritmi juda samarali.
Xotiradan foydalanish - Xotiradan foydalanish minimal, chunki
saralanadigan elementlarning dastlabki ro'yxatini saqlash uchun zarur bo'lgan
narsalardan tashqari, ishlash uchun qo'shimcha xotira maydoni kerak emas.
Oddiylik - Boshqa teng darajada samarali tartiblash algoritmlariga
qaraganda tushunish osonroq, chunki u rekursiya kabi ilg'or informatika
tushunchalaridan foydalanmaydi.
Uyma tartiblashning kamchiliklari:
Qimmatli : yig'ish tartibi qimmat.
Beqaror : Uyma tartiblash beqaror. Bu nisbiy tartibni o'zgartirishi mumkin.
Samarali: Uyma tartiblash juda murakkab ma'lumotlar bilan ishlashda
unchalik samarali emas.
HeapSort ilovalari:
Heapsort asosan gibrid algoritmlarda qo'llaniladi
IntroSort
Deyarli tartiblangan (yoki K tartiblangan) massivni saralash
massivdagi k eng katta (yoki eng kichik) elementlar
Uyumli tartiblash algoritmi cheklangan foydalanishga ega, chunki
Quicksort va Mergesort amalda yaxshiroq. Shunga qaramay, Heap ma'lumotlar
strukturasining o'zi juda ko'p ishlatiladi.
Heapify - massiv yordamida ifodalangan ikkilik daraxtdan yig'ma
ma'lumotlar strukturasini yaratish jarayoni. U Min-Heap yoki Max-heap
yaratish uchun ishlatiladi. Indeksi n/2 – 1 bilan berilgan bargsiz tugunning
oxirgi indeksidan boshlang. Heapify rekursiyadan foydalanadi.
Heapify uchun algoritm:
heapify(massiv)
Root = massiv[0]
Eng katta = eng katta( massiv[0] , massiv [2 * 0 + 1]/ massiv [2 * 0 + 2])
if(Root != Eng katta)](/data/documents/4510d625-03b7-4bdc-9e97-5877679e64d4/page_11.png)
![Swap(Root, Largest)
Heapify qanday ishlaydi?
Massiv = {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17}
Tegishli to liq ikkilik daraxt:ʻ
1
/ \
3 5
/ \ / \
4 6 13 10
/ \ / \
9 8 15 17
Yuqoridagi massivdan Max-Heap qurish vazifasi .
Jami tugunlar = 11.
Jami bargsiz tugunlar= (11/2)-1=5
oxirgi bargsiz tugun = 6.
Shuning uchun, oxirgi barg bo'lmagan tugun indeksi = 4.
Uyumni qurish uchun faqat tugunlarni to'plang: [1, 3, 5, 4, 6] teskari
tartibda.
Heapify 6 : 6 va 17-ni almashtiring.
1
/ \
3 5
/ \ / \
4 17 13 10
/ \ / \
9 8 15 6
Heapify 4 : 4 va 9-ni almashtiring.](/data/documents/4510d625-03b7-4bdc-9e97-5877679e64d4/page_12.png)
![17
/ \
15 13
/ \ / \
9 6 5 10
/ \ / \
4 8 3 1
2.3. Uyumni saralash algoritmi
Uyumni saralash algoritmi
Muammoni hal qilish uchun quyidagi fikrga amal qiling:
Avval massivni heapify-dan foydalanib yig'ma ma'lumotlar strukturasiga
aylantiring, so'ngra Max-heapning ildiz tugunini birin-ketin o'chiring va uni
uyumdagi oxirgi tugun bilan almashtiring va keyin uyumning ildizini yig'ing.
Uyumning o'lchami 1 dan katta bo'lguncha bu jarayonni takrorlang
Muammoni hal qilish uchun quyidagi amallarni bajaring:
Kirish ma'lumotlaridan maksimal to'p hosil qiling.
Bu vaqtda maksimal element to'pning ildizida saqlanadi. Uni to'plamning
oxirgi elementi bilan almashtiring, so'ngra to'plam hajmini 1 ga kamaytiring.
Nihoyat, daraxt ildizini to'plang.
Uyumning o'lchami 1 dan katta bo'lganda 2-bosqichni takrorlang.
Eslatma: Tugunga to'g'rilash jarayoni faqat uning asosiy tugunlari yig'ilgan
bo'lsa, qo'llanilishi mumkin. Shunday qilib, yig'ish pastdan yuqoriga qarab
amalga oshirilishi kerak.
Uyma tartiblashning batafsil ishlashi
Uyma tartiblashni aniqroq tushunish uchun keling, tartiblanmagan
massivni olaylik va uni yig'ma tartiblash yordamida saralashga harakat qilaylik.
Massivni ko'rib chiqing: arr[] = {4, 10, 3, 5, 1}.
To'liq ikkilik daraxtni yaratish: massivdan to'liq ikkilik daraxtni yarating.
Massivdan to'liq ikkilik daraxtni yarating
Massivdan to'liq ikkilik daraxtni yarating](/data/documents/4510d625-03b7-4bdc-9e97-5877679e64d4/page_14.png)
![Maksimal to'pga aylantirish: Shundan so'ng, vazifa o'sha tartiblanmagan
massivdan daraxt qurish va uni maksimal to'pga aylantirishga harakat qilishdir.
Uyumni maksimal yig'maga aylantirish uchun asosiy tugun har doim
kichik tugunlardan katta yoki teng bo'lishi kerak
Bu erda, ushbu misolda, 4- ota tugun 10-chi tugundan kichikroq bo'lgani
uchun, ularni maksimal yig'ish uchun almashtiring.
Uni maksimal yig'ma tasvir vidjetiga aylantiring
Endi, ko'rinib turganidek, ota-ona sifatida 4 bola 5 dan kichikroq , shuning
uchun ikkalasini ham almashtiring va natijada hosil bo'lgan to'p va massiv
quyidagicha bo'lishi kerak:
Daraxtni maksimal to'pga aylantiring
Daraxtni maksimal to'pga aylantiring
Uyumni saralashni amalga oshiring: Har bir qadamda maksimal elementni
olib tashlang (ya'ni, uni oxirgi holatga o'tkazing va uni olib tashlang) va keyin
qolgan elementlarni ko'rib chiqing va uni maksimal to'pga aylantiring.
Ildiz elementni (10) maksimal to'pdan o'chiring. Ushbu tugunni o'chirish
uchun uni oxirgi tugun bilan almashtirishga harakat qiling, ya'ni (1). Ildiz
elementni olib tashlaganingizdan so'ng, uni maksimal to'plamga aylantirish
uchun yana yig'ing.
Natijadagi to'p va massiv quyidagicha ko'rinishi kerak:
10 ni olib tashlang va heapify qiling
10 ni olib tashlang va heapify qiling
Yuqoridagi amallarni takrorlang va u quyidagicha ko'rinadi:
5 ni olib tashlang va heapify qiling
5 ni olib tashlang va heapify qiling
Endi ildizni (ya'ni 3) yana olib tashlang va heapify-ni bajaring.
4 ni olib tashlang va heapify qiling
4 ni olib tashlang va heapify qiling
Endi ildiz yana bir marta olib tashlanganda, u tartiblanadi. va tartiblangan
massiv arr[] = {1, 3, 4, 5, 10} kabi bo'ladi .
Saralangan massiv
Saralangan massi](/data/documents/4510d625-03b7-4bdc-9e97-5877679e64d4/page_15.png)
![Uyma tartibini amalga oshirish
Quyida yuqoridagi yondashuvni amalga oshirish ko'rsatilgan:
// Heap Sort in C
#include <stdio.h>
// Function to swap the position of two elements
void swap(int* a, int* b)
{ int temp = *a;
*a = *b;
*b = temp;
}
// To heapify a subtree rooted with node i
// which is an index in arr[].
// n is size of heap
void heapify(int arr[], int N, int i)
{
// Find largest among root, left child and right child
// Initialize largest as root
int largest = i;
// left = 2*i + 1
int left = 2 * i + 1;
// right = 2*i + 2
int right = 2 * i + 2;
// If left child is larger than root
if (left < N && arr[left] > arr[largest])
largest = left;
// If right child is larger than largest
// so far](/data/documents/4510d625-03b7-4bdc-9e97-5877679e64d4/page_16.png)
![if (right < N && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
// If largest is not root
if (largest != i) {
swap(&arr[i], &arr[largest]);
// Recursively heapify the affected
// sub-tree
heapify(arr, N, largest); }}
// Main function to do heap sort
void heapSort(int arr[], int N)
{ // Build max heap
for (int i = N / 2 - 1; i >= 0; i--)
heapify(arr, N, i);
// Heap sort
for (int i = N - 1; i >= 0; i--)
swap(&arr[0], &arr[i]);
// Heapify root element to get highest element at
// root again
heapify(arr, i, 0);
}
}
// A utility function to print array of size n
void printArray(int arr[], int N)
{
for (int i = 0; i < N; i++)
printf("%d ", arr[i]);
printf("\n");](/data/documents/4510d625-03b7-4bdc-9e97-5877679e64d4/page_17.png)
![}
// Driver's code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
heapSort(arr, N);
printf("Sorted array is\n");
printArray(arr, N);
// This code is contributed by _i_plus_plus_.
Chiqish
Saralangan massiv
5 6 7 11 12 13
Vaqt murakkabligi: O(N log N)
Yordamchi fazo: O(1)
Uyma tartiblash bilan bog'liq ba'zi tez-tez so'raladigan savollar
Uyma tartiblashning ikki bosqichi qanday?
Uyumni saralash algoritmi ikki bosqichdan iborat. Birinchi bosqichda
massiv maksimal to'pga aylantiriladi. Va ikkinchi bosqichda eng yuqori element
(ya'ni, daraxt ildizidagi) olib tashlanadi va qolgan elementlar yangi max to'pni
yaratish uchun ishlatiladi.
Nima uchun Uyma tartiblash barqaror emas?
Uyma tartiblash algoritmi barqaror algoritm emas. Bu algoritm barqaror
emas, chunki uyada bajariladigan amallar ekvivalent kalitlarning nisbiy tartibini
o'zgartirishi mumkin.
Heap Sort "Bo'l va zabt et" algoritmiga misolmi?](/data/documents/4510d625-03b7-4bdc-9e97-5877679e64d4/page_18.png)
![2. https://yandex.ru/search/?text=About+Brodala-
okasaki+heap.geeksforgeeks&lr=10334&clid=2384857-110&win=541;
3. https://www.google.com/search?q=Brodala-
okasaki+heap.org&oq=Brodala-
okasaki+heap.org&aqs=chrome..69i57j33i10i160.12407j0j7&sourceid=chrom
e&ie=UTF-8;
4. https://en.wikipedia.org/wiki/Brodal_queue;
ILOVALAR
ILOVA 1. Modul N1 boshlang’ich kodi
// Heap Sort in C
#include <stdio.h>
// Function to swap the position of two elements
void swap(int* a, int* b)
{ int temp = *a;
*a = *b;
*b = temp;
}
// To heapify a subtree rooted with node i
// which is an index in arr[].
// n is size of heap
void heapify(int arr[], int N, int i)
{
// Find largest among root, left child and right child
// Initialize largest as root
int largest = i;
// left = 2*i + 1
int left = 2 * i + 1;](/data/documents/4510d625-03b7-4bdc-9e97-5877679e64d4/page_20.png)
![// right = 2*i + 2
int right = 2 * i + 2;
// If left child is larger than root
if (left < N && arr[left] > arr[largest])
largest = left;
// If right child is larger than largest
if (right < N && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
// If largest is not root
if (largest != i) {
swap(&arr[i], &arr[largest]);
// Recursively heapify the affected
// sub-tree
heapify(arr, N, largest); }}
// Main function to do heap sort
void heapSort(int arr[], int N)
{ // Build max heap
for (int i = N / 2 - 1; i >= 0; i--)
heapify(arr, N, i);
// Heap sort
for (int i = N - 1; i >= 0; i--)
swap(&arr[0], &arr[i]);
// Heapify root element to get highest element at
// root again
heapify(arr, i, 0);
}
}](/data/documents/4510d625-03b7-4bdc-9e97-5877679e64d4/page_21.png)
![// A utility function to print array of size n
void printArray(int arr[], int N)
{
for (int i = 0; i < N; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver's code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
heapSort(arr, N);
printf("Sorted array is\n");
printArray(arr, N);
// This code is contributed by _i_plus_plus_.
Chiqish
Saralangan massiv
5 6 7 11 12 13
Vaqt murakkabligi: O(N log N)
Yordamchi fazo: O(1)](/data/documents/4510d625-03b7-4bdc-9e97-5877679e64d4/page_22.png)
Mavzu: “Brodala-Okasaki uyumi”. MUNDARIJA Kirish ......................................................................................................... 2 I Bob. Ustuvor mavbat va uyum haqida umumiy tushunchalar ............... 3 II Bob. Brodala-okasaki uyumi haqida boshlang'ich tushunchalar ........... 6 2.1. Asimptotik optimallik. ........................................................................ 9 2.2. Uyma tartiblash. ............................................................................... 10 2.3. Uyumni saralash algoritmi ............................................................... 14 Xulosa ...................................................................................................... 19 ADABIYOTLAR RO’YXATI ................................................................ 19 ILOVALAR ............................................................................................. 20 ILOVA 1. Modul N1 boshlang’ich kodi ................................................. 20
Kirish Ustivor navbatlar ko'pincha uyum (kucha) bilan amalga oshirilsa-da, ular konseptual jihatdan uyumlardan farq qiladi. Ustivor navbat - bu "ro'yxat" yoki "karta" ga o'xshash narsa; Ro'yxat bog langan ro'yxat yoki massiv yordamida ʻ amalga oshirilishi mumkin bo'lganidek, ustivor navbat uyum yoki tartiblanmagan massiv kabi boshqa usullar yordamida amalga oshirilishi mumkin. Ustivor navbat - bu yozuvlar bir-biri bilan chiziqli taqqoslanadigan kalitlarga (masalan, raqamlar) ega bo'lgan va ikkita amalni realizatsiya qiladigan axborot tizimidir. Bu ikki amal tizimga tasodifiy yozuvni kiritish va yozuv tizimidan eng kichigi bilan tanlov kalit. Dasturiy ta'minot tizimlarida ustivor navbatlar juda keng tarqalgan va dasturlarn
I Bob . Ustuvor mavbat va uyum haqida umumiy tushunchalar Ko'pgina ilovalar kalitlarga ega bo'lgan elementlarni qayta ishlashni talab qiladi, lekin ular to'liq tartibda va birdaniga hamasi emas. Ko'pincha, biz bir qator narsalarni to'playmiz, so'ngra eng katta kalit bilan ishlov beramiz, keyin ko'proq narsalarni to'playmiz, so'ngra hozirgi eng katta kalit bilan ishlov beramiz va hokazo. Bunday muhitda tegishli ma'lumotlar turi ikkita amalni qo'llab-quvvatlaydi: maksimal miqdorni o chirishʻ va joylashtirish. Bunday ma'lumotlar turi ustivor navbat deb nomlanadi. Ustivor navbatlar odatdagi navbat yoki stek ma'lumotlar tuzilmasiga o'xshash abstrakt ma'lumotlar turi bo'lib, unda har bir element qo'shimcha ravishda bog liq ʻ bo'lgan "ustivorlikka" ega. Ustivor navbatda yuqori ustivor element past ustivor elementdan oldin xizmat qiladi. 3 Ustivor navbatlar ko'pincha uyum (kucha) bilan amalga oshirilsa-da, ular konseptual jihatdan uyumlardan farq qiladi. Ustivor navbat - bu "ro'yxat" yoki "karta" ga o'xshash narsa; Ro'yxat bog langan ro'yxat yoki massiv yordamida ʻ amalga oshirilishi mumkin bo'lganidek, ustivor navbat uyum yoki tartiblanmagan massiv kabi boshqa usullar yordamida amalga oshirilishi mumkin. Ustivor navbat - bu yozuvlar bir-biri bilan chiziqli taqqoslanadigan kalitlarga (masalan, raqamlar) ega bo'lgan va ikkita amalni realizatsiya qiladigan axborot tizimidir. Bu ikki amal tizimga tasodifiy yozuvni kiritish va yozuv tizimidan eng kichigi bilan tanlov kalit. Dasturiy ta'minot tizimlarida ustivor navbatlar juda keng tarqalgan va dasturlarning ishlashi to'g ridan-to'g ri ʻ ʻ ularni amalga oshirish samaradorligiga bog liq. ʻ Ustivorda navbatda qo llab-quvvatlanadigan amallar quyidagilar ʻ hisoblanadi: 1) Insert - navbatga element qo'shish 2) Max - ustivorligi yuqori bo'lgan elementni qaytaradi 3) ExtractMax - navbatdagi eng ustivor elementni olib tashlaydi 4) IncreaseKey - berilgan elementning ustivor qiymatini o'zgartiradi 5) Merge - ikkita navbatni bittaga birlashtiradi 1.1 Binar uyum (kucha) - piramida (binary heap). Binar uyum (binary heap) bu quyidagi shartlarni qanoatlantiradigan binar daraxtdir: - Har qanday uchning ustivorligi, uning avlodlarining ustivorligidan kichik emas.
- Daraxt to'liq ikkilik daraxt bo lishi uchun (complete binaryʻ tree) -barcha darajalar chapdan o'ngga to'ldiriladi (oxirgisi bundan mustasno bo lishi mumkin). ʻ 4 4 MAX 1-rasm. O’smaydigan piramida max-heap Har qanday uchning ustuvorligi avlodlarning ustuvorligidan kichik emas 4 MIN 100 10 36 25 1 17 13 1
2-rasm. Kamaymaydigan piramida min-heap Har qanday uchning ustuvorligi avlodlarning ustuvorligidan katta e mas 2 3 3 6 71 7 1 9 25 100