STL: купа

Купу в STL реалізовано за принципом max-heap. При такій організації ключ елемента більше або дорівнює ключам дочірніх елементів. Завдяки цьому перший елемент купи є найбільшим елементом. При цьому дочірні елементи не мають бути відсортованими відносно одне одного.

Функції для роботи з купою (алгоритми)

Усі алгоритми очикують правильно організовану купу в якості параметрів. Список і іноді масив не можуть бути використаними оскільки перелічені алгоритми вимагають випадкового доступу до елементів та зміни розміру купи.

make_heap

Створює купу з вказаної послідовності на місці. Можна вказати власну функцію порівняння.

pop_heap

Перевпорядковує купу переміщуючи найбільший (перший) елемент в кінець. Доступ до елемента можна отримати за допомогою back(), вилучити елемент можна за допомогою pop_back().

push_heap

Перевпорядковує купу розміщуючи останній елемент, який повинно бути додано в останню позицію попередньо.

sort_heap

Сортує купу. Після сортування купа стає не валідною.

Приклад використання алгоритмів

int a[] = {12, 9, 8, 4, 6, 7, 5, 0, -1, 2, 3 }; size_t size = sizeof(a) / sizeof(a[0]); vector<int> v(a, a + size); make_heap(a, a + size); copy(a, a + size, ostream_iterator<int>(cout, " ")); cout << endl; // 12 9 8 4 6 7 5 0 -1 2 3 sort_heap(a, a + size); copy(a, a + size, ostream_iterator<int>(cout, " ")); cout << endl; // -1 0 2 3 4 5 6 7 8 9 12 make_heap(v.begin(), v.end()); v.push_back(10); push_heap(v.begin(), v.end()); copy(v.begin(), v.end(), ostream_iterator<int>(cout, " ")); cout << endl; // 12 9 10 4 6 8 5 0 -1 2 3 7 pop_heap(v.begin(), v.end()); copy(v.begin(), v.end(), ostream_iterator<int>(cout, " ")); cout << endl; // 10 9 8 4 6 7 5 0 -1 2 3 12

Один коментар для “STL: купа”

Залишити відповідь

Зайти з допомогою: