Kampyuter injenering fakulteti 961-19 gurux 3-kurs talabasi Arslanov Sarvarning Ma’lumotlar tuzilmasi va algoritm fanidan

Kiriting, so'ng chiqarib oling

Keyin elementni qo'shib qo'yish, yuqoriga ko'tarish va tushirish operatsiyasini o'z ichiga oladigan, yuqorida tavsiflangan kiritish va ajratish funktsiyalarini chaqirishdan ko'ra samaraliroq bo'lishi mumkin. Buning o'rniga, biz faqat pastga tushirish operatsiyasini bajarishimiz mumkin:

1. 
   Biz surayotgan narsaning yoki uyumning yuqoridan yuqorisining kattaroqligini taqqoslang (maksimal yig'ishni nazarda tutib)
   
2. 
   Agar uyumning ildizi kattaroq bo'lsa:
   
   1. 
      Ildizni yangi element bilan almashtiring
      
   2. 
      Ildizdan boshlab pastga tushirish
      
3. 
   Aks holda, biz surayotgan buyumni qaytaring
   

Python kiritish uchun shunday funktsiyani taqdim etadi, so'ngra ekstraktsiya "heappushpop" deb nomlanadi, bu quyida keltirilgan.^[6][7] Uyma massiv birinchi indeksda birinchi elementga ega deb qabul qilinadi.

// Yangi buyumni (max) uyumga suring, so'ngra hosil bo'lgan uyumning ildizini ajratib oling. // uyum: massivni ifodalovchi massiv, 1 // da indekslangan element: kiritish uchun element // Ikkisining kattasini qaytaradi element va ning ildizi uyum.Push-Pop(uyum: ro'yxati, element: T) -> T: agar uyum bo'sh emas va uyum [1]> element keyin: // almashtirish uyum[1] va element _downheap (uyum indeksdan boshlab 1) qaytish element

Python-da "heapreplace" deb ataladigan ochilish va keyin kiritish uchun shunga o'xshash funktsiyani aniqlash mumkin:

// Uyumning ildizini ajratib oling va yangi elementni itaring // uyum: massivni ifodalovchi massiv, 1 // da indekslangan element: kiritish uchun element // ning joriy ildizini qaytaradi uyumO'zgartiring(uyum: ro'yxati, element: T) -> T: almashtirish uyum[1] va element _downheap (uyum indeksdan boshlab 1) qaytish element

Qidirmoq

Ixtiyoriy elementni topish O (n) vaqtni oladi.