Как реализовать приоритетную очередь с функциями extractMax и add, которая поддерживает одинаковые элементы?

Для реализации приоритетной очереди с функциями extractMax и add, которая поддерживает одинаковые элементы, можно воспользоваться структурой данных, называемой кучей (Heap). Куча является полным бинарным деревом, в котором каждый узел имеет значение большее (или равное) значению его потомков, а также сохраняет свойство полного дерева (все уровни заполнены, кроме, быть может, самого нижнего, который заполняется слева направо).

Для начала, нужно определить структуру данных, представляющую узел кучи. Узел должен содержать значение (элемент), а также информацию о количестве одинаковых элементов для поддержки элементов с одинаковыми значениями. Для удобства, можно определить эту структуру в виде класса:

class HeapNode {
public:
    int value;
    int count;
};

Здесь value представляет значение элемента, а count - количество одинаковых элементов.

Далее создадим класс PriorityQueue, который будет реализовывать приоритетную очередь с функциями extractMax и add.

class PriorityQueue {
private:
    vector<HeapNode> heap;

    void heapifyUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap[index].value <= heap[parentIndex].value) {
                break;
            }
            swap(heap[index], heap[parentIndex]);
            index = parentIndex;
        }
    }

    void heapifyDown(int index) {
        int n = heap.size();
        while (true) {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
            
            int largestIndex = index;
            if (leftChildIndex < n && heap[leftChildIndex].value > heap[largestIndex].value) {
                largestIndex = leftChildIndex;
            }
            if (rightChildIndex < n && heap[rightChildIndex].value > heap[largestIndex].value) {
                largestIndex = rightChildIndex;
            }
            
            if (largestIndex == index) {
                break;
            }
            
            swap(heap[index], heap[largestIndex]);
            index = largestIndex;
        }
    }

public:
    void add(int value) {
        for (int i = 0; i < heap.size(); i++) {
            if (heap[i].value == value) {
                heap[i].count++;
                return;
            }
        }
        
        HeapNode node;
        node.value = value;
        node.count = 1;
        
        heap.push_back(node);
        heapifyUp(heap.size() - 1);
    }

    int extractMax() {
        if (heap.empty()) {
            throw "PriorityQueue is empty!";
        }
        
        int maxElement = heap[0].value;
        heap[0].count--;
        
        if (heap[0].count == 0) {
            swap(heap[0], heap[heap.size() - 1]);
            heap.pop_back();
            heapifyDown(0);
        }
        
        return maxElement;
    }
};

Класс PriorityQueue содержит приватное поле heap, которое представляет собой вектор узлов кучи.

Метод add позволяет добавить элемент в приоритетную очередь. Он сначала проходит по всем элементам кучи и проверяет, есть ли в них уже элемент с таким же значением. Если да, то увеличивает количество одинаковых элементов данного значения. В противном случае, создает новый узел и добавляет его в конец кучи. Затем, вызывается функция heapifyUp, чтобы восстановить свойства кучи.

Метод extractMax позволяет извлечь максимальный элемент из приоритетной очереди. Если куча пуста, выбрасывается исключение. Первый элемент кучи (с наибольшим значением) уменьшается на единицу, и если его количество становится равным нулю, он заменяется последним элементом в куче. Затем вызывается функция heapifyDown, чтобы восстановить свойства кучи.

Теперь можно использовать класс PriorityQueue для работы с приоритетной очередью, поддерживающей одинаковые элементы:

int main() {
    PriorityQueue priorityQueue;
    
    priorityQueue.add(5);
    priorityQueue.add(10);
    priorityQueue.add(3);
    priorityQueue.add(10);
    priorityQueue.add(7);
    
    int maxElement = priorityQueue.extractMax();
    cout << "Max element: " << maxElement << endl; // Output: Max element: 10
    
    return 0;
}

В этом примере добавлено несколько элементов в приоритетную очередь с использованием метода add. Затем метод extractMax вызывается, чтобы извлечь максимальный элемент, который затем выводится на экран.

Таким образом, приведенный код реализует приоритетную очередь с функциями extractMax и add, которая поддерживает одинаковые элементы.