C++, Theory, Visual C++

C++. STL. Algorithms for working with data, which are presented according to the “heap” principle

Algorithms for working with data, which are presented according to the “heap” principle. Examples

Contents

Search other resources:

1. Загальні відомості про клас vector. Огляд методів класу

Клас vector представляє собою динамічний масив, розмір якого у програмі може змінюватись при необхідності. Цей клас є одним з найбільш універсальних та поширених у використанні при написанні програм на C++. Доступ до елементів класу здійснюється як до звичайного масиву з допомогою квадратних дужок [ ].

1. Algorithm make_heap. Prepare a sequence for use as a heap

The make_heap algorithm has two overloaded implementations, which are declared as follows

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

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

where

  • first – random access iterator. This iterator points to the first element of the range to be converted into a “heap”;
  • last – random access iterator. This iterator points to the position one past the last element of the range that is being converted to a “heap”;
  • pred – binary predicate that specifies the condition under which one element is less than another. If the condition is true, then the predicate returns true, otherwise it returns false.

Example.

#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;

int main()
{
  // The make_heap algorithm - Create a heap based on a given sequence.
  // In a heap, the first element is the largest (smallest) and also
  // the sorting criterion can be determined by a binary predicate.

  // 1. Using an algorithm without a predicate
  // 1.1. Declare a vector and output it
  vector<int> V1 = { 2, 1, 3, 2, 4, 5, 2, 1, 3, 0 };

  vector<int>::iterator it = V1.begin();
  cout << "V1 => ";
  while (it != V1.end())
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;

  // 1.2. Create a heap from a sequence
  make_heap(V1.begin(), V1.end());

  // 1.3. Display V1
  cout << "V1 => ";

  for (int i : V1)
    cout << i << " ";
  cout << endl;

  // 2. Using the algorithm with the standard predicate
  // 2.1. Declare another vector and output it
  vector<int> V2 = { 2, 1, 3, 2, 4, 5, 2, 1, 3, 0 };

  it = V2.begin();
  cout << "V2 => ";
  while (it != V2.end())
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;

  // 2.2. Create a heap based on the standard less predicate
  make_heap(V2.begin(), V2.end(), less<int>());

  // 2.3. Output the vector
  it = V2.begin();
  cout << "V2 => ";
  while (it != V2.end())
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;
}

Result

V1 => 2 1 3 2 4 5 2 1 3 0
V1 => 5 4 3 3 1 2 2 1 2 0
V2 => 2 1 3 2 4 5 2 1 3 0
V2 => 5 4 3 3 1 2 2 1 2 0

  ⇑

2. Algotithm push_heap. Add last element to existing “heap”

The algorithm has two implementations

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

template <class RandomAccessIterator, class BinaryPredicate>
void push_heap(
  RandomAccessIterator first,
  RandomAccessIterator last,
  BinaryPredicate pred );

where

  • first, last – random access iterators pointing respectively to the first and last elements of the range considered as a potential “heap”;
  • pred – a binary predicate that returns true if the first element is less than the other.

Example.

#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;

void PrintVector(vector<int>& V, string msg)
{
  cout << msg << " => ";
  for (int i : V)
    cout << i << " ";
  cout << endl;
}

int main()
{
  // push_heap algorithm - Add the element to existing heap, the heap is modified.
  // In the heap, first element is the largest (smallest) and also
  // the sorting criterion can be determined by a binary predicate.

  // 1. Using the algorithm without the predicate
  // 1.1. Declare a vector and output it
  vector<int> V1 = { 2, 1, 3, 4 };
  PrintVector(V1, "V1");

  // 1.2. Create a "heap" (heap) from the sequence.
  make_heap(V1.begin(), V1.end());
  PrintVector(V1, "make_heap(V1)");

  // 1.3. Add element to sequence and output sequence again.
  V1.push_back(23);
  PrintVector(V1, "V1+1");

  // 1.4. Add element to existing heap.
  push_heap(V1.begin(), V1.end());
  PrintVector(V1, "V1.push_heap");

  // 2. Using the algorithm with the standard greater predicate
  // 2.1. Create a vector
  vector<int> V2 = { 5, 9, 7, 3 };
  PrintVector(V2, "V2");

  // 2.2. Create a heap
  make_heap(V2.begin(), V2.end());
  PrintVector(V2, "make_heap(V2)");

  // 2.3. Add element to sequence V2
  V2.push_back(4);
  PrintVector(V2, "V2+1");

  // 2.4. Add element to existing heap - greater predicate
  push_heap(V2.begin(), V2.end(), greater<int>());
  PrintVector(V2, "push_heap(V2)");
}

