heapq: Python’da heap veri yapısı

Heap veri yapıları, kısaca tanımlamak gerekirse, her node’un kendi çocuklarından daha büyük değere (ya da daha büyük önceliğe) sahip olduğu, ağaç veri yapılarıdır denilebilir. Aşağıdaki örnekte bu sıralama küçükten büyüğe yapılmıştır.

300px-binary-heap

 

Heap’ler, diğer algoritmalardaki (örneğin Dijkstra) kullanımlarının dışında, PriorityQueue gibi veri yapılarında da kullanılır.

Heap üzerinde kullanabileceğimiz işlemler aslında temelde 3 adettir;

  • heapify: Bir diziyi heap özelliğini sağlar hale, yani her elemanı kendi çocuklarından büyük olduğu duruma getirir.
  • pop: En büyük elemanı döner.
  • push: Heap’e yeni bir eleman ekler.

Python’da bu 3 işlevi karşılayan ve heap işlemlerini gayet kolayca yapmamızı sağlayan heapq adında bir modül mevcut. Modül epey küçük, testiyle commentiyle 500 satır falan ama graph algoritmalarıyla falan uğraşıyorsanız gayet gereksiz bir ayrıntıdan sizi çok güzel kurtarıyor.

Modülün içindeki tüm metodlar dışarıdan verilen bir dizi üzerinde çalışıyor. Bilinmesi gereken bir ayrıntı, dizide eğer primitive tipler ya da tuple’lar tutmuyorsak, yani kendi yazdığımız bir sınıftan nesnelerin bir arrayini heap’e çevirmeye çalışıyorsak, sınıf içinde __lt__ metodunun yazılması gerekiyor.

Örneğin yukarıdaki resimdeki dizinin orijinal halinin [10, 7, 9, 2, 1, 8] şeklinde olduğunu düşünelim.

 

 

Bu diziyi heap haline getirmek için heapify metodunu kullanıyoruz. Bu metod diziyi bir heap’e çeviriyor, görüldüğü gibi her n. eleman 2*n ve 2*n+1 elemandan daha küçük (heapq heap’lerinin değişik bir tarafı min-heap olması yani diziyi küçükten büyüğe sıralaması).

 

Dizinin en küçük yani en önemli elemanını almak için heappop metodunu kullanıyoruz. Normalde bu elemana arr[0] şeklinde de erişebiliriz ama bu metod ilk elemanı heapten çıkarıp heap’i tekrar düzenliyor.

 

Heap’e eleman eklemek için ise heappush metodunu kullanıyoruz.

 

heapq’da, tüm işimizi görecek bu temel metodların dışında, nlargest, nsmallest, heappushandpop gibi işimizi kolaylaştıran ve temel metodları kullanarak yapılabilecek metodlar da mevcut.

Kısa bir soru

Arada bir teknik mülakatların sorularını inceliyorum. Bazıları basit olsa da nedense bir hoşuma gidiyor. Bu da onlardan bir tanesi :)

Bu soruyla bir tane teknik mülakatta karşılaşmıştım. Sonrasında mülakat sorularını incelerken bir yerde daha denk geldim. Sorunun kendisi gayet kısa, verilen bir dizide toplamları N’e eşit olan alt dizilerin sayılarının bulunması isteniyor.

Misal elimizdeki dizi [1, 23, -5, 7, 21, 3, 3, 2, -5], toplam olarak istenen N değeri de 23 olsun.

En basit çözüm olarak aşağıdaki çözüm verilebilir.

 

Bu çözüm tüm index çiftleri için toplamı hesaplayıp, toplam N’e eşitse sonucu 1 arttırıyor. O(n^3)‘lük bir çözüm, bu yüzden büyük diziler için çok da güzel bir çözüm değil. Aşağıdaki çözüm ise kümülatif toplamları tuttuğundan çözümü en içteki for’dan kurtarıyor ve complexity O(n^2) oluyor.

 

Bu iki çözümü de O(n)‘e yaklaştırmak istiyoruz. Kümülatif toplamları hesapladığımıza göre, totals dizisinin i. elemanı için yapmamız gereken (aslında 2. çözümde de yaptığımız) kümülatif toplamı totals[i] – N olan elemanların sayısını bulmak. Bunun içinse tekrar tekrar lineer arama yapmamıza gerek yok.

 

Son çözümde, her kümülatif toplamdan önceki toplamları bir hashtable’da tuttuk. Böylece, istenen değerlerinin sayısını O(1) zamanda hesaplayabiliyoruz. O(n) zaman da diziyi dolaşmakla geçiyor ve son çözümün complexity’si O(n) oluyor.

Umarım bir hata yapmamışımdır :)