Yığın Ağacı (Heap)

Yazan : Şadi Evren ŞEKER

Yığın ağacı bilgisayar bilimlerinde özellikle sıralama amacıyla çokca kullanılan bir veri yapısıdır. Bu veri yapısı üst düğümün (atasının) alt düğümlerden (çocuklarından) her zaman büyük olduğu bir ikili ağaç (binary tree) şeklinde düşünülebilir.

Aşağıda örnek bir yığın ağacı verilmiştir:

Yukarıdaki ikili ağaçta dikkat edilirse ağaç dengeli bir şekilde sırayla doldurulmuştur. Buna göre yeni bir eleman daha eklenmesi durumunda ağacın eleman sayısı 7’ye yükselecek ve sayıların yeri değişmekle birlikte yeni eleman şu andaki 18 sayısını içeren düğümün sağına gelecektir.

Yığın ağaçları her zaman sırayla dolar ve sırayla boşalır.

Yukarıdaki ağacın bir dizi ile tutulması da mümkündür.

Ayrıca herhangi bir ağacı yığın ağacına çevirmek (yığınlamak, heapify) de mümkündür ve bu işlem bir yığın ağacı oluşturma işleminin temelini oluşturur. Basitçe yığın ağacına yapılan her ekleme ve her çıkarma işleminden sonra bu yığınlama (heapify) işlemi yapılarak yığın ağacının formunu koruması sağlanmalıdır.

Aşağıda java dilinde bir yığınlama (heapify) fonksiyonu verilmiştir:

public void heapify(int[]A,int i)
  {
        int largest = 0;
    int le=left(i);
    int ri=right(i);
    if((le<=heapsize) && (A[le]>A[i]))
        largest = le;
    else
        largest = i;
    if((ri<=heapsize) && A[ri]>A[largest])
        largest = ri;

    if (largest != i) {
      int tmp = A[i];
      A[i]= A[largest];
      A[largest] = tmp;
      heapify(A, largest);
   }
  }
  public static int left(int i ){
      return 2*(i+1)-1;
  }

  public static int right(int i){
      return 2*(i+1);
  }

Dolayısıyla yukarıdaki yığınlama (heapify) fonksiyonu kullanarak bir yığın ağacı oluşturmak aşağıdaki şekildem mümkün olabilir:

public void BuildHeap(int[]A){

  heapsize=A.length-1;
  for(int i=0; i<Math.floor(A.length/2); i++)
  {
          heapify(A,i);
  }
}

Yorumlar

  1. yardım

    merhaba,
    bu java kodunu assemblye çevirmeye çalışıyorum,kodunuzu denemeden baya uğraştım fakat assembly de sorun olunca sizin kodunuzu denedim,ve doğru sonucu vermediğini farkettim.
    nerede hata oldugunu da çözemedim
    çalışan kodu acil olarak mailime ulaştırabilirmisiniz,yardım ederseniz çok sevinirim
    (bu arada bana minimum dan başlayarak sıralayan kod lazım ama eşitlikleri değiştirince aynı işi görür sanırım)

  2. Şadi Evren ŞEKER Article Author

    Evet min heap ve max heap arasındaki fark eşitlik kontrolüdür, ancak nasıl bir hata ile karşaıltığınızı anlayamadım. Kodda hata olabilir belki gözden kaçan bir durum (gerçi test etmiştim bu kodu yazıya eklemeden önce ama hata olması her zaman mümkün). Tam olarak nasıl bir durumda hata ile karşılaştığınızı yazarsanız düzeltip yardımcı olmaya çalışayım.

    Başarılar

  3. Emre

    Merhaba hocam,

    Anlamadığım bir konu var. BuildHeap(int[]A) methodu O(n) zamanda mı çalışıyor yoksa Heap sorting time complexitysi olan O(n log (n)) zamanda mı?

  4. Safa

    arkadaşlar merhaba ben ikili arama ağacına heap ağacını eklemek istiyorum. daha açık bir şekilde anlatmak gerekirse benim bir ülke verilerim var bir de şehir verilerim ülke verilerini ikili arama ağacına ekleyip şehir verilerini de her şehir kendi ülkesine bağlı olacak şekilde heap ağacına atmak istiyorum ardımcı olursanız çok sevinirim.

  5. çakın

    selam a.

    sorumu yazmak için en uygun burayı buldum.
    -Union by size N elemanlı bir ağacın sahip alabileceği maksimum yüksekklik nedir?

  6. Emin Soner TÜRK

    Hocam iyi günler,
    Heap kod analizi ile ilgili bir video çekeceğinizi söylemişsiniz fakat bulamıyorum. Kodu anlayamadım yardımcı olur musunuz?

    package com.company;

    public class Heap_Yapisi {
    public static class Node
    {
    private int iData;
    public Node(int key) { iData = key; }
    public int getKey() { return iData; }
    public void setKey(int id)
    { iData = id; }
    }

    public static class Heap
    {
    private Node[] heapArray;
    private int maxSize;
    private int currentSize;

    public Heap(int mx) {
    maxSize = mx;
    currentSize = 0;
    heapArray = new Node[maxSize];
    }

    public boolean isEmpty()
    { return currentSize==0; }

    public boolean insert(int key) {
    if(currentSize==maxSize)
    return false;
    Node newNode = new Node(key);
    heapArray[currentSize] = newNode;
    trickleUp(currentSize++);
    return true; //Başarılı olur.
    }

    public void trickleUp(int index) {
    int parent = (index-1) / 2;
    Node bottom = heapArray[index];
    while( index > 0 && heapArray[parent].getKey() < bottom.getKey()) {
    heapArray[index] = heapArray[parent];
    index = parent;
    parent = (parent-1) / 2;
    }
    heapArray[index] = bottom;
    }

    public int remove() {
    Node root = heapArray[0];
    heapArray[0] = heapArray[–currentSize];
    trickleDown(0);
    return root.getKey();
    }

    public void trickleDown(int index) {
    int largerChild;
    Node top = heapArray[index];
    while(index < currentSize/2) {
    int leftChild = 2*index+1;
    int rightChild = leftChild+1;
    if(rightChild < currentSize && heapArray[leftChild].getKey() = heapArray[largerChild].getKey())
    break;

    heapArray[index] = heapArray[largerChild];
    index = largerChild;
    }
    heapArray[index] = top;
    }

    public boolean change(int index, int newValue) {
    if(index=currentSize)
    return false;
    int oldValue = heapArray[index].getKey();
    heapArray[index].setKey(newValue);
    if(oldValue < newValue)
    trickleUp(index);
    else trickleDown(index);
    return true;
    }
    public void displayHeap() {
    System.out.print("heapArray: ");
    for(int m=0; m 0) {
    if(column == 0)
    for(int k=0; k<nBlanks; k++)
    System.out.print(' ');

    System.out.print(heapArray[j].getKey());
    if(++j == currentSize)
    break;
    if(++column==itemsPerRow) {
    nBlanks /= 2; itemsPerRow *= 2; column = 0; System.out.println(); }
    else
    for(int k=0; k<nBlanks*2-2; k++)
    System.out.print(' ');
    }
    System.out.println("\n"+dots+dots);
    }
    }
    }

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir