Priority Queue Using Binary Heap

Priority Queue

Priority queue her elemanın öncelik değerinin olduğu bir queue çeşitidir. Geleneksel queue’dan farklı olarak queue elemanlarının önceliklerine göre sıralanırlar.

Bir diziye sıralı bir şekilde eleman eklemek de aslında bir priority’dir diyebiliriz. Burada dikkat etmemiz gereken önceliği büyük olan elemanların mı yoksa küçük olan elemanların mı öncelikli eleman olacağıdır.

İşte burada karşımıza 2 tip priority queue karşımıza çıkıyor:

1- Max-Priority Queue: Bu priority queue’da yüksek değerli elemanların daha yüksek önceliğe sahip olması uygulanır.

[20,15,30,22,1,3,5,8,14] şeklinde bir queue ele aldığımızda 30 elemanının en yüksek önceliğe sahip olduğunu söyleyebiliriz.

Array’e dönüştürülen bir max-priority queue’da:

Root index = 0

Left Child Index = (2*i) +1 = 1

Right Child Index = (2*i) + 2 = 2

Parent Index = (i-1) / 2

2- Min-Priority Queue: Bu PQ’da düşük değerli elemanların daha yüksek önceliğe sahip olduğunu söyleyebiliriz.

Aynı şekilde min-priority queue için formüller:

Root Index : 1

Left Child Index : 2*i = 2

Right Child Index : (2* İ) + 1 = 3

Parent Index = (i/2)

Aynı şekilde yukarıdaki diziden 1 değerli elemanın en yüksek önceliğe sahip olduğunu söyleyebiliriz.

Priority Queue, Huffman Codes, Prim’s Algorithm gibi algoritmalarda da kullanılmaktadır. (ilerleyen yazılarımda bu algoritmalara da değineceğim)

Priority queue linked list veya dizi kullanılarak da tanımlanabilir ancak ben bu yazımda en çok yaygın olarak kullanılan Binary Heap kullanımını inceleyeceğim.

Heaplerin Priority queue konusunda daha iyi olmasının sebebi, enQueue ve deQueue (önceki yazımda kodları var) işlemlerinde karmaşıklığının daha düşük olmasıdır.

Dengeli bir binary search tree Big O değeri (log n) olacaktır.

Priority queue, binary tree şeklinde (bst şartı aranmadan) yapılabilirler. Priority queue için bir çok yol vardır. Ancak binary heap ile oluşturduğumuzda arraylere veya linked listlere göre daha iyi bir Big O (log n) sağlayabiliriz.

Priority queue verilerini, elemanlarının değerlerine göre spesifik şekilde  bir sıralanma ile sıralar. Yani, PQ’ya yeni bir eleman ekleneceği zaman diğer elemanların da öncelikleri değişecektir. Insert işleminde dikkat etmemiz gereken husus budur.

Aşağıda paylaşacağım kodu anlaşılırlığı kolay olsun diye önceden inceleyelim.

Insert

Insert işlemini bir dizi üzerinden inceleyelim. Main’de insert fonksiyonunu çeşitli sayılar ile çağırıyoruz. İlk eklenecek olan sayı [20]. Heap_size adında bir değişkenimizi 1 arttırıyoruz çünkü array olarak göstersek de aslında bir ağaç görüntüsü istediğimiz için 1. indisteki değerimizi root (kök) gibi düşünmeliyiz.

İkinci eklenecek olan sayı [15] tekrardan heap_size++ işlemi uygulanıp, 2. indise ekleniyor. decreaseKey adındaki fonksiyon çağrıldıktan sonra parentNode eğer eklenecek nodedan daha büyük olursa, ikisinin yerleri değişiyor. Aynı şekilde adımlar buna göre devam ediyor. Başlangıç indisinin 1 olduğunu ve bunun ağacın kökü olduğunu da bilmemiz gerekiyor. parentNode, leftChildNode değişkenlerini ise yukarıda belirtmiştim.

Koddan bağımsız olarak bir insert işlemini aşağıdaki şekillerden görebiliriz:

Delete

