pufakchaga tushishda davom etadi.
Xuddi shu jarayon
maksimal to'plar uchun ham amal qiladi, lekin tartib shundayki, bolalar
ikkalasi ham joriy tugundan kattaroqdir.
Ro'yxatdan to'p yaratish
N ta elementlar roʻyxatidan toʻp yaratishga yondashuvlardan biri
boʻsh toʻplamdan boshlanib, roʻyxatdagi har bir elementni birma-
bir qoʻshishdir. Bu yondashuv O(N log N) vaqtni oladi, chunki u N
ta kiritishni amalga oshiradi, ularning har biri log N vaqt
oladi. Biroq, bu yondashuv suboptimal va N ta elementdan to'p
qurishning optimal yondashuvi faqat O(N) vaqtini oladi!
Ushbu optimallashtirish ortidagi matematika va amalga oshirish
biroz murakkab, ammo
Vikipediya sahifasida
yaxshi tushuntirilgan
. Optimallashtirish haqida umumiy tushunchaga ega bo'lish yaxshi
fikr.
Python-da heapify funktsiyasi chiziqli vaqt ichida ro'yxatdagi
to'plamni yaratadi.
Amalga oshirish
Ajablanarlisi shundaki, bu murakkab ma'lumotlar strukturasi
massiv yordamida ifodalanishi mumkin! Ildiz tugun har doim
uyada eng kichik yoki eng katta element bo'lishini hisobga olsak,
biz ushbu elementni massivning birinchi elementi sifatida
joylashtirishimiz mumkin. Keyin bu asosiy massiv to'pning har bir
sathidan, chapdan o'ngga, yuqoridan pastga qarab to'ldiriladi.
To'liqlik kafolati va uyaning ikkilik daraxti xususiyati bilan biz
ushbu formulalar yordamida har bir tugunning bolalari va ota-
onalari indekslarini osongina hisoblashimiz mumkin:
Ota-ona: (joriy indeks - 1) // 2 (pastga yaxlitlash)
Chap bola: (joriy indeks * 2) + 1
O'ng bola: (joriy indeks * 2) + 2
Ushbu hisob-kitoblar unga massivga kiritish va olib tashlash
protseduralarini osongina amalga oshirish imkonini beradi. Qo'shishni
amalga oshirganimizda, biz yig'ish xususiyatini saqlab qolish uchun u bilan
almashish uchun ota-onaning joylashishini hisoblashimiz kerak. Qo'shish
operatsiyalari paytida elementni uning bolalaridan biri bilan almashtirish
kerak bo'lsa, chap va o'ng bolani hisoblashdan ham foydalanishimiz kerak.
Runtimelar
Eng yomon stsenariyda qo'shish va o'chirish uchun almashtirish
protsedurasi elementni uyum balandligi bo'ylab
harakatlantiradi. Uyumlar imkon qadar to'liq bo'lishi kafolatlangan
ikkilik daraxtlar bo'lgani uchun, uyumdagi darajalar soni log n
bo'ladi.
Misollar .
Max heap ga misol :
#include
#include
using namespace std;
class MaxHeap {
private:
vector heap;
void heapifyUp(int index) {
int parent = (index - 1) / 2;
while (index > 0 && heap[index] > heap[parent]) {
swap(heap[index], heap[parent]);
index = parent;
parent = (index - 1) / 2;
}
}
void heapifyDown(int index) {
int leftChild, rightChild, maxChild;
while (true) {
leftChild = 2 * index + 1;
rightChild = 2 * index + 2;
maxChild = index;
if (leftChild < heap.size() && heap[leftChild] > heap[maxChild]) {
maxChild = leftChild;
}
if (rightChild < heap.size() && heap[rightChild] > heap[maxChild]) {
maxChild = rightChild;
}
if (index != maxChild) {
swap(heap[index], heap[maxChild]);
index = maxChild;
} else {
break;
}
}
}
public:
void insert(int value) {
heap.push_back(value);
heapifyUp(heap.size() - 1);
}
int extractMax() {
if (heap.empty()) {
cerr << "Heap is empty." << endl;
return -1;
}
int maxVal = heap[0];
heap[0] = heap.back();
heap.pop_back();
heapifyDown(0);
return maxVal;
}
void display() {
for (int i : heap) {
cout << i << " ";
}
cout << endl;
}
};
int main() {
MaxHeap maxHeap;
maxHeap.insert(12);
maxHeap.insert(7);
maxHeap.insert(6);
maxHeap.insert(10);
maxHeap.insert(8);
maxHeap.insert(20);
cout << "Max Heap: ";
maxHeap.display();
cout << "Extracting Max: " << maxHeap.extractMax() << endl;
cout << "Max Heap after extraction: ";
maxHeap.display();
return 0;
}
Min heap ga misol :
#include
#include
using namespace std;
class MinHeap {
private:
vector heap;
void heapifyUp(int index) {
int parent = (index - 1) / 2;
while (index > 0 && heap[index] < heap[parent]) {
swap(heap[index], heap[parent]);
index = parent;
parent = (index - 1) / 2;
}
}
void heapifyDown(int index) {
int leftChild, rightChild, minChild;
while (true) {
leftChild = 2 * index + 1;
rightChild = 2 * index + 2;
minChild = index;
if (leftChild < heap.size() && heap[leftChild] < heap[minChild]) {
minChild = leftChild;
}
if (rightChild < heap.size() && heap[rightChild] < heap[minChild]) {
minChild = rightChild;
}
if (index != minChild) {
swap(heap[index], heap[minChild]);
index = minChild;
} else {
break;
}
}
}
public:
void insert(int value) {
heap.push_back(value);
heapifyUp(heap.size() - 1);
}
int extractMin() {
if (heap.empty()) {
cerr << "Heap bo'sh." << endl;
return -1;
}
int minVal = heap[0];
heap[0] = heap.back();
heap.pop_back();
heapifyDown(0);
return minVal;
}
void display() {
for (int i : heap) {
cout << i << " ";
}
cout << endl;
}
};
int main() {
MinHeap minHeap;
minHeap.insert(12);
minHeap.insert(7);
minHeap.insert(6);
minHeap.insert(10);
minHeap.insert(8);
minHeap.insert(20);
cout << "Min Heap: ";
minHeap.display();
cout << "Eng kichikni olish: " << minHeap.extractMin() << endl;
cout << "Min Heap olishdan so'ng: ";
minHeap.display();
return 0;
}
Xulosa :
i.
Heaplar, ayniqsa, eng katta yoki eng kichik elementlarni olishda va
tez qidirish, o'chirish yoki qidirish sizga ahamiyat bermaydigan
holatlarda foydalidir.
ii.
Heaplar, ayniqsa, ba'zi ma'lumotlar to'plamining x-eng katta yeng
kichik elementlarini olishni o'z ichiga olgan savollar uchun foydalidir.
iii.
Heapni yaratish faqat O(n) vaqtni oladi, shuning uchun siz to'plamni
yaratish uchun qo'shishni n marta bajarish o'rniga ro'yxatdan uyum
yaratish orqali yechimni optimallashtirishingiz mumkin.
| 