sort_heap

Статья
06/09/2015

Преобразует кучу в упорядоченный диапазон.

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

Параметры

_First
Произвольно-доступный итератор слишком позицию первого элемента в куче целевого объекта.
_Last
Произвольно-доступный итератор слишком положение за одно окончательное элементом в куче целевого объекта.
_Comp
Определяемый пользователем объект функции предиката, который определяет, в каком смысле один элемент меньше другого. Двоичный предикат принимает два аргумента и возвращает true , если он удовлетворяется, и false, если не удовлетворяется.

Заметки

Кучи 2 имеют свойства:

Первый элемент всегда является наибольшим.
Элементы могут быть добавлены или удалены в логарифмическом времени.

После приложения, если этот алгоритм, диапазон он был применен к, то больше не куча.

Это нестабильная сортировка, поскольку эквивалентности относительный порядок элементов не обязательно сохраняется.

Кучи идеальный способ реализации очереди приоритета и используются в реализации переходники класс priority_queue контейнера стандартной библиотеки шаблонов.

Указанный диапазон должен быть допустимым; все указатели должны быть dereferenceable и внутри последовательности последнего положения доступен из первого инкрементацией.

Сложность не более одного журнала N N, где N = (_Last — _First).

Пример

// 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);
}

Пример результатов выполнения

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 )

Требования

Заголовок: <algorithm>

Пространство имен: std

См. также

Ссылки

heap

Библиотека стандартных шаблонов

Поделиться через