Priority queues and heapsort

Hazırlık: en büyük çift toplamını en aza indirecek biçimde sayıları eşleştirme

Given 2n numbers, split them into n pairs so that the largest pair sum is as small as possible. For (1, 3, 5, 9) the options are pairs summing to (4, 14), (6, 12) or (10, 8); the last one is best, with a maximum of 10.

Verilen 2n sayıyı, en büyük çift toplamı mümkün olduğunca küçük olacak biçimde n çifte ayırın. (1, 3, 5, 9) için seçenekler, toplamları (4, 14), (6, 12) veya (10, 8) olan çiftlerdir. Maksimumu 10 olan son seçenek en iyisidir.

The O(n log n) answer: sort the numbers, then pair the smallest with the largest, the second smallest with the second largest, and so on. Every big number is “cushioned” by a small one. Sorting costs O(n log n) and the pairing is a single O(n) pass.

O(n log n) çözümü: sayıları sıralayın; ardından en küçüğü en büyükle, ikinci en küçüğü ikinci en büyükle eşleştirin ve sürdürün. Her büyük sayı, küçük bir sayıyla “dengelenir”. Sıralama O(n log n) tutar; eşleştirme ise tek bir O(n) taramadır.

Sıralama neden bu kadar önemlidir?

Computers spend a great deal of their time sorting; historically about a quarter of mainframe cycles.

Bilgisayarlar zamanlarının önemli bir kısmını sıralamaya harcar; tarihsel olarak ana bilgisayar işlem çevrimlerinin yaklaşık dörtte biri buna ayrılmıştır.

Sorting is the most thoroughly studied problem in computer science, with many known algorithms.

Sıralama, birçok bilinen algoritmasıyla bilgisayar bilimlerinde en ayrıntılı incelenmiş problemdir.

Most of the big ideas of this course (divide and conquer, randomised algorithms, lower bounds) can be taught in the context of sorting.

Bu dersin büyük fikirlerinin çoğu (böl ve yönet, rastgeleleştirilmiş algoritmalar, alt sınırlar) sıralama bağlamında öğretilebilir.

Once data is sorted, lots of other problems become easy, and an O(n log n) sort leads directly to sub-quadratic algorithms for them.

Veriler sıralandığında birçok başka problem kolaylaşır; O(n log n) maliyetli bir sıralama, doğrudan bu problemler için karesel-altı algoritmalara götürür.

The gap between quadratic and n log n sorting is enormous:

Karesel sıralama ile n log n sıralama arasındaki fark çok büyüktür:

Large-scale data processing is impossible with an Ω(n²) sort.

Ω(n²) maliyetli bir sıralamayla büyük ölçekli veri işleme mümkün değildir.

Sıralamanın uygulamadaki ayrıntıları

Comparison functions. “Sorted” only means something once you say what “before” means. Is Skiena the same key as skiena? Does Brown-Williams come before or after Brown, John? Increasing or decreasing? All of this is decided by the comparison function given to the sorting routine, which is asked “does x come before y?” for pairs of items.

Karşılaştırma fonksiyonları. “Sıralı” ancak “önce”nin ne anlama geldiği söylendiğinde anlam kazanır. Skiena ile skiena aynı anahtar mıdır? Brown-Williams, Brown, John’dan önce mi sonra mı gelir? Artan mı, azalan mı? Bütün bunları, sıralama yordamına verilen ve eleman çiftleri için “x, y’den önce mi gelir?” sorusunu yanıtlayan karşılaştırma fonksiyonu belirler.

Equal elements. Items with equal keys end up next to each other, but their relative order may matter (sort by surname, then by first name). Secondary keys belong in the comparison function. Some algorithms, quicksort in particular, need care to stay fast when there are many equal keys.

Eşit elemanlar. Eşit anahtarlı elemanlar yan yana gelir, ancak kendi aralarındaki göreli sıra önemli olabilir (önce soyadına, sonra ada göre sıralama). İkincil anahtarlar karşılaştırma fonksiyonunda yer almalıdır. Bazı algoritmalarda, özellikle hızlı sıralamada, çok sayıda eşit anahtar varken hızın korunması için dikkat gerekir.

Library functions. Every serious language has a built-in sort (C’s qsort, for example). You are almost always better off calling it than writing your own.

Kütüphane fonksiyonları. Her ciddi dilin yerleşik bir sıralama yordamı vardır (örneğin C’de qsort). Kendi yordamınızı yazmak yerine bunu çağırmak neredeyse her zaman daha iyidir.

Sıralama neleri kolaylaştırır?

Seçmeli sıralamaya yeniden bakış: veri yapısı önemlidir

Selection sort (Lecture 3) is really a loop of two operations, done n times:

