Veri Yapıları: Öbek (Heap)

(Son Güncelleme: )
veri yapıları › c++
, , ,

Ö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.