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.