Heap Tree (Yığın Ağacı) ve JS kütüphanesi kodları

İkili bir ağaç yapısıdır. Kök hariç , her düğümün bir ebeveyni vardı. Her ebeveyninde en fazla 2 çocuğu vardı.

2 türü vardır ; Minimum heap, Maximum heap.

Amacı

En yüksek performansta, bir diziden en küçük ve en büyük değerleri teker teker sırasıyla çekebilmektir. Bu dizi, sıralı değildir. Ancak ilk elemanı(kökü) daima en büyük veya en küçük elemandır.

Kuralları

  • Eğer minimum heap ise, ebeveyn çocuklarında daima küçük olmalıdır. Maximum heapde tam tersi geçerlidir.
  • Çocuklar arası ilişki yoktur.
  • Tek indeks sahip düğüm solda, çift indekse sahip düğüm sağdadır. (yani 3>sol; 4>sağ)
  • Ebeveyninin indeksinin 2 katının 1 fazlası sol çocuğun indeksi, 2 katının 2 fazlası sağ çocuğun indeksidir. (2nin sol çocuğu 5, sağ çocuğu 6′tir)
  • Yeni eklenen düğüm, her zaman ağacın en alt sol tarafına eklenir. (Yani dizinin en sağına eklenir)
NOT : Kökün indeksi 0'dır.

p : ebeveyn indeksi
x : herhangi bir düğümün indeksi
sol : sol çocuk indeksi
sağ : sağ çocuk indeksi
---
sol = 2*p+1
sağ = 2*p+2
--
x%2 = 0 ise => sağdadır.
p = x / 2 - 1
x%2 = 1 ise => soldadır.
p = (x - 1) / 2

Ekleme

  • Değer dizinin sonuna(en sağına), eklenir.
  • Eklenen değer ebeveyni ile kıyaslanır. Ebeveyninden küçük ise, onunla yer değiştiri ve bu işlemin aynısı ebeveynlerininin ebeveynleri ilede yapılır.

Çıkarma

  • Heapda, daima kök değer çıkartılır. Yani dizinin ilk elemanı çıkartılır.
  • Çıkartılan bu değer ile yeni ağaç oluşur.
  • Bu ağaçta kökten başlayan, çocuğu olmayan düğüme kadar, en küçük değere sahip çocuk ile kıyaslanır, eğer en küçük çocuktan büyük ise yer değiştirilir. Yer değiştirilen çocuk ile aynı işlem ağacın o dalı boyunca tekrarlanır.

Bu işlemi yapan, yeni yazdığım bir Heap sınıfı.

function Heap(sortFunc){
    this.nodes = [];
    this.sortFunc= sortFunc || function(a,b){return a-b;};
 
    this.func = function(a,b){
            return this.sortFunc(a,b) < 0;
    }
}
 
 
 
Heap.prototype = {
    add : function(e){
        var x = this.nodes.length;
        this.nodes.push(e);
        var p = this.parent(x);
 
        // heapify2up
        while(this.func(this.nodes[x],this.nodes[p]) && x!=0){
            this.nodes[x]=this.nodes[p];
            this.nodes[p]=e;
 
            x=p;
            e = this.nodes[x];
            p=this.parent(x);
        }
 
        return this.nodes;
 
    },
    get : function(){
        var r = this.nodes.shift();
 
        //heapify2down
        var x = 0;
        var childs = this.childs(x);
        var min;
        while(childs.length!=0){
            min=childs[0];
            if(childs.length==2 && !this.func(this.nodes[childs[0]],this.nodes[childs[1]])){
                min = childs[1];
            }
 
            if(this.func(this.nodes[min],this.nodes[x])){
                var temp = this.nodes[x];
                this.nodes[x] = this.nodes[min];
                this.nodes[min] = temp;
                x = min;
                childs = this.childs(x);
            }
            else childs=[]
        }
        return r;
    },
    isEmpty : function(){
        return this.nodes.length==0;
    },
    parent : function(x){
        if(this.right(x)) return x/2-1;
        return (x-1)/2;
    },
    childs : function(x){
      var a = [];
      if(this.nodes[2*x+1]){
          a.push(2*x+1);
          if(this.nodes[2*x+2])
              a.push(2*x+2);
      }
      return a;
    },
    right : function(x){
        return x%2==0;
    }
};

 

A* Algoritması (A yıldız arama algoritması)

Amacı : Bir düğümden, diğer düğüme en az maliyetli çözümü bulmak

Türü : Arama Algoritması, Sezgisel Algoritma (Yapay zeka)

Kâşifleri : Nils Nilsson,Bertram Raphael , Peter E. Hart

Kullanım yerleri :

  • Yol bulma
  • Oyunlarda aktörün hedefe doğru izleyeceği yolların tespiti
  • Gezgin satıcı probleminin çözümü
  • Labirentten en kısa çıkışı bulma

 

f(x) : durum fonksiyonu. Az olması, o durumun daha az maliyetli olduğunu belirtir.

f(x) = g(x) + h(x)

g(x) : Başlangıç durumuna göre maliyetimiz.

h(x) : Bitiş duruma olan sezgisel maliyet.

Algoritma

OPEN -> // fCost'a göre sıralı dizi

OPEN.ekle(başlangıç_düğümü)

DÖNGÜ - OPEN dizi boyutu 0 olmadığı müddetçe
    şuanki_düğüm <- OPEN.ilk elemanı
    OPEN.sil(şuanki düğüm)
    EĞER şuanki_düğüm, hedef düğüm ise
        DÖNGÜden çık // HEDEFE ULAŞTI
    şuanki_düğüm.closed=true
    şuanki_düğüm.gCostHesapla()
    komşular = şuanki_düğüm.komşular
    DÖNGÜ komşu <- komşular
        EĞER komşu.closed ise SONRAKİ_KOMŞUYA_GEÇ
        maliyet = şuanki_düğüm.gCost + komşuya_uzaklık
        komşu.gCostHesapla()
        EĞER komşu.OPENdaDeğilse veya maliyet<komşu.gCost ise
            komşu.gCost = maliyet
            komşu.hCostHesapla()
            komşu.ebeveyn = şuanki_düğüm
            EĞER komşu.OPENdaDeğilse
                OPEN.ekle(komşu)
OPEN dizi boyutu 0 olduğu için DÖNGÜden çıkıldıysa // HEDEFE ULAŞAMADI

Javascript Kodu

FIND (Yol bulmayı başlat)
RELOAD (Gridi yeniden yükle)
ilk tık -> başlangıç karesi
2. tık -> hedef kare
sonraki tıklar -> engel oluştur

See the Pen A* Algoritması by farukcan (@farukcan) on CodePen.