Çok sık kullanılan, karşılaştırmaya dayalı bir sıralama algoritmasıdır. zamanda gerçekleşir. Uzun zaman aldığından, büyük veri paketlerinde kullanılmamasına dikkat edilmelidir. Çalışma sistemine gelince: Arka kısımda 2li sıralama ağacı kullanır. Tüm sıralama işlemlerini bu ağaç üzerinde gerçekleştirir. Algoritma, verilen veri kümesini 2li ağaca çevirir. Bu işlemi yaparken herhangi bir koşul gözetilmez, elemanlar ağaca sırayla eklenir. Fakat ağaç oluşturduktan sonra ağacın en son elemanından başlayarak köke kadar tüm elemanları tarayarak, ağacın bir MAX ya da MIN HEAP ağacı olması sağlarız. (Bu kadarı, sıralamamızı azalan ya da artan olması durumuna göre karar veririz.). Bu işlemden sonra en sondaki eleman ile kök elemanının yerlerini değiştirilir ve en son yaprak ağaçtan koparılır. Sıralama, yer değiştirme ve koparma işlemleri, ağaçta sadece kök elemanı kalana kadar tekrarlanır. Koparılan elemanlar konduğu sırada listeye geri alınır. Böylece sıralama yapılmış olur. Pseudocode: Build Max Heap: BUILD-MAX-HEAP(A)     heap-size[A] ← length[A]     for i ← floor(length[A]/2) downto1         do              MAX-HEAPIFY(A, i) Max Heapify: MAX-HEAPIFY(A, i)     l ← LEFT(i)     r ← RIGHT(i)     if l ≤ heap-size[A] and A[l] > A[i]         then largest ← l         else largest ← i     if r ≤ heap-size[A] and A[r] > A[largest]         then largest ← r     if largest ≠ i         then exchange A[i] ↔ A[largest]             MAX HEAPIFY(A, largest) Sıralama örneği: Bize verilen dizi: 4 1 3 2 16 9 10 14 8 7 2li ağacımızı oluşturalım: Ağacı düzenleyelim (sıralama):   Ağacın son elemanı ile kökü yer değiştirelim, ve son düğümü ağaçtan kopartalım. Ağacın en son hali: Örnek C++ kodu: void heapsort(int *a, int size) { int i, temp; for (i = (size / 2)-1; i >= 0; i--) heapify(a, i, size - 1); for (i = size-1; i >= 1; i--) { temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, 0, i-1); } } void heapify(int *a, int root, int bottom) { int done, maxChild, temp; done = 0; while ((root*2 <= bottom) && (!done)) { if (root*2 == bottom) maxChild = root * 2; else if (a[root * 2] > a[root * 2 + 1]) maxChild = root * 2; else maxChild = root * 2 + 1; if (a[root] < a[maxChild]) { temp = a[root]; a[root] = a[maxChild]; a[maxChild] = temp; root = maxChild; } else done = 1; } } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Kaynak: İ.T.Ü. 2009 – 2010 Güz Dönemi, Advanced Data Structures dersi ders notları, Z.Çataltepe & S.Kabadayı Tags: , | Categories: Algoritma | C++