Seçmeli sıralama (Ders 3), gerçekte n kez yapılan iki işlemden oluşan bir döngüdür:

A: find the smallest of the remaining items;

A: kalan elemanların en küçüğünü bul;

B: pull it out and put it next.

B: onu çıkar ve sıradaki yere koy.

So it costs O(n × (cost of A + cost of B)). With an array or unsorted list, A is O(n) and B is O(1): total O(n²). With a balanced search tree or a heap, both A and B are O(log n): total O(n log n). That algorithm is heapsort. The key question to ask whenever an algorithm is slow: “can we use a different data structure?”

Dolayısıyla maliyeti O(n × (A’nın maliyeti + B’nin maliyeti)) olur. Dizi veya sırasız listeyle A, O(n); B, O(1)’dir: toplam O(n²). Dengeli arama ağacı veya öbekle hem A hem B, O(log n)’dir: toplam O(n log n). Bu algoritma öbek sıralamasıdır. Bir algoritma yavaş olduğunda sorulacak temel soru: “Farklı bir veri yapısı kullanabilir miyiz?”

Öncelik kuyrukları

A priority queue is a container that supports three operations:

Öncelik kuyruğu, üç işlemi destekleyen bir kapsayıcı yapıdır:

Insert(Q, x): add item x with its key.

Insert(Q, x): x elemanını anahtarıyla birlikte ekle.

Find-Minimum(Q) (or Find-Maximum): return the item with the smallest (largest) key.

Find-Minimum(Q) (veya Find-Maximum): en küçük (en büyük) anahtarlı elemanı döndür.

Delete-Minimum(Q) (or Delete-Maximum): remove that item.

Delete-Minimum(Q) (veya Delete-Maximum): bu elemanı kaldır.

Each can be done in O(log n) using a heap or a balanced binary tree. The reason to want a priority queue rather than sorting once is that jobs arrive at arbitrary times: inserting a new job is far cheaper than re-sorting everything.

Her biri öbek veya dengeli ikili ağaç kullanılarak O(log n) sürede yapılabilir. Bir kez sıralamak yerine öncelik kuyruğu istememizin nedeni, işlerin gelişigüzel zamanlarda gelmesidir: yeni bir iş eklemek, her şeyi yeniden sıralamaktan çok daha ucuzdur.

Two of Skiena’s applications: a dating queue (retrieve people by desirability, not by name; scores change so you re-insert with the new score; nobody needs deleting until they reach the top) and discrete event simulation (airports, parking lots: whichever event is scheduled soonest happens next). A stack and a queue are just special cases where the priority is arrival time.

Skiena’nın iki uygulaması: bir flört kuyruğu (kişileri adlarına değil, ne kadar arzu edildiklerine göre getir; puanlar değiştiğinden yeni puanla yeniden ekle; tepeye ulaşana kadar kimseyi silmeye gerek yoktur) ve ayrık olay benzetimi (havaalanları, otoparklar: hangi olay en erken zamana planlandıysa sırada o gerçekleşir). Yığın ve kuyruk, önceliğin geliş zamanı olduğu özel durumlardır.

Öbekler (heaps)

A binary heap is a binary tree with a key in each node such that:

İkili öbek, her düğümünde bir anahtar bulunan ve şu koşulları sağlayan ikili ağaçtır:

All leaves are on at most two adjacent levels.

Bütün yapraklar en fazla iki komşu düzeyde bulunur.

All levels except the lowest are completely full, and the leaves on the lowest level are packed to the left.

En alt düzey dışındaki bütün düzeyler tamamen doludur; en alt düzeydeki yapraklar sola yaslanmıştır.

The key in each node is ≤ the keys of its children, and the left and right subtrees are themselves heaps. (This is a min-heap; flip the inequality for a max-heap.)

Her düğümün anahtarı çocuklarının anahtarlarından ≤ büyüklüğündedir; sol ve sağ alt ağaçların kendileri de öbektir. (Bu bir minimum öbektir; maksimum öbek için eşitsizliği ters çevirin.)

Rules 1 and 2 fix the shape of the tree; rule 3 is the labelling. The labelling rule imposes a partial order: weaker than sorted order (so it is cheap to maintain) but stronger than random order (so the minimum can be found instantly; it is always the root).

1. ve 2. kurallar ağacın biçimini belirler; 3. kural etiketlemeye ilişkindir. Etiketleme kuralı bir kısmi sıra dayatır: sıralı düzenden daha zayıftır (dolayısıyla sürdürülmesi ucuzdur), fakat rastgele düzenden daha güçlüdür (dolayısıyla minimum anında bulunur; her zaman köktedir).

Storing a heap in an array. Because the shape is so regular, no pointers are needed. Number the nodes level by level from 1. Then:

