STL Heap Algoritmaları

Giriş
STL algoritmalarını işlevlerine göre gruplamak anlamayı çok daha kolaylaştırıyor. Aşağıdaki algoritmalar heap kullanımını gösteriyor. Heap bir grup içinde en büyük veya en küçük değere sahip olan nesneyi bulabilmek için kullanılır. Genellikle priority queue gibi veri yapılarında işe yarar.

make_heap metodu
Verilen veri yapısını en büyük/en küçük eleman en önde olacak şekilde sıralar. Metodun imzası şöyledir.

template <class RandomAccessIterator>
  void make_heap ( RandomAccessIterator first, RandomAccessIterator last );

Yani sadece vector veya array gibi yapılarda kullanılabilir.Sıralama için comparator da kullanılabilir. Binary Search Tree'den  farklı olarak en öndeki elemanın ardından gelenlerin sıralı olması beklenmemelidir!

"Heaps are a sort of binary tree that is normally stored in an array (vector). A heap is not actually maintained sorted; the element at the front is always the min (or it could be max); and there is an operation normally called re-heapify that takes log n time to restore the heap property after an element is added or removed. Removal is only from the front."

make_heap(), priority_queue'dan farklı olarak birkaç işlemin arka arkaya yapılmasına müsade ettiği için daha verimli olabilir. Şöyle yaparız.

vector<int> v{4,3,7,1,5};
make_heap(v.rbegin(), v.rend(), greater<int>());

q.pop_back();
q.push_back (9);

make_heap(v.rbegin(), v.rend(), greater<int>());

Örnek 1
En küçük eleman iterator'ün başladığı yerde olsun istersek şöyle yaparız.

vector<int> v{4,3,7,1,5};
make_heap(v.begin(), v.end(), greater<int>());

En sonda olsun istersek rbegin(),rend() kullanırız. Şöyle yaparız.

vector<int> v{4,3,7,1,5};
make_heap(v.rbegin(), v.rend(), greater<int>());

Örnek 2
Bir dizi şöyle heap yapılır.

struct MyComparator
{
    bool operator()(const&... lhs, const& ...rhs) const
    {
        return ...;
    }
};

std::vector<...>>    heap;
heap.push_back(...);


// Make a heap so the smallest value is on top.
std::make_heap(std::begin(heap), std::end(heap), MyComparator());

pop_heap metodu
Yukarıdaki örnekten devam edersek

std::push_heap(std::begin(heap), std::end(heap), MyComparator());

push_heap metodu
Yukarıdaki örnekten devam edersek

std::pop_heap(std::begin(heap), std::end(heap), countTester);

sort_heap metodu
Açıklaması şöyle

std::sort_heap requires ValueSwappable. In other words, it should be able to modify elements in-place through the iterator