Boʻsh uyum (kucha) hosil qilish
struct heap *heap_create(int maxsize)
{
struct heap *h;
h = malloc(sizeof(*h));
if (h != NULL)
{
h->maxsize = maxsize;
h->nnodes = 0;
/* Heap nodes [0, 1, maxsize] */
h->nodes = malloc(sizeof(*h->nodes) * (maxsize + 1));
if (h->nodes == NULL)
144
{
free(h);
return NULL;
}
return h;
}
Uyumni oʻchirish
void heap_free(struct heap *h)
{
free(h->nodes);
free(h);
}
void heap_swap(struct heapnode *a, struct heapnode *b)
{
struct heapnode temp;
temp = *a;
*a = *b;
*b = temp; }
16
14 10 8
7
9
3
2
4
1
51-rasm. Maksimal elementni izlash
struct heapnode *heap_max(struct heap *h
{
if (h->nnodes == 0)
return NULL;
return &h->nodes[l];
}
Maksimal element
max-heap ildizida
saqlanadi
max-heap (10 ta element)
145
Binar uyum (kucha) ga element qoʻshish.
Ustuvorligi 15 ga teng
boʻlgan elementni joylashtirish
52-rasm. Binar uyum (kucha) ga element qoʻshish
Binar kuchaga element joylashtirish
int heap_insert(struct heap *h, int key, char *value)
{
if (h->nnodes >= h->maxsize) {
return -1;
}
h->nnodes++;
h->nodes[h->nnodes].key = key;
h->nodes[h->nnodes].value = value;
for (int i = h->nnodes; i > 1 &&
h->nodes[i].key > h->nodes[i / 2].key; i = i/2)
{
heap_swap(&h->nodes[i], &h->nodes[i / 2]);
}
return 0;
146
}
Maksimal elementni oʻchirish
53-rasm. Maksimal elementni oʻchirish
struct heapnode heap_extract_max(struct heap
{
if (h->nnodes == 0)
return (struct heapnode){0, NULL};
struct heapnode maxnode = h->nodes[l];
h->nodes[l] = h->nodes[h->nnodes];
h->nnodes--;
heap_heapify(h, 1);
return maxnode;
}
Uyum xususiyatlarini tiklash
void heap_heapify(struct heap *h, int index)
{
for (;;) {
147
int left = 2 * index;
int right = 2 * index + 1;
int largest = index;
if (left <= h->nnodes &&
h->nodes[left].key > h->nodes[index].key)
{ largest = left; }
if (right <= h->nnodes && h->nodes[right].key > h->nodes[largest].key)
{ largest = right; }
if (largest == index)
break;
heap_swap(&h->nodes[index], &h->nodes[largest]);
index = largest;
}
}
Kalit qiymatini oshirish
int heap_increase_key(struct heap *h, int index, int key)
{
if (h->nodes[index].key > key)
return -l;
h->nodes[index].key = key;
for ( ; index > 1 && h->nodes[index].key > h->nodes[index / 2].key; index = index
/ 2)
{
heap_swap(&h->nodes[index], &h->nodes[index / 2]);
}
return index;
}
Binar kucha bilan bilan ishlash
int main()
{
struct heap *h;
struct heapnode node;
h - heap_create(100);
heap_insert(h,
16, "16");
heap_insert(h,
14, "14");
heap_insert(h,
10, ―10");
148
heap_insert(h,
8, "8");
heap_insert(h,
7, "7");
heap_insert(h,
9, ―9");
heap_insert(h,
3, "3");
heap_insert(h,
2, "2");
heap_insert(h,
A, ―4‖);
heap_insert(h,
1, "1");
node = heap_extract_max(h);
printf(―Item: %d\n", node.key);
int i = heap_increase_key(h, 9, 100);
heap_free(h);
return 0;
}
11.2. Uyum (kucha)larni saralash (Heap-Sort)
Heapsort
(Heapsort, "Heap sorting") - n elementlarni saralashda
O(nlogn) amallarda eng yomon, o'rtacha va eng yaxshi (ya'ni
kafolatlangan) holda ishlaydigan saralash algoritmi. Ishlatiladigan
qo'shimcha xotira miqdori massiv kattaligiga bogʻliq emas (ya'ni O (1)).
Ushbu
saralashni
pufaksimon
saralashning
rivojlantirilgan
koʻrinishi deb qarash mumkin.
Eng yomon vaqt -
Eng yaxshi vaqt -
Oʻrtacha vaqt -
Heap-Sort algoritmini realizatsiya qilish (C++)
#include
#include
using namespace std;
int main()
{
srand(time(NULL));
int const n = 100;
int a[n];
149
for ( int i = 0; i < n; ++i )
{
a[i] = rand()%1000;
cout << a[i] << " ";
}
//massivni to'ldirish
//-----------Saralash------------//
//O'sish bo'yicha saralash.
int sh = 0; //смещение
bool b = false;
for(;;) //Sikl cheksiz davom etadi
{
b = false;
for ( int i = 0; i < n; i++ )
{
if( i * 2 + 2 + sh < n )
{
if( ( a[i + sh] > /*<*/ a[i * 2 + 1 + sh] ) || ( a[i + sh] > /*<*/ a[i * 2 + 2 +
sh] ) )
{
if ( a[i * 2 + 1 + sh] < a[i * 2 + 2 + sh] )
{
swap( a[i + sh], a[i * 2 + 1 + sh] );
b = true;
}
else if ( a[i * 2 + 2 + sh] < a[ i * 2 + 1 + sh])
{
swap( a[ i + sh], a[i * 2 + 2 + sh]);
b = true;
}
}
// oxirgi ikki element uchun qo'shimcha tekshirish
// ushbu tekshiruv yordamida siz piramidani saralashingiz mumkin
// faqat uchta elementdan iborat
if( a[i*2 + 2 + sh] < /*>*/ a[i*2 + 1 + sh] )
{
swap( a[i*2+1+sh], a[i * 2 +2+ sh] );
b = true;
}
150
}
else if( i * 2 + 1 + sh < n )
{
if( a[i + sh] > /*<*/ a[ i * 2 + 1 + sh] )
{
swap( a[i + sh], a[i * 2 + 1 + sh] );
b = true;
}
}
}
if (!b) sh++;
if ( sh + 2 == n ) break;
} //Saralash tugatildi
//Natijani chiqarish
cout << endl << endl;
for ( int i = 0; i < n; ++i ) cout << a[i] << " ";
// getch();
return 0;
}
Mavzu yuzasidan savollar:
1. Ustivor navbat nima?
2. Heap-Sort algoritmi haqida gapiring
3. Uyum tushunchasi.
4. Binar kucha bilan ishlash?
5. Ustivor navbat ma‘lumotlar strukturasi qoʻllaniladigan sohalarga
qaysilar kiradi?
Mustaqil ishlash uchun masalalar:
1. Masalalarda Heap-Sort algoritmini qoʻllang.
2. Binar uyumga element qoʻshish dasturini yozing
151
12-§. Hisoblash geometriyasi algoritmlari
Hisoblash geometriyasi
- geometrik masalalarni yechish
algoritmlari bilan shugʻullanadigan informatika bo'limi.
Bu uchburchak, qavariq sirtlarni qurish, bitta obyektning
boshqasiga tegishliligini aniqlash, ularning kesishishini topish va
boshqalar kabi vazifalar bilan shugʻullanadi, ular geometrik obyektlar
bilan ishlaydi: nuqta, segment, ko'pburchak, aylana va hokazolar.
Hisoblash geometriyasi kompyuter grafikalarida, muhandislik
dizaynida va boshqa koʻplab geometriya sohalarida qo'llaniladi.
|