Öbeği dizide saklama. Biçim çok düzenli olduğundan işaretçi gerekmez. Düğümleri 1’den başlayarak düzey düzey numaralandırın. O zaman:

the left child of node k is at position 2k;

k düğümünün sol çocuğu 2k konumundadır;

the right child is at position 2k + 1;

sağ çocuğu 2k + 1 konumundadır;

the parent of node k is at position ⌊k/2⌋.

k düğümünün ebeveyni ⌊k/2⌋ konumundadır.

The slides’ example is a heap of years: 1492 at the root, children 1783 and 1776, grandchildren 1804, 1865, 1945, 1963, and so on; as an array it reads 1492, 1783, 1776, 1804, 1865, 1945, 1963, 1918, 2001, 1941. This implicit layout only works because the tree is nearly full; a sparse tree would waste every missing slot, which is exactly why rules 1 and 2 are insisted upon. The trade-off is flexibility: an array-based tree cannot be restructured as freely as a pointer-based one.

Slaytlardaki örnek yıllardan oluşan bir öbektir: kökte 1492; çocukları 1783 ve 1776; torunları 1804, 1865, 1945, 1963 vb. Dizide 1492, 1783, 1776, 1804, 1865, 1945, 1963, 1918, 2001, 1941 biçiminde görünür. Bu örtük yerleşim yalnızca ağaç neredeyse dolu olduğu için çalışır; seyrek bir ağaçta her eksik göz boşa giderdi. 1. ve 2. kurallarda ısrar edilmesinin nedeni tam olarak budur. Ödün verilen özellik esnekliktir: dizi tabanlı bir ağaç, işaretçi tabanlı bir ağaç kadar serbestçe yeniden yapılandırılamaz.

Height. A heap of n items has height ⌊lg n⌋, because all levels but the last are full and 1 + 2 + 4 + … + 2ʰ = 2ʰ⁺¹ − 1 ≥ n.

Yükseklik. n elemanlı bir öbeğin yüksekliği ⌊lg n⌋’dir; çünkü son düzey dışındaki bütün düzeyler doludur ve 1 + 2 + 4 + … + 2ʰ = 2ʰ⁺¹ − 1 ≥ n.

Ekleme: yukarı taşıma (bubble up)

Put the new item in the leftmost open slot (position n + 1). It may now be smaller than its parent, breaking rule 3. Fix it by swapping with the parent, and repeat upward until the parent is smaller or the root is reached:

Yeni elemanı en soldaki boş göze (n + 1 konumu) koyun. Eleman artık ebeveyninden küçük olabilir; bu, 3. kuralı bozar. Ebeveyniyle yer değiştirerek düzeltin; ebeveyni daha küçük olana veya köke ulaşana kadar yukarı doğru tekrarlayın:

insert(Q, x):
    n = n + 1
    Q[n] = x
    bubble_up(Q, n)

bubble_up(Q, p):
    if p is the root: return
    if Q[parent(p)] > Q[p]:
        swap Q[p] and Q[parent(p)]
        bubble_up(Q, parent(p))

insert(Q, x):
    n = n + 1
    Q[n] = x
    bubble_up(Q, n)

bubble_up(Q, p):
    if p kök ise: return
    if Q[parent(p)] > Q[p]:
        Q[p] ile Q[parent(p)] yer değiştir
        bubble_up(Q, parent(p))

Each swap moves the item one level up, so insertion costs O(log n). Building a heap by n insertions therefore costs Θ(n log n): the last n/2 insertions each cost about lg n.

Her yer değiştirme elemanı bir düzey yukarı taşır; bu yüzden ekleme O(log n) tutar. Dolayısıyla n eklemeyle öbek kurmak Θ(n log n) maliyetlidir: son n/2 eklemenin her biri yaklaşık lg n tutar.

Minimumu çıkarma: aşağı taşıma (bubble down)

The minimum is the root. Remove it, move the last item of the array into the root slot (keeping the shape rules intact), then repair rule 3 downward: compare the node with its two children, swap with the smaller child if that child is smaller, and repeat:

Minimum köktür. Onu kaldırın, dizinin son elemanını kök gözüne taşıyın (biçim kurallarını koruyarak); ardından 3. kuralı aşağı yönde onarın: düğümü iki çocuğuyla karşılaştırın, küçük çocuk düğümden de küçükse onunla yer değiştirin ve tekrarlayın:

extract_min(Q):
    min = Q[1]
    Q[1] = Q[n]
    n = n − 1
    bubble_down(Q, 1)
    return min

bubble_down(Q, p):
    find the smallest among Q[p] and its (up to two) children
    if that smallest is a child c:
        swap Q[p] and Q[c]
        bubble_down(Q, c)

extract_min(Q):
    min = Q[1]
    Q[1] = Q[n]
    n = n − 1
    bubble_down(Q, 1)
    return min

bubble_down(Q, p):
    Q[p] ve (en fazla iki) çocuğu arasındaki en küçüğü bul
    if bu en küçük eleman bir c çocuğu ise:
        Q[p] ile Q[c] yer değiştir
        bubble_down(Q, c)

Again each swap moves one level, so O(log n).

Yine her yer değiştirme bir düzey ilerler; dolayısıyla O(log n).

Doğrusal zamanda öbek kurma

There is a faster way to build a heap from n items than n insertions. Notice that two heaps plus a fresh item can be merged into one heap by making the item the root and bubbling it down. So: copy the items into the array in any order, then call bubble_down on positions n/2, n/2 − 1, …, 1 (positions above n/2 are leaves, which are already tiny heaps). This is called heapify.

n elemandan öbek kurmanın n eklemeden daha hızlı bir yolu vardır. İki öbek ve yeni bir elemanın, eleman kök yapılıp aşağı taşınarak tek öbekte birleştirilebildiğine dikkat edin. O hâlde elemanları diziye herhangi bir sırayla kopyalayın; sonra n/2, n/2 − 1, …, 1 konumlarında bubble_down çağırın (n/2’den büyük indisli konumlar yapraktır; zaten küçük öbeklerdir). Buna öbekleştirme (heapify) denir.

Why is this only O(n)? Because most of the sub-heaps being merged are tiny. In a full binary tree of n nodes there are at most ⌈n/2ʰ⁺¹⌉ nodes at height h, and bubbling one of them down costs O(h). The total is

Bu neden yalnızca O(n)’dir? Çünkü birleştirilen alt öbeklerin çoğu çok küçüktür. n düğümlü dolu bir ikili ağaçta h yüksekliğinde en fazla ⌈n/2ʰ⁺¹⌉ düğüm vardır; bunlardan birini aşağı taşımak O(h) tutar. Toplam şöyledir:

The sum Σ h/2ʰ is not quite a geometric series, but it converges, to 2. (Differentiate the geometric series identity Σ xᵏ = 1/(1 − x) to get Σ k xᵏ⁻¹ = 1/(1 − x)², multiply by x, and put x = 1/2.) So building a heap takes at most about 2n comparisons: linear time.

Σ h/2ʰ toplamı tam olarak geometrik seri değildir; ancak 2’ye yakınsar. (Σ xᵏ = 1/(1 − x) geometrik seri özdeşliğinin türevini alarak Σ k xᵏ⁻¹ = 1/(1 − x)² elde edin, x ile çarpın ve x = 1/2 koyun.) Böylece öbek kurmak en fazla yaklaşık 2n karşılaştırma gerektirir: doğrusal zaman.

Skiena’s meta-lesson: “doing at most x operations of at most y time each” gives O(xy), which is always true but sometimes a big over-estimate. Here the lazy bound is O(n log n); the careful bound is O(n). Ask whether your analysis is tight.

Skiena’nın genel dersi: “Her biri en fazla y zaman alan en fazla x işlem yapmak” O(xy) verir; bu her zaman doğrudur, ancak bazen büyük bir fazla tahmindir. Burada özensiz sınır O(n log n), dikkatli sınır ise O(n)’dir. Analizinizin sıkı olup olmadığını sorun.

Öbek sıralaması (heapsort)

heapsort(s, n):
    build a heap from s (linear time)
    for i from 1 to n:
        s[i] = extract_min(heap)

heapsort(s, n):
    s'den bir öbek kur (doğrusal zaman)
    for i from 1 to n:
        s[i] = extract_min(heap)

Building costs O(n) and each of the n extractions costs O(log n), so heapsort is O(n log n). It cannot be O(n) because extracting n minimums in order is sorting, and Lecture 9 shows sorting needs Ω(n log n) comparisons.

Kurma O(n), n çıkarma işleminin her biri O(log n) tutar; dolayısıyla öbek sıralaması O(n log n)’dir. O(n) olamaz; çünkü n minimumu sırayla çıkarmak sıralamadır ve Ders 9’da sıralamanın Ω(n log n) karşılaştırma gerektirdiği gösterilir.

Done carefully, heapsort needs no extra memory: build the heap inside the original array, and after each extraction put the removed element into the hole left at the end of the array (with a max-heap, this fills the array from the back with the largest items, leaving it sorted in increasing order).

Dikkatli gerçekleştirilirse öbek sıralaması ek bellek gerektirmez: öbeği özgün dizinin içinde kurun; her çıkarmadan sonra çıkarılan elemanı dizinin sonunda kalan boşluğa koyun. (Maksimum öbekle bu işlem, diziyi arkadan başlayarak en büyük elemanlarla doldurur ve artan sırada sıralı bırakır.)