Min-Priority-Queue kullandığımız için silinecek olan eleman en küçük elemandır. En küçük elemanı silmek için ilk elemanın yerine son eleman atılır ve minHeap adında heap içerisini düzenleyen bir fonksiyon çağırılır.

Aynı şekilde koddan bağımsız olarak şekiller üzerinden bir silme işlemini şekillerden görebiliriz.

Diğer Fonksiyonlar için

Fonksiyonlarda yorum satırı olarak belirtmeye çalıştım.

Aşağıda minimum priority queue için C kodunu paylaşıyorum.

 

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define INF INT_MAX

int tree_size = 20;
int heap_size = 0;

void swap(int *a, int *b){
    int temporary;
    temporary = *a;
    *a = *b;
    *b = temporary;
}

int getRightChildNode(int array[], int index){
    if ((((2*index)+1) < tree_size) && index >= 1) 
        return (2*index)+1; 
    
    return -1;
}

int getLeftChildNode(int array[], int index){
    if ((((2*index)) < tree_size) && index >= 1)
        return 2*index;
    
    return -1;
}

int getParentNode(int array[], int index){
    if((index>1) && (index < tree_size))
        return index/2;
    return -1;
}

void minHeap(int array[], int index){ // ekleme veya silme işlemlerinden sonra ağaç içi dengeyi sağlamak amaçlı fonksiyon 
    int leftChildIndex = getLeftChildNode(array, index);
    int rightChildIndex = getRightChildNode(array, index);
    
    int smallestIndex = index;
    
    if((leftChildIndex <= heap_size) && (leftChildIndex > 0)){
        if(array[leftChildIndex] < array[smallestIndex]){ 
            smallestIndex = leftChildIndex;
        }
    }
    
    if((rightChildIndex <= heap_size) && (leftChildIndex > 0)){

        if(array[rightChildIndex] < array[smallestIndex]){
            smallestIndex = rightChildIndex;
        }
    }
    
    if (smallestIndex != index) {
        swap(&array[index], &array[smallestIndex]);
        minHeap(array, smallestIndex);
    }
    
}



int minimum(int array[]){
    return array[1];
}

int delMin(int array[]){
    int min = array[1];
    array[1] = array[heap_size];
    heap_size--;
    minHeap(array, 1);
    return min;
}

void decreaseKey(int array[],int index,int key){
    array[index] = key;
    while ((index>1) && (array[getParentNode(array, index)] > array[index])) {
        swap(&array[index], &array[getParentNode(array, index)]);
        index = getParentNode(array, index);
    }
    
}

void increaseKey(int array[], int index, int key){
    array[index] = key;
    minHeap(array, index);
    
}

void insert(int array[], int key){
    heap_size++;
    array[heap_size] = INF;
    decreaseKey(array, heap_size, key);
}

void printHeap(int array[]){
    for (int i=1; i<= heap_size; i++) {
        printf("[%d] ",array[i]);
    }
    
}

int main(int argc, const char * argv[]) {
    int array[tree_size];
    insert(array, 20);
    insert(array, 15);
    insert(array, 8);
    insert(array, 10);
    insert(array, 5);
    insert(array, 7);
    insert(array, 6);
    
    printf("*** Current Heap ***\n");
    printHeap(array);
    
    increaseKey(array, 5, 22);
    printf("\n*** After Increase the element [22] ***\n");
    printHeap(array);
    
    printf("\nMinumum value is [%d]", minimum(array));
    printf("\nSo Delete [%d]\n", delMin(array));
    printf("***After delete element [1]***\n");
    printHeap(array);
    printf("\n");
    printf("1st deleted element [%d]\n",delMin(array));
    printf("***After delete elements last view of heap***\n");
    printHeap(array);
    printf("\n");
    printf("2nd deleted element [%d]\n",delMin(array));
    printf("3th deleted element [%d]\n",delMin(array));
    printf("4th deleted element [%d]\n",delMin(array));
    printf("5th deleted element [%d]\n",delMin(array));
    printf("***After delete elements last view of heap***\n");
    printHeap(array);
    
   
}

Bir cevap yazın

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