Heap sort haqida
![Kirish. Uyumni saralash algoritmi
Heap Sort - bu kompyuter dasturlashda mashhur va samarali tartiblash
algoritmi . Uyumli tartiblash algoritmini yozishni o'rganish uchun ikki turdagi
ma'lumotlar tuzilmalarini - massivlarni va daraxtlarni bilish kerak.
I bob. Heap sort
Biz tartiblamoqchi bo'lgan dastlabki raqamlar to'plami massivda saqlanadi,
masalan [10, 3, 76, 34, 23, 32], tartiblangandan so'ng biz tartiblangan massivni
olamiz [3,10,23,32,34,76].
Uyumni saralash massiv elementlarini to'liq ikkilik daraxtning maxsus turi
sifatida tasvirlash orqali ishlaydi.
Eslatma: Majburiy shart sifatida siz to'liq ikkilik daraxt va yig'ma
ma'lumotlar tuzilishi haqida bilishingiz kerak .
Massiv indekslari va daraxt elementlari o'rtasidagi bog'liqlik
To'liq ikkilik daraxt qiziqarli xususiyatga ega bo'lib, biz har qanday
tugunning bolalari va ota-onalarini topish uchun foydalanishimiz mumkin.
Agar massivdagi biron bir elementning indeksi bo'lsai,
indeksdagi 2i+1element chap bolaga, 2i+2indeksdagi element esa o'ng
yordamchiga aylanadi. Shuningdek, indeksdagi har qanday elementning ota-onasi i
ning pastki chegarasi bilan berilgan (i-1)/2.
Massiv va to'p
indekslari o'rtasidagi bog'liqlik
Keling, sinab ko'raylik,
Chap bola 1 (indeks 0)
= (2*0+1) indeksdagi element
= 1 indeksdagi element
= 12
1 bolaning o'ng farzandi
2](/data/documents/7a96d952-5241-461e-a59c-690b1c1d5f71/page_2.png)
![Maks to'p va min yig'im
Daraxtni qanday qilib
"to'plash" mumki n.
To'liq ikkilik daraxtdan
boshlab, biz to'plamning
barcha barg bo'lmagan
elementlarida heapify deb
nomlangan funktsiyani
ishga tushirish orqali uni
Max-Heapga
aylantirishimiz mumkin.
Heapify rekursiyadan foydalanganligi sababli, uni tushunish qiyin bo'lishi
mumkin. Shunday qilib, keling, birinchi navbatda, uchta element bilan daraxtni
qanday yig'ish kerakligini o'ylab ko'raylik.
heapify(array)
Root = array[0]
Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2])
if(Root != Largest)
Swap(Root, Largest)
5](/data/documents/7a96d952-5241-461e-a59c-690b1c1d5f71/page_5.png)
![I
ldiz elementining pastki daraxtlari maksimal to'p bo'lsa, uni qanday yig'ish kerak
Shunday qilib, har ikkala pastki daraxt ham max-heap bo‘lgan daraxtda
max-heap xususiyatini saqlab qolish uchun ildiz elementi uning bolalaridan
kattaroq bo‘lguncha yoki barg tuguniga aylanmaguncha heapify-ni qayta-qayta
ishga tushirishimiz kerak.
Biz bu ikkala shartni bitta to'plash funktsiyasida birlashtira olamiz
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
Bu funksiya asosiy korpus uchun ham, har qanday o‘lchamdagi daraxt uchun
ham ishlaydi. Shunday qilib, pastki daraxtlar maksimal to'p bo'lsa, har qanday
daraxt o'lchami uchun maksimal to'p holatini saqlab qolish uchun ildiz elementini
to'g'ri joyga ko'chirishimiz mumkin.
Maksimal to'pni yarating
Har qanday daraxtdan maksimal to'pni qurish uchun biz har bir kichik
daraxtni pastdan yuqoriga yig'ishni boshlashimiz mumkin va funktsiya barcha
7](/data/documents/7a96d952-5241-461e-a59c-690b1c1d5f71/page_7.png)
![Quyidagi kod operatsiyani ko'rsatadi.
// Heap sort
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
1.2.heap sort algoritmini c++ da kodi
// Heapify root element to get highest element at root again
heapify(arr, i, 0);
}
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(arr[i], arr[largest]);
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);
}
}
13](/data/documents/7a96d952-5241-461e-a59c-690b1c1d5f71/page_13.png)
![// Print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
// Driver code
int main() {
int arr[] = {1, 12, 9, 5, 6, 10};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
}
Uymli saralash murakkabligi
Vaqtning murakkabligi
Eng yaxshi O(nlog n)
Eng yomoni O(nlog n)
O'rtacha O(nlog n)
Heap Sort O(nlog n)barcha holatlar uchun vaqt murakkabligiga ega (eng
yaxshi holat, o'rtacha holat va eng yomon holat).
Buning sababini tushunaylik. Tarkibida n ta element bo lgan to liq ikkilikʻ ʻ
daraxtning balandligilog n
Yuqorida aytib o'tganimizdek, pastki daraxtlari allaqachon max-uymalar
bo'lgan elementni to'liq yig'ish uchun biz elementni chap va o'ng bolalari bilan
solishtirishni davom ettirishimiz va ikkala bolasi ham kichikroq bo'lgan nuqtaga
yetguncha uni pastga surishimiz kerak.
Eng yomon stsenariyda biz elementni ildizdan barg tuguniga ko'chirishimiz kerak,
bu ko'p log(n)taqqoslash va almashtirish.
build_max_heap bosqichida biz buni n/2elementlar uchun qilamiz, shuning uchun
build_heap bosqichining eng yomon murakkabligi n/2*log n ~ nlog n.
Saralash bosqichida biz ildiz elementini oxirgi element bilan almashtiramiz
va ildiz elementini yig'amiz. Har bir element uchun bu yana log neng yomon
14](/data/documents/7a96d952-5241-461e-a59c-690b1c1d5f71/page_14.png)
![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.
HeapSort ilovalari:
Heapsort asosan IntroSort kabi gibrid algoritmlarda qo'llaniladi .
Deyarli tartiblangan (yoki K tartiblangan) massivni saralash
massivdagi k eng katta (yoki eng kichik) elementlar
Uyumni saralash algoritmi cheklangan foydalanishga ega, chunki Quicksort
va Mergesort amalda yaxshiroq. Shunga qaramay, Heap ma'lumotlar
strukturasining o'zi juda ko'p ishlatiladi.
Muammoni Hal Qilish
Yuborilganlar soni: 68.2K
Heapify nimani anglatadi?
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 birinchi
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)
Swap(Root, Largest)
Heapify qanday ishlaydi?
Massiv = {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17}
Tegishli to liq ikkilik daraxt:ʻ
Yuqoridagi massivdan Max-Heap qurish vazifasi .
16](/data/documents/7a96d952-5241-461e-a59c-690b1c1d5f71/page_16.png)
![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.
Heapify 4 : 4 va 9-ni almashtiring.
Heapify 5 : 13 va 5 ni almashtiring.
Heapify 3 : Avval 3 va 17 ni almashtiring, yana 3 va 15 ni almashtiring.
17](/data/documents/7a96d952-5241-461e-a59c-690b1c1d5f71/page_17.png)
![Heapify 1 : Avval 1 va 17 ni almashtiring, yana 1 va 15 ni almashtiring, nihoyat 1
va 6 ni almashtiring.
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.
18](/data/documents/7a96d952-5241-461e-a59c-690b1c1d5f71/page_18.png)
![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
Endi ildiz yana bir marta olib tashlanganda, u tartiblanadi. va tartiblangan
massiv arr[] = {1, 3, 4, 5, 10} kabi bo'ladi.
21](/data/documents/7a96d952-5241-461e-a59c-690b1c1d5f71/page_21.png)
![Saralangan massiv
Uyma tartibini amalga oshirish
Quyida yuqoridagi yondashuvni amalga oshirish ko'rsatilgan:
C++
// 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;
22](/data/documents/7a96d952-5241-461e-a59c-690b1c1d5f71/page_22.png)
![// If right child is larger than largest
// so far
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");
}
// Driver's code
int main()
{
23](/data/documents/7a96d952-5241-461e-a59c-690b1c1d5f71/page_23.png)
![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);
}
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?
Uyma tartiblash umuman Bo'l va bosib ol algoritmi EMAS . U elementlarni
saralash uchun “bo‘l va zabt et” yondashuvidan emas, balki uning elementini
samarali saralash uchun yig‘ma ma’lumotlar strukturasidan foydalanadi.
Qaysi tartiblash algoritmi yaxshiroq - yig'ish tartibi yoki birlashtirish tartibi?
Javob ularning vaqt murakkabligi va makonga bo'lgan talabni taqqoslashda
yotadi. Birlashtirish tartibi Uyma tartiblashdan biroz tezroq. Biroq, boshqa
tomondan, birlashtirish tartibi qo'shimcha xotirani oladi. Talabga qarab, qaysi
birini ishlatishni tanlash kerak.
Nima uchun Uyma tartiblash Tanlashdan yaxshiroq?
Uyumni saralash tanlov tartibiga o'xshaydi, lekin maksimal elementni
olishning yaxshiroq usuli bilan. Doimiy vaqtda maksimal elementni olish uchun u
yig'ma ma'lumotlar strukturasidan foydalanadi.
Uyma tartiblash umuman Bo'l va bosib ol algoritmi EMAS . U elementlarni
saralash uchun “bo‘l va zabt et” yondashuvidan emas, balki uning elementini
samarali saralash uchun yig‘ma ma’lumotlar strukturasidan foydalanadi.
24](/data/documents/7a96d952-5241-461e-a59c-690b1c1d5f71/page_24.png)
Mundarija Kirish. Uyumni saralash algoritmi ................................................................................................................ 2 I bob. Heap sort ........................................................................................................................................... 2 1.1.Heap sort algoritmi haqida .................................................................................................................... 3 1.2.heap sort algoritmini c++ da kodi ........................................................................................................ 13 Uymli saralash murakkabligi ...................................................................................................................... 14 Xulosa. ....................................................................................................................................................... 26 Manbalar ................................................................................................................................................... 27 1
Kirish. Uyumni saralash algoritmi Heap Sort - bu kompyuter dasturlashda mashhur va samarali tartiblash algoritmi . Uyumli tartiblash algoritmini yozishni o'rganish uchun ikki turdagi ma'lumotlar tuzilmalarini - massivlarni va daraxtlarni bilish kerak. I bob. Heap sort Biz tartiblamoqchi bo'lgan dastlabki raqamlar to'plami massivda saqlanadi, masalan [10, 3, 76, 34, 23, 32], tartiblangandan so'ng biz tartiblangan massivni olamiz [3,10,23,32,34,76]. Uyumni saralash massiv elementlarini to'liq ikkilik daraxtning maxsus turi sifatida tasvirlash orqali ishlaydi. Eslatma: Majburiy shart sifatida siz to'liq ikkilik daraxt va yig'ma ma'lumotlar tuzilishi haqida bilishingiz kerak . Massiv indekslari va daraxt elementlari o'rtasidagi bog'liqlik To'liq ikkilik daraxt qiziqarli xususiyatga ega bo'lib, biz har qanday tugunning bolalari va ota-onalarini topish uchun foydalanishimiz mumkin. Agar massivdagi biron bir elementning indeksi bo'lsai, indeksdagi 2i+1element chap bolaga, 2i+2indeksdagi element esa o'ng yordamchiga aylanadi. Shuningdek, indeksdagi har qanday elementning ota-onasi i ning pastki chegarasi bilan berilgan (i-1)/2. Massiv va to'p indekslari o'rtasidagi bog'liqlik Keling, sinab ko'raylik, Chap bola 1 (indeks 0) = (2*0+1) indeksdagi element = 1 indeksdagi element = 12 1 bolaning o'ng farzandi 2
= (2*0+2) indeksdagi element = 2 indeksdagi element = 9 Xuddi shunday, 12 yoshli chap bola (indeks 1) = (2*1+1) indeksdagi element = 3 indeksdagi element = 5 12 yoshli o'ng bola = (2*1+2) indeksdagi element = 4 indeksdagi element = 6 Keling, har qanday tugunning ota-onasini topish uchun qoidalar mavjudligini tasdiqlaylik 9 bolaning ota-onasi (2-pozitsiya) = (2-1)/2 = ½ = 0,5 ~ 0 indeks = 1 12 yoshli ota-ona (1-pozitsiya) = (1-1)/2 = 0 indeks = 1 Massiv indekslarini daraxt pozitsiyalariga solishtirishni tushunish, yig'ma ma'lumotlar tuzilmasi qanday ishlashini va undan yig'ish saralashni amalga oshirishda qanday ishlatilishini tushunish uchun juda muhimdir. Uyma ma'lumotlar strukturasi nima? 1.1.Heap sort algoritmi haqida Heap - bu daraxtga asoslangan maxsus ma'lumotlar tuzilmasi. Ikkilik daraxt to'plangan ma'lumotlar strukturasiga amal qiladi, deyiladi if bu to'liq ikkilik daraxtdir Daraxtdagi barcha tugunlar o'z farzandlaridan katta bo'lgan xususiyatga amal qiladi, ya'ni eng katta element ildizda va uning ikkala bolalari va ildizdan kichikroq va hokazo. Bunday to'p max-heap deb ataladi. Buning o'rniga, barcha tugunlar o'z farzandlaridan kichikroq bo'lsa, u min-to'p deb ataladi 3
Quyidagi misol diagrammasi Max-Heap va Min-Heapni ko'rsatadi. 4
Maks to'p va min yig'im Daraxtni qanday qilib "to'plash" mumki n. To'liq ikkilik daraxtdan boshlab, biz to'plamning barcha barg bo'lmagan elementlarida heapify deb nomlangan funktsiyani ishga tushirish orqali uni Max-Heapga aylantirishimiz mumkin. Heapify rekursiyadan foydalanganligi sababli, uni tushunish qiyin bo'lishi mumkin. Shunday qilib, keling, birinchi navbatda, uchta element bilan daraxtni qanday yig'ish kerakligini o'ylab ko'raylik. heapify(array) Root = array[0] Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2]) if(Root != Largest) Swap(Root, Largest) 5