Yazılım Mühendisliği ve Teknolojiler üzerine…

0%

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

Yayın Kategori

İ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 = 2p+1
sağ = 2p+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ı. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
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;
    }
};
İlgili Gönderiler