Result

V1 => 2 1 3 4
make_heap(V1) => 4 2 3 1
V1+1 => 4 2 3 1 23
V1.push_heap => 23 4 3 1 2
V2 => 5 9 7 3
make_heap(V2) => 9 5 7 3
V2+1 => 9 5 7 3 4
push_heap(V2) => 4 9 7 3 5

  ⇑

3. Algorithm pop_heap. Remove the largest element from the beginning of the heap to the position that follows the last in the range, and then form a new heap from the remaining elements

The pop_heap algorithm has two overloaded implementations that differ in the absence/presence of a predicate:

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

template <class RandomAccessIterator, class BinaryPredicate>
void pop_heap(
  RandomAccessIterator first,
  RandomAccessIterator last,
  BinaryPredicate pred);

where

  • first, last – random access iterators pointing respectively to the first and last elements of the range considered as a potential “heap”;
  • pred – binary predicate that returns true if the first element is less than the other.

Example.

#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;

void PrintVector(vector<int>& V, string msg)
{
  cout << msg << " => ";
  for (int i : V)
    cout << i << " ";
  cout << endl;
}

int main()
{
  // The pop_heap algorithm is to remove the largest element from the heap with its further rebuilding.
  // In a heap, the first element is the largest (smallest) and also
  // the sorting criterion can be determined by a binary predicate.

  // 1. Using an algorithm without a predicate
  // 1.1. Declare vector and output it
  vector<int> V1 = { 2, 1, 3, 4 };
  PrintVector(V1, "V1");

  // 1.2. Create a "heap" (heap) from the sequence
  make_heap(V1.begin(), V1.end());
  PrintVector(V1, "make_heap(V1)");

  // 1.3. Add an element to the sequence and output the sequence again
  V1.push_back(23);
  PrintVector(V1, "V1+1");

  // 1.4. Add element to existing heap
  push_heap(V1.begin(), V1.end());
  PrintVector(V1, "V1.push_heap");

  // 1.5. Pop the largest element from existing heap - pop_heap algorithm
  pop_heap(V1.begin(), V1.end());
  V1.resize(V1.size() - 1);
  PrintVector(V1, "V1.pop_heap");

  // 2. Using the algorithm with the standard greater predicate
  // 2.1. Create a vector
  vector<int> V2 = { 5, 9, 7, 3 };
  PrintVector(V2, "V2");

  // 2.2. Create a heap
  make_heap(V2.begin(), V2.end());
  PrintVector(V2, "make_heap(V2)");

  // 2.3. Add element to the sequence V2
  V2.push_back(4);
  PrintVector(V2, "V2+1");

  // 2.4. Add element to existing heap - greater predicate
  push_heap(V2.begin(), V2.end(), greater<int>());
  PrintVector(V2, "push_heap(V2)");

  // 2.5. Pull the largest element from the existing heap
  pop_heap(V2.begin(), V2.end(), greater<int>());
  V2.resize(V2.size() - 1);
  PrintVector(V2, "V2.pop_heap");
}

Result

V1 => 2 1 3 4
make_heap(V1) => 4 2 3 1
V1+1 => 4 2 3 1 23
V1.push_heap => 23 4 3 1 2
V1.pop_heap => 4 2 3 1
V2 => 5 9 7 3
make_heap(V2) => 9 5 7 3
V2+1 => 9 5 7 3 4
push_heap(V2) => 4 9 7 3 5
V2.pop_heap => 5 9 7 3

  ⇑

4. Algorithm sort_heap. Sort the numbers in the “heap”

The algorithm has two overloaded implementations

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

template <class RandomAccessIterator, class Compare>
void sort_heap(
  RandomAccessIterator first,
  RandomAccessIterator last,
  Compare pred);

where

  • first, last – random access iterators pointing respectively to the first and last elements of the range considered as a potential “heap”;
  • pred – a binary predicate that returns true if the first element is less than the second.

Example.

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <ostream>
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()
{
  // The sort_heap algorithm - sort numbers in heap

  // 1. Create a vector and display it
  vector<int> V1 = { 2, -1, 3, 8, 4, 0, 5, 3, 1 };
  print("V1", V1);

  // 2. Convert sequence V1 to heap
  make_heap(V1.begin(), V1.end());

  // 3. Sort numbers in the "heap"
  sort_heap(V1.begin(), V1.end());

  // 4. Display the result
  print("sort_heap(V1)", V1);
}

Result

V1 => 2 -1 3 8 4 0 5 3 1
sort_heap(V1) => -1 0 1 2 3 3 4 5 8

  ⇑

Related topics

  ⇑