CP #49: Heap Problemleri

Heap 

• Heap, binary tree'nin ozel bir formudur
• Complete binary tree ozelligi vardir. (Leaf node'lar arasinda en fazla 1 level fark olabilir)
• Heap property: her bir node, kendi child node'larindan daha buyuk olmalidir.
• Max-heap, bir array seklinde de implemente edilebilir. Bu durumda i. node'un child node'lari sirasi ile 2i + 1 ve 2i + 2 olacaktir.
• Insertion: O(log n)
• Max element look-up: O(1) 
• Deletion of the max element: O(log n)
• Ayni zamanda Priority Queue adi da verilmektedir. Cunku max elemani kopardigimizda, siradaki eleman ondan sonra gelen en buyuk eleman olacaktir. Yani Queue gibi davransa da, elemanlarin oncelik sirasi vardir.
• Max-heap yaninda min-heap yapisi da bulunur ki, tamamen ayni ozelliklere sahip olup, max eleman icin degil de min eleman icin calisir.
• Eger sadece en buyuk veya en kucuk elemanla ilgileniyorsak, hizli look-up, arama ve silme islemleri onemli degil ise heap kullanmak iyi bir cozumdur.
• En buyuk veya kucuk k elemanin bulunmasi gibi problemlerde sirasi ile min-heap ve de max-heap kullanmak iyi bir cozumdur.

Python Heapq

• heapq.heapify(L): L arrayindaki elemanlari min-heap olacak sekilde inplace olarak modifiye eder. O(n).
• heapq.nlargest(k, L) veya heapq.nsmallest(k, L): L arrayindan en buyuk veya kucuk k elemani geri dondurur. O(k).
• heapq.heappush(L, e): L arrayi ile temsil edilen heap'e e elemanini push eder O(log k).
• heapq.heappop(L): heap'ten min elemani kopart. O(log k)
• heapq.heappushpop(L, e): elemani heap'e push et ve en kucuk elemani heap'ten kopart. O(log k).
• e = L[0] : kopartmadan, en kucuk elemani gormek. O(1).

Problemlere gecelim.

1. K Longest Strings

Bir stream halinde stringler veriliyor. Ve bunlardan en uzun k adet olanini tutmamiz ve istendiginde dondurmemiz isteniyor. Stringler stream olarak geldigi icin geriye donup okuma sansimiz yok. Stringlerin siralamasi da onemli degil. Sadece o ana kadar gorulen en uzun k stringi nasil tutabiliriz?

Cozum

Ilk 7 strign icin problem yok, bunlarin bir data-structure'a basip saklayabiliriz. Peki 8. string geldiginde ne olacak? Eger bu string, bizdeki en kisa stringden daha uzun ise, elimizdeki en kisa stringi atip, yerine yeni gelen stringi basmamiz gerekiyor. Buradan da gorulecegi gibi min-heap kullanirsak, O(1) maliyeti ile elimizdeki en kisa stringi bulabiliriz. Daha sonra eldeki en kisa elemani min-heap'ten kopartiyoruz, O(log k). Ve de yeni elemani min-heap'e ekliyoruz ki bu da O(log k) maliyete sahip olacaktir.

Eger min-heap yerine bir array kullansaydik ornegin, her adimda min elemani bulmak icin O(k) maliyetimiz olacakti. Min-heap burada ciddi bir performans artisi getiriyor. Simdi implementasyona bir bakalim:

# heapq yapisini import etmemiz gerekiyor

import heapq

def top_k(k: int, stream: Iterator[str]) -> List[str]:

    # heap yapisini bir list ile init ediyoruz.

    # elde mevcut elemanlar var ise, bunlari direk kullanabiliriz

    # bu ornekte stream'den k adet elemani ilk basta okuyup, (uzunluk, string) olacak sekilde

    # tuple'lar halinde array'de tutuyoruz. Uzunluklari onemli cunku min-heap buna gore

    # siralamayi yapacak.

    # python'daki heapq, default olarak min-heap olarak davranmaktadir

    min_heap = [(len(s), s) for s in itertools.islice(stream, k)]

    # heapq'ya bu listi verip, heap olusturmasini soyluyoruz

    heapq.heapify(min_heap)

    

    # stream'den yeni eleman geldikce heap'e basiyoruz

    for next_string in stream:

        # bu metod sayesinde next_string direk min-heap'e push ediliyor ve

        # minimum eleman heap'ten pop ediliyor. 

        # min-heap, ilk basta kac eleman ile heapify edildi ise onu koruyor 

        heapq.heappushpop((len(next_string), next_string))

    # stream bitince de eldeki k elemani donduruyoruz

    return [p[1] for p in heapq.nsmallest(k, min_heap)]

Hatta burada heapq.heappushpop yapmadan once (cunku bunun maliyeti O(log k)), next_string'in bizim elimizdeki en kucuk stringden daha uzun olup olmadigina bakabiliriz. En kisa stringi koparmadan bakmak icin min_heap arrayinin ilk elemanina bakmak yeterli olacaktir. Bu sayede bagzi adimlarda O(log k) yerine O(1) ile bu adimi gecebiliriz. Bu da average time compl. artirmasa da, best case time compl.'ye olumlu katki saglayacaktir. Best case'de, stream'deki ilk 7 string en uzun olup diger tamami bunlardan kisa olur ise, her adimda sadece O(1) ile kontrol kismi atlatilir ve sonuc olarak O(1) cozum elde edilir.

2. Merge Sorted Files

Elimizde cok sayida ordered items iceren dosyalar var. Bunlari birlestirip tek bir dosya yapmamiz gerekiyor. Bunu yapabiliriz? 

Cozum

Ozetle, kendi iclerinde sorted olan birden fazla sequence veriliyor ve bunlari da sorted bir sekilde birlestirmemiz isteniyor. Naive yontemle, tamamini tek bir list seklinde birlestirip, sort edebiliriz. Hepsini birlestirmek toplamdaki eleman sayisi n ise O(n) zaman alacaktir. Bunlari sort etmek de O(n logn) zaman alacagindan toplamda cozum O(n logn) maliyete sahip olacaktir. 

Bu cozumde neyi kullanmadik? Arraylarin zaten sorted oldugu bilgisini. Biz array'larin herbirinin ilk elamnini alip bir min-heap'e basarsak, daha sonra buradan en kucuk elemani pop edip sonuc arrayina basarsak ve bu islemi tum arraylar bitene kadar yaparsak, sonunda sorted bir array elde etmis oluruz. Elimizde k adet dosya var ise, min-heap eleman sayisi her adimda k adet olacagindan, yeni bir eleman basip en kucuk elemani pop etmek O(log k) maliyet alacaktir. Yani toplamda O(n logk) maliyete sahip bir cozum uretecegiz. Onceki O(n logn) ile kiyaslandiginda, dosya sayisi k'ya bagli olarak bir performans artisi sozkonusu olacaktir. 

import heapq

def merge_sorted_arrays(sorted_arrays: List[List[int]]) -> List[int]:

    # min-heap olarak kullanacagimiz array

    L = []

    # enson birlestirilmis sorted array

    ret = []

    # ilk once herbir sorted list'in ilk elemanini L'ye basiyoruz

    # sonra min-heap olusturacagiz

    # min-heap'te 3lu tuple tutacagiz: ilk eleman, index ve iterator

    # eger ilk elemanlar ayni ise, min-heap yine de bir siralama bekleyecektir

    # bu siralamayi da surekli artan bir index (burada L'nin lengthini kullandik) ile

    # cozebiliriz

    for sorted_arr in sorted_arrays:

        iterator = iter(sorted_arr)

        L.append((next(iterator, None), len(L), iterator))

    heapq.heapify(L)

    # simdi L icerisinde eleman oldugu surece devam edecegiz

    while L:

        min_elm_in_heapq, iterator = heapq.heappop(L)

        ret.append(min_elm_in_heapq)

        next_elm = next(iterator, None)

        

        # burada direk None kontrolu yapmak gerekiyor

        # eger if next_elm: diyip birakirsak, next_elm sifir degerine sahip ise

        # bunu islemiyor olacagiz demektir

        if next_elm is not None:

            heapq.heappush((next_elm, len(L) + len(ret), iterator))

    return ret

Bakacak olursa, bize verilen sorted array sayisi k ise, min-heap icerisinde en fazla k adet eleman olacaktir. Her bir min_heap push ve pop islemini O(log k) maliyetinde oldugu dusunulurse, toplamda merge islemi O(n logk) olacaktir. Ekstra space olarak da O(k) kullandik diyebiliriz.

3. Sort An Increasing-Decreasing Array 

Bir arrayin elemanlari, verilen bir k index degeri icerisinde artip sonra tekrar azaliyorsa, buna k-increasing-decreasing array adi verilir. Boyle bir arrayi sort edecek bir algoritma tasarlayiniz. 

Ornek: Burada k=4 icin bir increasing-decreasing array gosterilmistir. Yani en fazla 4 eleman boyunca array artan sekilde davraniyor daha sonra da en fazla 4 eleman boyunca azalan sekilde davraniyor.

Cozum 

Naive cozumde butun arrayi alip direk sort edebiliriz ki O(n logn) maliyete sahip olacaktir. Ya da, arrayi monotonik olarak artan ve azalan parcalara bolup, bunlari bir onceki problemde oldugu gibi, birden fazla sorted arrayi birlestirme mantigi ile birlestirebiliriz. Tabi oncelikle monotonik azalan arraylari reverse etmemiz ve artan hale getirmemiz gerekir. 

Arrayi bastan sona pass ederek, O(n), artan ve azalan parcalari tespit edebliriz. Reverse islmei de yine lineer olacaktir ama arrayin taamini kapsamayacaktir. 

import heapq

def sort_k_increasing_decreasing_array(A: List[int]) -> List[int]:

    # once arrayi monotonik artan/azalan parcaciklara bolecegiz

    # bunun icin arrayin sifirinci degil de 1. elemaninda baslayarak

    # surekli bir gerideki elemanla, suandaki elemani kiyaslayarak,

    # yukari yonde mi (artan), asagi yonde mi (azalan) gittigimizi kontrol edecegiz

    direction = None

    # artan parcalari tutacagimiz array

    increasing = []

    # azalan parcalar

    decreasing = []

    cur_seq = []

    for i in range(1, len(A)):

        cur_dir = A[i-1] < A[i]

        # eger yon degisti ise, yeni bir array parcacigina baslamak gerek

        # mevcut olani da onceki direction'a gore increasing ya da decreasinge

        # ekleyecegiz.

        if cur_dir != direction:

            if cur_seq:

                if direction:

                    increasing.append(cur_seq[:])

                else:

                    decreasing.append(cur_seq[:])

            

            cur_seq = [A[i]]

        else:

            # eger yon degismedi ise, gelen elemani mevcut cur_seq'e ekle

            cur_seq.append(A[i])

    # burada array bittiginde elimizde eger hala cur_seq icerisinde eleman var ise

    # bunu da bir yere eklememiz gerekiyor

    if cur_seq:

        if direction:

                increasing.append(cur_seq[:])

        else:

                decreasing.append(cur_seq[:])

    # decreasing olanlari ters ceviriyoruz

    for i in range(len(dereasing)):

        decreasing[i] = reversed(decreasing[i])

    # merge-k-sorted-array kismina geldik

    L = []

    # min-heap'i hazirlayalim

    for arr in increasing + decreasing:

        iterator = iter(arr)

        L.append((next(iterator, None), len(L), iterator))

    heapq.heapify(L)

    ret = []

    while L:

        min_elm, iterator = heapq.heappop(L)

        ret.append(min_elm)

        next_elm = next(iterator, None)

        if next_elm is not None:

            heapq.heappush(L, (next_elm, len(L) + len(ret), iterator))

    return ret

Aslinda basit bir cozum olmakla beraber birkac edge-case can sikici olabiliyor. Neyse, bakacak olur isek, ilk once O(n) bir iterasyon ile arrayi artan ve azalan parcaciklara ayirdik. Bu islem sirasinda cur_seq arrayini kopyaliyoruz. Eger cur_arr uzunlugu p iser bu da O(p) bir islem. Ancak soyle dusunulebilir, toplamda butun parcalama islemi bittiginde, hicbir zaman bir elemani birden fazla kez kopyalamiyoruz. Bu da demek oluyor ki tum arrayi bir kere kopyalamisiz. Yani O(n) time compl. sahip. 

Sonrasi zaten malum, merge-k-sorted-arrays problemi. Yine min-heap yontemini kullandik ve artan/azalan parcacik sayisi k ise, toplamda O(n logk) maliyetinde bir cozum elde ettik. Ekstra hafiza olarak da, O(n) kullandigimizi soyleyebiliriz cunku orjinal array'deki tum elemanlari bir kere olmak uzere artan/azalan array parcalarindan birisine kopyaladik. 

4. Sort An Almost Sorted Array

Elimizde neredeyse sort edilmis bir array var. Hic bir eleman, gercek sorted halinde olmasi gereken pozisyondan k'dan fazla uzakta degil. Boyle bir arrayi sort eden bir algoritma tasarlayiniz. 

Ornek:
k = 2,  array = 3, -1, 2, 6, 4, 5, 8 

Cozum

Demek ki biz verilen sequence uzerinde k uzunlugunda bir window gezdirip, bu window icerisini sadece sort edersek, cozume ulasmis olacagiz. Ne de olsa hicbir eleman olmasi gereken yerden k'dan daha uzak degil. Yine bu eldeki k adet elemani, sliding window ile sort etmek icin, min-heap yapisi kullanabiliriz. Soyle dusunelim, verilen sequence'den k adet elemani direk heap'e basiyoruz. Daha sonra, yeni eleman geldikce, once heapten minimum elemani kopartip, return arrayina ekliyoruz, daha sonra da sequence'den gelen yeni elemani heap'e basiyoruz. Bu durumda k adet eleman surekli sorted sekilde kalmis oluyor. Sequence bittigi zaman da, heap icerisinde kalmis olan elemanlari da bitene kadar kopartip return arrayina ekliyoruz ve donduruyoruz. Sonucta her bir heap push islemi O(log k) maliyete sahip. Sequence icerisinde n eleman oldugu kabul edilirse toplamda O(n logk) gibi efektif bir cozum olacak. Naive cozumde sequence bitene kadar elemanlari kopartirp, bir arrayda toplayip direk sort edip dondurebilirdik ki O(n logn) gib bir maliyeti olurdu. 

import heapq

def sort_almost_sorted_array(sequence: Iterator[int], k: int) -> List[int]:

    L = []

    ret = []

    

    # ilk once k adet elemani arraye basip heap'e cevirecegiz

    # burada tabi ki seq icerisinde min k eleman oldugunu kabul ediyoruz

    for _ in range(k):

        L.append(next(sequence, None))

    heapq.heapify(L)

    # seq bitene kadar mokoko

    while True:

        min_elm = heapq.heappop(L)

        ret.append(min_elm)

        next_elm = next(seqeuence, None)

        

        # seq bitti mi?

        if next_elm is not None:

            heapq.heappush(L, next_elm)

        else:

            # seq bitti, heap icerisinde kalan elemanlari da

            # ret'e basiyoruz

            while L:

                ret.append(heapq.heappop(L))

            return ret

Analizini de yukarida yapmistik, toplamda O(n logk) time compl var. Space kullanimi olarak ret var O(n), ayrica heap icin de O(k) kullandik. Toplamda O(n + k) diyebiliriz.

5. Compute The K Closest Stars

Samanyolu galaksisinde 10^12 adet yildiz oldugu biliniyor. Herbir yildizin konumu da 3 boyutlu duzlemde (x,y,z) seklinde bir nokta ile belirleniyor. Dunya merkezde olmak uzere (yani (0,0,0) noktasinda), dunyaya en yakin k yildizi bulunuz. 

Cozum

Yine cok benzer bir problem ile karsi karsiyayiz. 10^12 adet yildiz falan var diyerek yapilan show aslinda bize sunu soyluyor, bunu alip direk sort etme. K tanesi lazim bana, distance degeri en kucuk olan k tanesini getir yeter. Burada tabi heap devreye giriyor. Kucuk bir twist var burada, bize en yakin olanlar lazim oldugu icin, her yeni yildizi kontrol ettigimizde (sonuca hepsini bir kere kontrol etmemiz gerekiyor, muneccim degiliz), eldeki k adet icerisinden en uzak olanini atmamiz gerekli. Tum yildizlari itere ettikten sonra heap icerisinde kalanlar en yakin olanlar olacaktir. Her adimda, k eleman icerisinden en uzak olani bulabilmek icin max-heap kullanmak gerek. 

Python'daki heapq sadece min-heap seklinde calistigi icin, uzaklik degerlerini -1 ile carparak eklersek max-heap gibi davranmis olur. 

import heapq

def fin_closest_k_stars(stars: Iterator[Star], k:int) -> List[Star]:

    # yine ilk k elemani heape basarak basliyoruz

    L = []

    for _ in range(k):

        star = next(stars, None)

        L.append((-1 * star.distance, star))

    heapq.heapify(L)

    while True:

        # once bakalim baska eleman var mi?

        # egere stars icerisinde k adet eleman var ise

        # ve biz once direk pop edersek, bir eleman az sonuc dondurmus oluruz ki

        # yanlis olur. bize yakismaz.

        next_star = next(stars, None)

        

        if next_star is not None:

            # simdi eldeki k eleman icinden en uzak olanini

            # def ediyoruz ve yerine geleni ekliyoruz

            heapq.heappushpop(L, (-1 * next_star.distance, star))

        else:

            # yildizlar bitti, heap icerisinden sadece yildizlari ayiklayip

            # return ediyoruz

            return list(map(lambda x: x[1], L))

Onceki problemlere benzer sekilde time compl. O(n logk). Ve eger geri donus arrayini saymaz isek, ekstra hafiza kullanimi da sadece heap'ten dolyi O(k). 

Post cok uzadi arkadaslar, gelecek problemlerde gorusmek uzere.