Рубрики

Как реализовать Min Heap с использованием STL?

В C ++ STL существует priority_queue, который можно напрямую использовать для реализации Max Heap. Смотрите ниже пример.

// C ++ программа, чтобы показать, что
// по умолчанию Max Heap
#include <bits/stdc++.h>

using namespace std;

  
// Код драйвера

int main ()

{

    // Создает максимальную кучу

    priority_queue <int> pq;

    pq.push(5);

    pq.push(1);

    pq.push(10);

    pq.push(30);

    pq.push(20);

  

    // извлекаем элементы по одной из максимальной кучи

    while (pq.empty() == false)

    {

        cout << pq.top() << " ";

        pq.pop();

    }

  

    return 0;

}

Выход :

30 20 10 5 1

Поскольку элементы печатаются в порядке убывания, у нас по умолчанию максимальная куча.

Как реализовать Min Heap?
priority_queue поддерживает конструктор, который требует двух дополнительных аргументов, чтобы сделать его min heap.

    priority_queue <Type, vector<Type>, ComparisonType > min_heap;

`

Ниже приведен пример для целых чисел.

// C ++ программа для использования priority_queue для реализации min heap
#include <bits/stdc++.h>

using namespace std;

  
// Код драйвера

int main ()

{

    // Создаем кучу мин

    priority_queue <int, vector<int>, greater<int> > pq;

    pq.push(5);

    pq.push(1);

    pq.push(10);

    pq.push(30);

    pq.push(20);

  

    // один за другим извлекаем элементы из минимальной кучи

    while (pq.empty() == false)

    {

        cout << pq.top() << " ";

        pq.pop();

    }

  

    return 0;

}

Выход :

1 5 10 20 30 

Как сделать минимальную кучу пользовательского класса?
Рассмотрим ниже пример, где мы строим минимальную кучу из 2 точек D, упорядоченных по оси X.

// C ++ программа для использования priority_queue для реализации Min Heap
// для определенного пользователем класса
#include <bits/stdc++.h>

using namespace std;

  
// Пользовательский класс, Point

class Point

{

   int x;

   int y;

public:

   Point(int _x, int _y)

   {

      x = _x;

      y = _y;

   }

   int getX() const { return x; }

   int getY() const { return y; }

};

  
// Для сравнения двух точек

class myComparator

{

public:

    int operator() (const Point& p1, const Point& p2)

    {

        return p1.getX() > p2.getX();

    }

};

  
// Код драйвера

int main ()

{

    // Создаем кучу точек Min (порядок по координате x)

    priority_queue <Point, vector<Point>, myComparator > pq;

  

    // Вставляем точки в минимальную кучу

    pq.push(Point(10, 2));

    pq.push(Point(2, 1));

    pq.push(Point(1, 5));

  

    // один за другим извлекаем элементы из минимальной кучи

    while (pq.empty() == false)

    {

        Point p = pq.top();

        cout << "(" << p.getX() << ", " << p.getY() << ")";

        cout << endl;

        pq.pop();

    }

  

    return 0;

}

Выход :

(1, 5)
(2, 1)
(10, 2)

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Как реализовать Min Heap с использованием STL?

0.00 (0%) 0 votes