C++ Data Structure Heap

[Sawer]

Data projem için bir öğrenci database'i oluşturmam istendi.Linked list,binary search tree ve heapde bunlar üstünde türlü işlemler yapıcam bla bla.linked listle ile bst bitti.Şimdi heap'e başlıcaktımki heapi hiç anlamadığımı farkettim.İnternettede adam gibi kaynak bulamadım.


bunu wikipedia'dan buldum.Heap hakkında bildiklerim her zaman left childdan right child'e gidiyor.childlar arasında büyüktür,küçüktür ilişkisi yok.max heap yaptığım için root buyuk olucak.Bilmediğim şey şunlar.

1-Diyelim üstteki resimdeki heap'e 60 sayısını eklersem ne olucak.

2-Örnek bir algoritma bulamadım,eğer bulursanız lütfen linkleyin.



3- şimdi bu heapde 20 yi silersem ne olucak. çünkü heapde sol dolu olmalı 15 ile 10 'u sola kaydırmam mı lazım?

bu sorulardan birini bile yanıtlarsanız çok sevinicem.Şimdiden saolun.

[Penthesilea]

heap property diye bisey tum subtreelerde gecerli olacak
bu da complete olmasi her subtree nin + her subtree'nin root'unun, subtree'nin en buyuk key'ine sahip olmasi.

bu sitede cok iyi anlatilmis ondan anlatmiyorum bastan aynisini :)
http://www.cs.auckland.ac.nz/software/AlgAnim/heaps.html

[riglous]

1. Siradaki ilk bos yer, 3'un sol tarafi oldugu icin oraya yazacak. Daha sonra 3'le 60'i karsilastiracaksin, 60 daha buyuk oldugu icin, 3'le 60'in yerleri degisecek. Boylece 60, 19'un sagina geldi. 3'de 60'in solunda. Daha sonra 60'la 19'u karsilastiracaksin. 60 daha buyuk oldugu icin 19'la yer degistirecek (yukaridakiyle ayni islem oldugu icin recursive yapman isi kolaylastiracaktir). Daha sonra tekrar parent'la kontrol ediyorsun, (100 > 60) -> true oldugu icin "swap" yapman gerekmiyor. Boylece stabil oluyor.

2. Penthesilea'nin verdigi linki oku, yine anlamazsan yazalim.

2. kisimda ne demek istedigini anlamadim. Sanirim bosluklar silindigi icin demek istedigin tam olarak cikmamis. Sirasiyla ne insert ettigini yaz, sonra da naaptigini... Ama tahmin ettigimse

3. Yanlis soru sormussun cunku heap'in bir diger adi priority queue'dur. Bunun nedeni queue ozelligi tasimasidir. Yani en tepedeki (root) cikmadan, onun cocuklarini cikaramazsin.

Bu isi array'le mi yapacaksin yoksa linked list'le mi? Iki durumda da insert edilecek yere pointer tutman daha saglikli dusunmeni saglayacaktir. Array'de bu surekli arttigi icin sorun olmaz. Parent'lar icin f(index)=ceil((index-2)/2) formulunu kullanabilirsin. Linked list'te ne yapildigini unutmusum, yaslaniyorum...

[riglous]

Orjinal mesaji degistirme yahu. Ondan sonra edit manyagi oluyoruz..

[Penthesilea]

evet bu arada soruyu ben de anlamamisim resmi cizince anladim, riglous'un dedigi gibi, heap'i sadece kafasindan koparabilirsin.

[Sawer]

eheh

@riglous;
gerçekten çok teşşekkür ederim.bayağa anladım ama şu delete kısmını tam anlamadım.2. resimde(ki paintte çizdim:D) 20'yi silmek için tam olarak ne yapmam lazım.20 yi silip 15'i 20 nin yerine yazdırıp 10'uda solamı kaydırıcam.

@pent verdiğin linki inceliyorum akşama yazarım yapıp yapamadığımı.

saolun.

[riglous]

20'yi silemezsin.
- 40'i silmen lazim. Sen 40'i silince onun yerine 35 gececek.
- 35'i sildin. Yerine 30 gecti.
- 30'u sildin yerine 25 gecti.
- 25'i silince yerine 20 geldi.
- Anca simdi 20'yi silebilirsin.

[riglous]

Penthesilea'nin verdigi linkte cok guzel anlatilmis. 2 fonksiyona ihtiyacin var, biri climb_up digeri climb_down.
- Silince daima en yukaridaki gidiyo ya, pq[tail-1]'i alip en yukari koyuyorsun ve tail=tail-1 diyorsun. Daha sonra da climb_down(0) yapiyosun.

[Sawer]

tamam anladım gerçekten saolun.

[Sawer]

pent'in verdiği site ne güzelmiş ya.Adamlar üşenmemiş animationlı halini koymuşlar.insertion'ı yazdım,yarında delete'i yazıcam.