Örneğin ekin yığınında olduğu gibi bir yığından bahsettiğimizde üstüste istif edilmiş birbiri üzerinde oturan elemanlar geliyor. Bu elemanlar da oraya konuldukları sırayla birbirinin üstünde duruyorlar. Ve sadece en üstteki elemanı alabiliyoruz (tüm bu yığını devirmeden)

http://i.imgur.com/khqDF.jpg

Öbekte ise elemanların belirli bir yerleştirme sırası yok. Elemanlara istediğimiz gibi erişip bir elemanı çıkartabiliriz çünkü belirli bir 'enüstte' duran eleman yok.

http://i.imgur.com/E5QTV.jpg

Şimdi bundan bahsettim çünkü stack için türkçe karşılık 'yığın ya da yığıt' sanırım. Ama ben heap yerine 'yığın' kullanıyordum. Ama yığın da üstüste anlamı verdiği için öbek daha mı uygun olur acaba. (Neyse şimdilik gene yığın kullanarak devam ediyorum)

Aslında böyle bir topluluk 'std.algorithm' sınıfında varmış.

import std.stdio, std.container, std.algorithm, std.range;

void main()
{
   int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
   auto h = heapify(a);
   assert(h.front == 16);
   assert(a == [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]);
}

Ama dikkat ederseniz burada en büyük elemanları ağacın en üstüne getiriyor. Benim istediğim tam tersi ağacın en küçük elemanları en üste gelsin.

http://opendatastructures.org/versions/edition-0.1d/ods-java/img1156.png

Bu maksatla denemek ve öğrenmek amaçlı şu şekilde bir ikili yığın yazdım. Yorumlarınızı bekliyorum.

import std.algorithm;

struct İkiliYığın
{
   int[] dizi;
   int büyüklük;

   this (int[] dizi)
   {
       this.dizi = dizi;
       this.büyüklük = dizi.length;
   }

   int soldaki(int i)
   {
       return 2 * i + 1;
   }

   int sağdaki(int i)
   {
       return 2 * i + 2;
   }

   int üstteki(int i)
   {
       return (i - 1) / 2;
   }

   bool ekle(int x)
   {
       dizi[büyüklük++] = x;
       return true;
   }

   void yukarıKaydır(int i)
   {
       int ü = üstteki(i);
       while (i > 0 && karşılaştır(dizi[i], dizi[ü]) < 0) {
           swap(i, ü);
           i = ü;
           ü = üstteki(i);
       }
   }
}

int karşılaştır (int x, int  y)
{
   if (x < y) return -1;
   if (y > x) return 1;
   return 0;
}


void main()
{
   İkiliYığın yığın;
}

Yeterli kadar test edemedim şimdilik ;-) Bir de buradaki 'swap' işlevi düşündüğümüz gibi çalışır mı emin olamadım.

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Yaptığım bir kaç basit hatayı düzelttikten sonra:

import std.algorithm, std.stdio;

struct İkiliYığın
{
   int[] dizi;
   int büyüklük;

   this (int[] dizi)
   {
       this.dizi = dizi;
       this.büyüklük = dizi.length;
   }

   int soldaki(int i)
   {
       return 2 * i + 1;
   }

   int sağdaki(int i)
   {
       return 2 * i + 2;
   }

   int üstteki(int i)
   {
       return (i - 1) / 2;
   }

   bool ekle(int x)
   {
       dizi.length++;
       dizi[büyüklük++] = x;
       yukarıKaydır(büyüklük-1);
       return true;
   }

   void yukarıKaydır(int i)
   {
       int ü = üstteki(i);
       while (i > 0 && karşılaştır(dizi[i], dizi[ü]) < 0) {
           yerDeğiştir(i, ü);
           i = ü;
           ü = üstteki(i);
       }
   }

   void yerDeğiştir(int i, int j)
   {
       int gecici = dizi[i];
       dizi[i] = dizi[j];
       dizi[j] = gecici;
   }
}

int karşılaştır (int x, int  y)
{
   if (x < y) return -1;
   if (y > x) return 1;
   return 0;
}


