Ustuvor navbatlarni piramida orqali qurish stl da ustuvor navbatlar Piramidaviy saralash

Piramidaviy saralash

Piramidaviy saralash (ing. heapsort) – tanlash orqali saralashning takomillashtirilgan varsiyasi. Oddiy tanlash orqali saralash N marta berilgan massivdan kichik element yechib olinadi va munosib joyga joylashtirilishga asoslangan. Agar kichik elementni tanlash uchun ketma-ket qidirishdan foydalanilsa, u holda har safar butun massiv ko’rib chiqiladi. Bu esa har bir iteratsiyaga O(N) murakkablik beradi va umumiy murakkablik O(N²) ga teng bo’ladi.

Kichik elementni izlashda ketma-ket qidiruv o’rniga piramidadan foydalanish mumkin, u har bir qadamda minimal elementni O(1) bilan yechib olishni va O(logN) bilan qayta tiklanishni beradi. Bundan kelib chiqadiki, umumiy murakkablik O(NlogN) ga teng bo’ladi. Piramidaning aralashtirmaslik uchun o’zini har bir qadamda maksimal elementni yechib olib va uni oxiriga qo’shish mumkin. Piramidani berilgan bo’sh bo’lmagan massivda hosil qilishni ikkita usuli mavjud:

• 
  Boshidan oxirigacha ko’rib chiqib, ketma-ket ravishta har bir element uchun up() (odatda ustuvor navbatni massivning har bir elementiga enqueue() amalini qo’llagan holda qurishga o’xshash) amalini qo’llab. Murakkablik O(NlogN);
  
• 
  Piramidani “pastdan yuqoriga” tarzida qurish, down() protsedurasini barcha element uchun chaqirgan holda massivning oxiridan boshigacha ko’rib chiqib. down() ni yaproqlar uchun chaqirish hech qanday o’zgarishga olib kelmaydi, shuning uchun siklni (size/2-1) dan boshlasa ham bo’ladi. Bir qancha manbalarda, shuningdek T. Kormenning “Алгоритмы: построение и анализ” kitobida ham ushbu metodning murakkabligi O(N) gacha kamayishi ko’rsatilgan.
  

down() funksiyasi unga parametrlar orqali berilgan a[] va size qiymatlaridan foydalansin. U holda piramidaviy saralash quyidagi ko’rinishga ega bo’ladi:

void heapsort(int a[], int size) {

for (int i = size / 2 - 1; i >= 0; i--)

down(a, size, i);

for (int i = 0; i < size; i++) {

swap(a[0], a[size - 1 - i];

down(a, size - i, 0);

}

}

Piramidaviy saralashning xususiyatlari:

• 
  Murakkablik O(NlogN);
  
• 
  Tanlash orqali saralash kabi qo’shimcha hotira talab qilmaydi, misol uchun surish orqali saralashdan farqli ravishta;
  
• 
  Tanlash orqali saralash kabi barqaror emas (masalan, sonlar kalit hisoblangan [1-a,1-b] massiv, saralashdan so’ng [1-b,1-a] ko’rinishiga ega bo’ladi);
  
• 
  Tanlash orqali saralash kabi moslashuvchan emas.