Veri Yapıları: Öbek (Heap)

Öbek

Öbekler, eklemeleri soldan sağa doğru yapılan ve son seviyesi dışındaki tüm seviyeleri dolu olan bir ikili ağaç çeşididir.

Öbeklerin ana özellikleri her ebeveyn değerin çocuklarından daha küçük / büyük değere sahip olmasıdır.

Yabancı kaynaklarda Min Heap ve Max Heap şeklinde adlandırılmaları bu sebepten dolayıdır.

Öncelikli ikili ağaçlar olarak da düşünülebilirler.

Öbekler genellikle ikili arama ağaçlarındakinin aksine dizi gibi yapılar ile gerçekleştirilirler.

Bunun sağladığı avantajlardan birisi de ebeveyn ve çocuk düğümleri arasındaki ilişkiyi matematiksel basit bir ifade ile kurulabilmesidir.

Bu ifadeler şu şekildedir;

  • Ebeveynin indisi: (indis - 1) / 2
  • Sol çocuğun indisi: 2 * indis + 1
  • Sağ çocuğun indisi: 2 * indis + 2

Lafı fazla uzatmadan kod üzerinden gerçekleştirme yaparak aşama aşama ilerleyelim.

Gerçekleştirim

Öbek örneğimizi C++ dilinde vektörleri kullanarak gerçekleştireceğiz.

