Skip to content
The Chat Archive
gpt-3.5-turbo-0613· OpenAI WildChat-4.8M (AI2)

Требуется разработать на языке С++, без использования сторонних библиотек (стандартные…

  1. User

    Требуется разработать на языке С++, без использования сторонних библиотек (стандартные заголовочные файлы сторонними не являются!), фреймворков и стандартной библиотеки шаблонов следующую программу работы с кучей. В классе должны быть описаны методы добавления, поиска и удаления узла.

  2. Assistant

    Вот пример реализации класса кучи (heap) на языке C++:

    #include <iostream>
    #include <vector>
    
    class Heap {
    private:
        std::vector<int> heap;
    
    public:
        void insert(int value) {
            // Добавление узла в кучу
            heap.push_back(value);
            int index = heap.size() - 1;
            int parentIndex = (index - 1) / 2;
    
            // Поддержание свойства кучи (heap property)
            while (index > 0 && heap[index] > heap[parentIndex]) {
                std::swap(heap[index], heap[parentIndex]);
                index = parentIndex;
                parentIndex = (index - 1) / 2;
            }
        }
    
        bool search(int value) {
            // Поиск узла в куче
            for (int i = 0; i < heap.size(); i++) {
                if (heap[i] == value) {
                    return true;
                }
            }
            return false;
        }
    
        void remove(int value) {
            // Удаление узла из кучи
            int index = -1;
            for (int i = 0; i < heap.size(); i++) {
                if (heap[i] == value) {
                    index = i;
                    break;
                }
            }
    
            if (index == -1) {
                std::cout << "Узел не найден в куче" << std::endl;
                return;
            }
    
            heap[index] = heap[heap.size() - 1];
            heap.pop_back();
    
            int parentIndex = index;
            int leftChildIndex = 2 * parentIndex + 1;
            int rightChildIndex = 2 * parentIndex + 2;
    
            // Поддержание свойства кучи (heap property)
            while ((leftChildIndex < heap.size() && heap[parentIndex] < heap[leftChildIndex])
                || (rightChildIndex < heap.size() && heap[parentIndex] < heap[rightChildIndex])) {
                if (rightChildIndex < heap.size() && heap[rightChildIndex] > heap[leftChildIndex]) {
                    std::swap(heap[parentIndex], heap[rightChildIndex]);
                    parentIndex = rightChildIndex;
                } else {
                    std::swap(heap[parentIndex], heap[leftChildIndex]);
                    parentIndex = leftChildIndex;
                }
                leftChildIndex = 2 * parentIndex + 1;
                rightChildIndex = 2 * parentIndex + 2;
            }
        }
    };
    

    Пример использования класса кучи:

    int main() {
        Heap heap;
    
        heap.insert(5);
        heap.insert(3);
        heap.insert(8);
        heap.insert(2);
        heap.insert(1);
    
        std::cout << "Поиск узла 8: " << (heap.search(8) ? "найден" : "не найден") << std::endl;
        std::cout << "Поиск узла 10: " << (heap.search(10) ? "найден" : "не найден") << std::endl;
    
        heap.remove(8);
    
        std::cout << "Поиск узла 8 после удаления: " << (heap.search(8) ? "найден" : "не найден") << std::endl;
    
        return 0;
    }
    

    В этом примере создается объект класса Heap и добавляются значения в кучу с помощью метода insert(). Затем выполняется поиск значения с помощью метода search(). Затем значение удаляется с помощью метода remove(). Результаты поиска выводятся на экран.