void main()
{
   İkiliYığın yığın = [ 4, 9, 8, 17, 26, 50, 16, 19, 69, 32, 93, 55];

   yığın.ekle(6);

   foreach (eleman; yığın.dizi) {
       write (eleman, " ");
   }
   writeln();
   writeln ("Yigin uzunlugu: ", yığın.dizi.length);
}

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Sizin yazdığınız kodu incelemeden önce eleman çıkarma işlevini de ekledim.

import std.algorithm, std.stdio, std.conv;

struct İkiliYığın
{
   private
   {
       int[] dizi;
       int büyüklük;
   }

   this (int[] dizi)
   {
       this.dizi = dizi;
       this.büyüklük = dizi.length;
   }

   public string toString() const
   {
       string sonuç;
       foreach (eleman; dizi) {
           sonuç ~= to!string(eleman) ~ " ";
       }
       return sonuç;
   }

   int soldaki(int i)
   {
       return 2 * i + 1;
   }

   int sağdaki(int i)
   {
       return 2 * i + 2;
   }

   int üstteki(int i)
   {
       return (i - 1) / 2;
   }

   bool ekle(int x)
   {
       dizi.length++;
       dizi[büyüklük++] = x;
       yukarıKaydır(büyüklük-1);
       return true;
   }

   int çıkart()
   {
       int enküçük = dizi[0];
       dizi[0] = dizi[$ - 1];

       dizi = dizi [0 .. $ - 1];

       büyüklük = dizi.length;

       aşağıKaydır(0);
       return enküçük;
   }

   void yukarıKaydır(int i)
   {
       int ü = üstteki(i);
       while (i > 0 && karşılaştır(dizi[i], dizi[ü]) < 0) {
           yerDeğiştir(i, ü);
           i = ü;
           ü = üstteki(i);
       }
   }

   void yerDeğiştir(int i, int j)
   {
       int gecici = dizi[i];
       dizi[i] = dizi[j];
       dizi[j] = gecici;
   }

   void aşağıKaydır (int i)
   {
       do {
           int j = -1;
           int sağ = sağdaki(i);
           if (sağ < büyüklük && karşılaştır(dizi[sağ], dizi[i]) < 0) {
               int sol = soldaki(i);
               if (karşılaştır(dizi[sol], dizi[sağ]) < 0) {
                   j = sol;
               } else {
                   j = sağ;
               }
           } else {
               int sol = soldaki(i);
               if (sol < büyüklük && karşılaştır(dizi[sol], dizi[i]) < 0) {
                   j = sol;
               }
           }
           if (j >= 0) yerDeğiştir(i, j);
           i = j;
       } while (i >= 0);
   }
}

int karşılaştır (int x, int  y)
{
   if (x < y) return -1;
   if (y > x) return 1;
   return 0;
}

void main()
{
   İkiliYığın yığın = [ 4, 9, 6, 17, 26, 8, 16, 19, 69, 32, 93, 55, 50];
   yığın.çıkart();

   writeln(yığın);
   writeln ("Yigin uzunlugu: ", yığın.dizi.length);
}

Çalışması da şu şekilde:

<
http://opendatastructures.org/ods-cpp/img1357.png>

Burada her zaman en küçük elemanı çıkarıyor. Burada en küçük eleman 4 olduğu için en sondaki elemanı 4'ün üzerine yazıyor. Sonra diziyi bir kısaltıyor.

http://opendatastructures.org/ods-cpp/img1358.png

Sonra 50 uygun bir sırada olmadığı için uygun sıraya gelene kadar aşağı kaydırıyor.

http://opendatastructures.org/ods-cpp/img1359.png

http://opendatastructures.org/ods-cpp/img1360.png

Böylece sayılar yerli yerine oturmuş oluyor.

Yazdığınız kodu hemen şimdi inceliyorum :)

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Tam da bu konulara ilgi duyduğum zamanlar bu iletiler bir hazine kadar değerliler, teşekkürler...

Peki şöyle bir şeyi nasıl yaparız?

Yine bir dizi kullanıyoruz ve yapının ismi önemsiz; yığın veya yığıt ama değişik özellikleri var:

• Henüz offset değerini geçmeden dolmuyor (veri kaydı yapılmıyor ama her iki yönde dizilere ulaşır gibi range hatası vermiyor!)
• Kapasitesi dolduğunda hata da vermiyor (kayıt da etmiyor) ama index değeri artıyor...:)

