4. Dinamik ma‟lumotlar tuzilmasi haqida ma’lumot bering

16 * 2 ^ 30/52 ≈ 330,382,099 ta tugun

1.000.000.000 yozuvlardan iborat lug'atni qanday saqlash kerak?

• 
  Facebook foydalanuvchilari soni (2013 yil iyul):
  
• 
  1 200 000 000
  
• 
  Google Gmail foydalanuvchilari soni (2012 yil iyun):
  
• 
  425,000,000
  
• 
  VKontakte foydalanuvchilari soni (2013 yil fevral):
  
• 
  43,000,000
  
• 
  Yechim: tashqi xotiradan foydalaning - HDD / SSD disklari, tarmoq xotirasi
  

68. B-daraxtlar ustida amallar haqida tushuncha bering.
B-daraxtlar ustida amallar
 Barcha amallarda biz quyidagilarni qabul qilamiz:
- B daraxtining ildizi doimo operativ xotirada bo'ladi
- DiskRead va DiskWrite protseduralari diskka ma'lumotlarni o'qish va yozish uchun ishlatiladi
B daraxti tashqi xotiraga murojaatlar sonini minimallashtiradi (DiskRead, DiskWrite-ga)
69. Heapsort algoritmi haqida tushuncha bering.

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

#include
#include

using namespace std;

int main()

{
srand(time(NULL));
int const n = 100;
int a[n];
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;
}
}
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;
}