sort_heap

Makale
03/27/2013

Bir yığın sıralanmış bir aralığa dönüştürür.

template<class RandomAccessIterator>
   void sort_heap(
      RandomAccessIterator _First, 
      RandomAccessIterator _Last
   );
template<class RandomAccessIterator, class Predicate>
   void sort_heap(
      RandomAccessIterator _First, 
      RandomAccessIterator _Last,
      Predicate _Comp
   );

Parametreler

_First
İlk öğenin konumunu hedef yığınındaki adresleme rasgele erişim Yineleyici.
_Last
Hedef yığın son öğesinde geçmiş konum adresleme rasgele erişim Yineleyici.
_Comp
Anlamlı bir öðe baþka birinden küçük olduğu tanımlayan kullanıcı tanımlı işlevin doðrulama nesnesi.İkili karşılaştırma iki baðýmsýz deðiþken alýr ve döner doğru memnun, ve yanlış tatmin olduğunda.

Notlar

Yığınlar, iki özellik vardır:

Birinci öğe her zaman büyük olur.
Öğeler eklenebilir veya Logaritmik zamandaki kaldırılmış.

Bu algoritma, aralık uygulandığı, sonra artık bir yığın uygulamasıdır.

Göreli eşdeğer öğelerin sırasını mutlaka korunmaz çünkü bu kararlı bir sıralama değil.

Yığınlar öncelik kuyruğu uygulamak için ideal bir yöntem olduğunu ve standart Şablon Kütüphanesi kapsayıcı Adaptörü uygulamasında kullanılan priority_queue sınıfı.

Başvurulan aralığı geçerli olması gerekir; Tüm işaretçiler dereferenceable ve sıra içinde son konuma birinciden erişilebildiğinden tarafından incrementation.

Karmaşıklığını en çok n günlük n, burada n = (_Last – _First).

Örnek

// alg_sort_heap.cpp
// compile with: /EHsc
#include <algorithm>
#include <functional>
#include <iostream>
#include <ostream>
#include <string>
#include <vector>
using namespace std;

void print(const string& s, const vector<int>& v) {
    cout << s << ": ( ";

    for (auto i = v.begin(); i != v.end(); ++i) {
        cout << *i << " ";
    }

    cout << ")" << endl;
}

int main() {
    vector<int> v;
    for (int i = 1; i <= 9; ++i) {
        v.push_back(i);
    }
    print("Initially", v);

    random_shuffle(v.begin(), v.end());
    print("After random_shuffle", v);

    make_heap(v.begin(), v.end());
    print("     After make_heap", v);

    sort_heap(v.begin(), v.end());
    print("     After sort_heap", v);

    random_shuffle(v.begin(), v.end());
    print("             After random_shuffle", v);

    make_heap(v.begin(), v.end(), greater<int>());
    print("After make_heap with greater<int>", v);

    sort_heap(v.begin(), v.end(), greater<int>());
    print("After sort_heap with greater<int>", v);
}

Örnek Çıktı

Initially: ( 1 2 3 4 5 6 7 8 9 )
After random_shuffle: ( 9 2 7 3 1 6 8 4 5 )
     After make_heap: ( 9 5 8 4 1 6 7 2 3 )
     After sort_heap: ( 1 2 3 4 5 6 7 8 9 )
             After random_shuffle: ( 5 8 3 1 2 9 7 6 4 )
After make_heap with greater<int>: ( 1 2 3 4 5 9 7 6 8 )
After sort_heap with greater<int>: ( 9 8 7 6 5 4 3 2 1 )

Gereksinimler

Başlık: <algorithm>

Namespace: std

Ayrıca bkz.

Başvuru

heap

Standart Şablon Kütüphanesi

Aracılığıyla paylaş