Gülmeyin, ilginç bir şey ama sistematik bir mantık üzerine sistemi henüz çalıştırmayı başaramadım. Yani yapıyı kurarken bir offset değeri veriyorum ama bir çok yerde takıldım gibi. Hadi biraz kodlardan konuşalım, yapım kısaca şöyle:

struct birGaripYığıt // :)
{
   public:
       int _Index;

   private:
       int[] stack;
       size_t _Length;
       size_t _Offset;

   this (size_t realLen, size_t diffLen = 0) {     // eğer sıfır ise normal yığıt gibi kullan
       if(diffLen > 0)
       {
           stack = new int[realLen - diffLen + 1]; // +1 dizi yapıları 0 ile başladığı için
       } else {                                    // sanki sorgularda kolaylık sağlıyor
           stack = new int[realLen];
       }
     _Length = realLen;
     _Offset = diffLen;
   }

   public void set(size_t len, int data) @property
   {
       _Index++;
       if(len >= _Offset)
       {
           stack[len - _Offset] = data;
       }
   }

   public int get(size_t len) @property
   {
       _Index--;
       if(len >= _Offset)
       {
           return stack[len - _Offset];
       }
       return 0;
   }
}

Yani özetle iki index var biri sanal, diğeri gerçek. Gerçek olanı offset'in gölgesinde dizide kullanırken, sanal olanı dışarıda işlerimizi halletmek için kullanacağız.

Sevgiler, saygılar...

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Lütfen sormadım farz edin...:)

Bir Garip Yığıt (http://ddili.org/forum/thread/891) başlığında çözüm yer almaktadır...

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

"İkili yığın" hoşuma gitti. :) Ben de "heap"e karşılık "yığın", "stack"e karşılık da "yığıt" kullanıyorum. Bunun tek nedeni zamanında yaptığım araştırmaya göre bunun yaygın olduğunu görmemdi.

Senin koduna geçmeden önce bunun BinaryHeap ile mümkün olduğunu göstermek istiyorum. BinaryHeap sıralama kıstasını da alabildiği halde onun kolaylık işlevi olan heapify() böyle bir bilgi almıyor.

heapify()'ın bu yetersizliği ile ilgili bir hata raporu açacaktım ama zaten açılmış:

http://d.puremagic.com/issues/show_bug.cgi?id=6066

Yani eğer heapify() aşağıdaki gibi yazılmış olsa istediğini kolayca halledebiliriz:

import std.stdio, std.container, std.algorithm, std.range;

auto heapify(alias less = "a < b", Store)(Store s,
                                         size_t initialSize = size_t.max)
{
   return BinaryHeap!(Store, less)(s, initialSize);
}

void main()
{
   int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];

   {
       auto h = .heapify(a);
       assert(h.front == 16);
       assert(a[0] == 16);
   }

   {
       auto h = .heapify!"a > b"(a);
       assert(h.front == 1);
       assert(a[0] == 1);
   }
}

Tabii asıl heapify() ile karışmasın diye başında noktayla çağırıyorum: .heapify.

Ek olarak, lambda vs. de kullanabilirdik:

       auto h = .heapify!((a, b) => a > b)(a);

Başka bir çözüm, kıstası sarmalayan şöyle bir işlev yazmak olabilir:

auto heapifyTers(Store)(Store s, size_t initialSize = size_t.max)
{
   return BinaryHeap!(Store, "a > b")(s, initialSize);
}
// ...
       auto h = heapifyTers(a);

Tamam, şimdi senin koduna geçebilirim... :)

• büyüklük'ün türü 64 bitlik ortamda derleme hatası oluşturuyor. Bence size_t olsa daha iyi olur ama başka işlevler de hep int kullandıkları için şöyle cast(int) ile hızlıca hallettim :):

       this.büyüklük = cast(int)dizi.length;

• Değişken ismi olarak ü'yü sevdim. :)

• Algoritmanı derinlemesine incelemedim ama yukarıdaki heapifyTers()'in sonucuyla karşılaştırdığımda aynı çıkmıyor. :/

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (acehreli):

Bir yanlışlık yapmış olmalıyım. Son gösterdiğin kod heapifyTers() ile aynı:

void main()
{
   {
       İkiliYığın yığın = [ 4, 9, 6, 17, 26, 8, 16, 19, 69, 32, 93, 55, 50];
       writeln(yığın);
   }

   {
       auto a = [ 4, 9, 6, 17, 26, 8, 16, 19, 69, 32, 93, 55, 50];
       auto h = heapifyTers(a);

       writeln(a);

       for ( ; !h.empty(); h.removeFront()) {
           writeln(h.front);
       }
   }
}

import std.container;
auto heapifyTers(Store)(Store s, size_t initialSize = size_t.max)
{
   return BinaryHeap!(Store, "a > b")(s, initialSize);
}

Çıktısı:

'4 9 6 17 26 8 16 19 69 32 93 55 50
[4, 9, 6, 17, 26, 8, 16, 19, 69, 32, 93, 55, 50]
'

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Anlattıkların aklıma birden fazla şey getirdi:

• İki uca doğru uzayan veri yapısı olarak C++'ın STL'inde de bulunan double-ended queue (std::deque) var.

• set() ve get() uzunluk değil de indeks alıyorlar, değil mi? Yani sen aslında var olmayan bir indekse yazdığında bile hata verilmeyecek ve oraya o değer yazılacak mı? Öyleyse ya otomatik olarak uzayan bir dizi olacak ya da bu bir sparse vector veri yapısı. (?)

• Aslında koddan anlaşıldığına göre indeksleri kaymış olan bir dizi mi düşünüyoruz? Yani 10 numaralı eleman deyince belki de aslında içerde 0 numaralı elemanı kullanacağız. (Sanırım amacın bu.)

Kusura bakma; umarım ortalığı daha da karıştırmadım? :)

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (acehreli):

> void main()
> {
>     {
>         İkiliYığın yığın = [ 4, 9, 6, 17, 26, 8, 16, 19, 69, 32, 93, 55, 50];
>         writeln(yığın);
>     }
>
>     {
>         auto a = [ 4, 9, 6, 17, 26, 8, 16, 19, 69, 32, 93, 55, 50];
>         auto h = heapifyTers(a);
>
>         writeln(a);
>
>         for ( ; !h.empty(); h.removeFront()) {
>             writeln(h.front);
>         }
>     }
> }
>
> import std.container;
> auto heapifyTers(Store)(Store s, size_t initialSize = size_t.max)
> {
>     return BinaryHeap!(Store, "a > b")(s, initialSize);
> }
> ```

>
> Çıktısı:
>
> '4 9 6 17 26 8 16 19 69 32 93 55 50
> [4, 9, 6, 17, 26, 8, 16, 19, 69, 32, 93, 55, 50]
> '
>

Ben bu örneği çalıştırdığımda şu çıktıyı alıyorum.

'4 9 6 17 26 8 16 19 69 32 93 55 50
[4, 9, 6, 17, 26, 8, 16, 19, 69, 32, 93, 55, 50]
4 6 8 9 16 17 19 26 32 50 55 69 93
'

Benim burada dikkatimi çeken 'heapify' algoritmasını çalıştırdığımız zaman elemanları da sağdan sola doğru sıraya sokuyor.

Ama örneğin aşağıdaki gibi bir yığın geçerli bir yığın değil mi. Eğer geçerli bir yığınsa binaryHeap'i böyle bir yığınla ilklendirmenin bir yolu olmalı.

<http://opendatastructures.org/ods-cpp/img1357.png>

Burada dikkat ederseniz aynı seviyede bulunan elemanlardan solda olan daha küçük değil. Sadece üstte bulunan eleman diğerinden daha büyük olmuş oluyor. Ama biz 'heapify' algoritmasını çalıştırdığımız zaman aşağıdaki gibi sıraya sokuyor.

<http://opendatastructures.org/ods-cpp/img1346.png>

-- 
[ Bu gönderi, <http://ddili.org/forum>'dan dönüştürülmüştür. ]

O zaman

'4 9 6 17 26 8 16 19 69 32 93 55 50'

geçerli bir ikili yığın (binary heap) oluyor değil mi. Peki bu durumda 'std.container' sınıfında bulunan 'BinaryHeap''i nasıl böyle bir değerle ilklendirebiliriz.

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]