Diğer nesne tabanlı dillerde (Java, C# vb.) diziyi tercih edebilirsiniz.

Öncelikle örneğimizde bize gerekecek kütüphaneleri çağıralım;

1
2
3
4
#include <iostream>
#include <vector>

using namespace std;

Sıra geldi Obek sınıfımızı tanımlamaya;

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
class Obek {
public:
// öbek boyutunu geri gönderecek fonksiyonumuz
int boyut() { return obek.size(); }
// öbeğin en küçük değerini (kökü) gönderecek fonksiyonumuz
int enKucuguSil();
// öbeğe veri eklemek için kullanacağımız fonksiyonumuz
void ekle(int veri);
// öbeği yazdırmak için kullanacağımız fonksiyonumuz
void yazdir();

private:
// ebeveyn indisine göre sağ çocuğu bulacak fonksiyonumuz
int sag(int ebeveyn);
// ebeveyn indisine göre sol çocuğu bulacak fonksiyonumuz
int sol(int ebeveyn);
// çocuğun indisine göre ebeveyni gönderecek fonksiyonumuz
int ebeveyn(int cocuk);
// elemanları yukarı taşımakta kullanılacak fonksiyonumuz
void yukariTasi(int indis);
// elemanları aşağı taşımakta kullanılacak fonksiyonumuz
void asagiTasi(int indis);
private:
vector<int> obek; // öbek vektörümüz
};

Şimdi sırasıyla tanımlamalarını yaptığımız sınıf fonksiyonlarımızı gerçekleştirelim.

int enKucuguSil();

1
2
3
4
5
6
7
8
9
10
11
// en küçük elemanı silip geri gönderen fonksiyonumuz
int Obek::enKucuguSil()
{
int enKucuk = obek.front();

obek[0] = obek.at(obek.size() - 1);
obek.pop_back();
asagiTasi(0);

return enKucuk;
}

int ekle(int veri);

1
2
3
4
5
6
7
8
// gönderdiğimiz veriyi öbeğe eleman olarak ekleyen fonksiyonumuz
void Obek::ekle(int veri)
{
// vektörümüzün sonuna elemanımızı ekliyoruz
obek.push_back(veri);
// son eklenen elemanı yukarıda uygun yere taşıyoruz
yukariTasi(obek.size() - 1);
}

void yazdir();

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// öbeğimizi baştan sona yazdiran fonksiyonumuz
void Obek::yazdir()
{
vector<int>::iterator yer = obek.begin();
cout << "Öbek: ";

// vektörü başından sonuna kadar dolaşıp sırayla yazdırıyoruz
while (yer != obek.end()) {
cout << *yer << " ";
++yer;
}

cout << endl;
}

int sag(int ebeveyn);

1
2
3
4
5
6
7
8
// gönderilen ebeveynin sağ çocuğunu bulan ve geriye gönderen fonksiyon
int Obek::sag(int ebeveyn)
{
// sağ çocuğun olması gerektiği yerin indisini alıyoruz
int i = 2 * ebeveyn + 2;
// indis öbek içindeyse indisi gönderiyoruz
return (i < obek.size()) ? i : -1;
}

int sol(int ebeveyn);

1
2
3
4
5
6
7
8
// gönderilen ebeveynin sol çocuğunu bulan ve geriye gönderen fonksiyon
int Obek::sol(int ebeveyn)
{
// sol çocuğun olması gerektiği yerin indisini alıyoruz
int i = 2 * ebeveyn + 1;
// indis öbek içindeyse indisi gönderiyoruz
return (i < obek.size()) ? i : -1;
}

int ebeveyn(int cocuk);

1
2
3
4
5
6
7
8
9
10
11
12
// gönderilen çocuğun ebeveynini bulan ve geriye gönderen fonksiyonumuz
int Obek::ebeveyn(int cocuk)
{
if (cocuk != 0)
{
// ebeveynin olması gerektiği yerin indisini alıyoruz
int i = (cocuk - 1) / 2;
return i; // ve geriye indisi gönderiyoruz
}
// çocuk mevcut değilse ebeveyni olmayacağı için -1 gönderiyoruz
return -1;
}

void yukariTasi(int indis);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// elemanlarımızı yukarıya taşımamıza olanak sağlayan fonksiyonumuz
void Obek::yukariTasi(int indis)
{
// indisimizdeki değer ebeveyninden küçük olduğu sürece
while ((indis > 0) && (ebeveyn(indis) >= 0) &&
(obek[ebeveyn(indis)] > obek[indis]))
{
// ebeveyni ile takas işlemini gerçekleştiriyoruz
int gecici = obek[ebeveyn(indis)];
obek[ebeveyn(indis)] = obek[indis];
obek[indis] = gecici;
indis = ebeveyn(indis);
}
}

void asagiTasi(int indis);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// elemanlarımızı aşağıya taşımamıza olanak sağlayan fonksiyonumuz
void Obek::asagiTasi(int indis)
{
// yerine taşınılacak uygun çocuğu buluyoruz
int cocuk = sol(indis);

if ((cocuk > 0) && (sag(indis) > 0) &&
(obek[cocuk] > obek[sag(indis)]))
{
cocuk = sag(indis);
}

if (cocuk > 0)
{
// uygun çocuk ile takas işlemini gerçekleştiriyoruz
int gecici = obek[indis];
obek[indis] = obek[cocuk];
obek[cocuk] = gecici;
asagiTasi(cocuk);
}
}

Ve son olarak test senaryomuzu içeren int main() fonksiyonumuz;

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
int main()
{
// öbeğimizi oluşturuyoruz
Obek* kucukObek = new Obek();

// oluşturduğumuz öbeğe sırayla çeşitli değerler ekliyoruz
kucukObek->ekle(7);
kucukObek->yazdir();
kucukObek->ekle(5);
kucukObek->yazdir();
kucukObek->ekle(1);
kucukObek->yazdir();
kucukObek->ekle(8);
kucukObek->yazdir();
kucukObek->ekle(2);
kucukObek->yazdir();
kucukObek->ekle(4);
kucukObek->yazdir();
kucukObek->ekle(9);
kucukObek->yazdir();
kucukObek->ekle(10);
kucukObek->yazdir();
kucukObek->ekle(3);
kucukObek->yazdir();
kucukObek->ekle(6);
kucukObek->yazdir();

// sırayla öbekteki en küçük değerleri yazdırıyoruz
int obekBoyutu = kucukObek->boyut();

for (int i = 0; i < obekBoyutu; i++)
cout << "Öbekteki en küçük değer: " << kucukObek->enKucuguSil() << endl;

// oluşturduğumuz öbeği bellekten temizliyoruz
delete kucukObek;

getchar();
}

Tamamlanmış öbek örneğimiz birleştirilmiş tam kodlarını da paylaşalım;

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <iostream>
#include <vector>

using namespace std;

class Obek {
public:
// öbek boyutunu geri gönderecek fonksiyonumuz
int boyut() { return obek.size(); }
// öbeğin en küçük değerini (kökü) gönderecek fonksiyonumuz
int enKucuguSil();
// öbeğe veri eklemek için kullanacağımız fonksiyonumuz
void ekle(int veri);
// öbeği yazdırmak için kullanacağımız fonksiyonumuz
void yazdir();

private:
// ebeveyn indisine göre sağ çocuğu bulacak fonksiyonumuz
int sag(int ebeveyn);
// ebeveyn indisine göre sol çocuğu bulacak fonksiyonumuz
int sol(int ebeveyn);
// çocuğun indisine göre ebeveyni gönderecek fonksiyonumuz
int ebeveyn(int cocuk);
// elemanları yukarı taşımakta kullanılacak fonksiyonumuz
void yukariTasi(int indis);
// elemanları aşağı taşımakta kullanılacak fonksiyonumuz
void asagiTasi(int indis);
private:
vector<int> obek; // öbek vektörümüz
};

// en küçük elemanı silip geri gönderen fonksiyonumuz
int Obek::enKucuguSil()
{
int enKucuk = obek.front();

obek[0] = obek.at(obek.size() - 1);
obek.pop_back();
asagiTasi(0);

return enKucuk;
}

// gönderdiğimiz veriyi öbeğe eleman olarak ekleyen fonksiyonumuz
void Obek::ekle(int veri)
{
obek.push_back(veri); // vektörümüzün sonuna elemanımızı ekliyoruz ve
yukariTasi(obek.size() - 1); // son eklenen elemanı yukarıda uygun yere taşıyoruz
}

// öbeğimizi baştan sona yazdiran fonksiyonumuz
void Obek::yazdir()
{
vector<int>::iterator yer = obek.begin();
cout << "Öbek: ";

// vektörü başından sonuna kadar dolaşıp sırayla yazdırıyoruz
while (yer != obek.end()) {
cout << *yer << " ";
++yer;
}

cout << endl;
}

// gönderilen ebeveynin sağ çocuğunu bulan ve geriye gönderen fonksiyonumuz
int Obek::sag(int ebeveyn)
{
int i = 2 * ebeveyn + 2; // sağ çocuğun olması gerektiği yerin indisini alıyoruz
return (i < obek.size()) ? i : -1; // indis öbek içindeyse indisi gönderiyoruz
}

// gönderilen ebeveynin sol çocuğunu bulan ve geriye gönderen fonksiyonumuz
int Obek::sol(int ebeveyn)
{
int i = 2 * ebeveyn + 1; // sol çocuğun olması gerektiği yerin indisini alıyoruz
return (i < obek.size()) ? i : -1; // indis öbek içindeyse indisi gönderiyoruz
}

// gönderilen çocuğun ebeveynini bulan ve geriye gönderen fonksiyonumuz
int Obek::ebeveyn(int cocuk)
{
if (cocuk != 0)
{
int i = (cocuk - 1) / 2; // ebeveynin olması gerektiği yerin indisini alıyoruz
return i; // ve geriye indisi gönderiyoruz
}
return -1; // çocuk mevcut değilse ebeveyni olmayacağı için -1 gönderiyoruz
}

// elemanlarımızı yukarıya taşımamıza olanak sağlayan fonksiyonumuz
void Obek::yukariTasi(int indis)
{
// indisimizdeki değer ebeveyninden küçük olduğu sürece
while ((indis > 0) && (ebeveyn(indis) >= 0) && (obek[ebeveyn(indis)] > obek[indis]))
{
// ebeveyni ile takas işlemini gerçekleştiriyoruz
int gecici = obek[ebeveyn(indis)];
obek[ebeveyn(indis)] = obek[indis];
obek[indis] = gecici;
indis = ebeveyn(indis);
}
}

// elemanlarımızı aşağıya taşımamıza olanak sağlayan fonksiyonumuz
void Obek::asagiTasi(int indis)
{
// yerine taşınılacak uygun çocuğu buluyoruz
int cocuk = sol(indis);

if ((cocuk > 0) && (sag(indis) > 0) && (obek[cocuk] > obek[sag(indis)]))
{
cocuk = sag(indis);
}

if (cocuk > 0)
{
// uygun çocuk ile takas işlemini gerçekleştiriyoruz
int gecici = obek[indis];
obek[indis] = obek[cocuk];
obek[cocuk] = gecici;
asagiTasi(cocuk);
}
}

int main()
{
// öbeğimizi oluşturuyoruz
Obek* kucukObek = new Obek();

// oluşturduğumuz öbeğe rastgele sırayla çeşitli değerler ekliyoruz
kucukObek->ekle(7);
kucukObek->yazdir();
kucukObek->ekle(5);
kucukObek->yazdir();
kucukObek->ekle(1);
kucukObek->yazdir();
kucukObek->ekle(8);
kucukObek->yazdir();
kucukObek->ekle(2);
kucukObek->yazdir();
kucukObek->ekle(4);
kucukObek->yazdir();
kucukObek->ekle(9);
kucukObek->yazdir();
kucukObek->ekle(10);
kucukObek->yazdir();
kucukObek->ekle(3);
kucukObek->yazdir();
kucukObek->ekle(6);
kucukObek->yazdir();

// sırayla öbekteki en küçük değerleri yazdırıyoruz
int obekBoyutu = kucukObek->boyut();

for (int i = 0; i < obekBoyutu; i++)
cout << "Öbekteki en küçük değer: " << kucukObek->enKucuguSil() << endl;

// oluşturduğumuz öbeği bellekten temizliyoruz
delete kucukObek;

getchar();
}

Böylece Öbek yapısının üzerinden geçmiş olduk. Sonraki yazılarda görüşmek üzere.