Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· openaiHugging Face Suzhen/CodeChat

Реализуй заполнение кучи строками в данной программе: #include <iostream> // для вывода…

  1. User

    Реализуй заполнение кучи строками в данной программе: #include // для вывода результатов

    template class Heap { private: T* heap; // массив для хранения узлов кучи int size; // размер кучи public: Heap(); // конструктор по умолчанию ~Heap(); // деструктор

    void insert(T value); // добавить узел в кучу
    bool search(T value); // найти узел в куче
    bool remove(T value); // удалить узел из кучи
    
    void print(); // вывод текущего состояния кучи
    

    };

    template Heap::Heap() { heap = new T[100]; // создаем массив из 100 элементов size = 0; // инициализируем размер кучи }

    template Heap::~Heap() { delete[] heap; // освобождаем память, выделенную для массива }

    template void Heap::insert(T value) { int index = size; // индекс нового узла равен текущему размеру кучи heap[index] = value; // добавляем новый узел в массив

    size++; // увеличиваем размер кучи
    
    // выполняем восстановление свойства кучи (например, с помощью просеивания вверх)
    while (index > 0 && heap[(index - 1) / 2] < heap[index]) {
        std::swap(heap[(index - 1) / 2], heap[index]);
        index = (index - 1) / 2;
    }
    

    }

    template bool Heap::search(T value) { for (int i = 0; i < size; i++) { if (heap[i] == value) { return true; // значение найдено в куче } }

    return false; // значение не найдено
    

    }

    template bool Heap::remove(T value) { for (int i = 0; i < size; i++) { if (heap[i] == value) { // перемещаем последний узел вместо удаляемого heap[i] = heap[size - 1];

            size--; // уменьшаем размер кучи
    
            // выполняем восстановление свойства кучи (например, с помощью просеивания вниз)
            while (true) {
                int left = 2 * i + 1;
                int right = 2 * i + 2;
    
                int largest = i;
    
                if (left < size && heap[left] > heap[largest]) {
                    largest = left;
                }
    
                if (right < size && heap[right] > heap[largest]) {
                    largest = right;
                }
    
                if (largest != i) {
                    std::swap(heap[i], heap[largest]);
                    i = largest;
                }
                else {
                    break;
                }
            }
    
            return true; // узел удален из кучи
        }
    }
    
    return false; // узел не найден
    

    }

    template void Heap::print() { for (int i = 0; i < size; i++) { std::cout << heap[i] << " "; }

    std::cout << std::endl;
    

    }

    int main() { Heap heap;

    heap.insert(1.23);
    heap.insert(1);
    heap.insert(222);
    heap.insert(0.9992);
    
    heap.print(); // выводит: 9 4 6 2
    
    std::cout << heap.search(222) << std::endl; // выводит: 1 (значение 4 найдено)
    std::cout << heap.search(1) << std::endl; // выводит: 0 (значение 8 не найдено)
    
    std::cout << heap.remove(4) << std::endl;
    std::cout << heap.remove(1) << std::endl;
    heap.print(); // выводит: 9 2 6
    
    return 0;
    

    }

  2. Assistant

    #include // для вывода результатов

    template class Heap { private: T* heap; // массив для хранения узлов кучи int size; // размер кучи public: Heap(); // конструктор по умолчанию ~Heap(); // деструктор

    void insert(T value); // добавить узел в кучу
    bool search(T value); // найти узел в куче
    bool remove(T value); // удалить узел из кучи
    
    void print(); // вывод текущего состояния кучи
    

    };

    template Heap::Heap() { heap = new T[100]; // создаем массив из 100 элементов size = 0; // инициализируем размер кучи }

    template Heap::~Heap() { delete[] heap; // освобождаем память, выделенную для массива }

    template void Heap::insert(T value) { int index = size; // индекс нового узла равен текущему размеру кучи heap[index] = value; // добавляем новый узел в массив

    size++; // увеличиваем размер кучи
    
    // выполняем восстановление свойства кучи (например, с помощью просеивания вверх)
    while (index > 0 && heap[(index - 1) / 2] < heap[index]) {
        std::swap(heap[(index - 1) / 2], heap[index]);
        index = (index - 1) / 2;
    }
    

    }

    template bool Heap::search(T value) { for (int i = 0; i < size; i++) { if (heap[i] == value) { return true; // значение найдено в куче } }

    return false; // значение не найдено
    

    }

    template bool Heap::remove(T value) { for (int i = 0; i < size; i++) { if (heap[i] == value) { // перемещаем последний узел вместо удаляемого heap[i] = heap[size - 1];

            size--; // уменьшаем размер кучи
    
            // выполняем восстановление свойства кучи (например, с помощью просеивания вниз)
            while (true) {
                int left = 2 * i + 1;
                int right = 2 * i + 2;
    
                int largest = i;
    
                if (left < size && heap[left] > heap[largest]) {
                    largest = left;
                }
    
                if (right < size && heap[right] > heap[largest]) {
                    largest = right;
                }
    
                if (largest != i) {
                    std::swap(heap[i], heap[largest]);
                    i = largest;
                }
                else {
                    break;
                }
            }
    
            return true; // узел удален из кучи
        }
    }
    
    return false; // узел не найден
    

    }

    template void Heap::print() { for (int i = 0; i < size; i++) { std::cout << heap[i] << " "; }

    std::cout << std::endl;
    

    }

    int main() { Heapstd::string heap; // изменено на Heapstd::string

    heap.insert("Hello"); // изменено на строки
    heap.insert("World");
    heap.insert("!");
    heap.insert("This");
    heap.insert("is");
    heap.insert("a");
    heap.insert("heap");
    
    heap.print(); // выводит: World is heap Hello This a !
    
    std::cout << heap.search("is") << std::endl; // выводит: 1 (значение найдено)
    std::cout << heap.search("not") << std::endl; // выводит: 0 (значение не найдено)
    
    std::cout << heap.remove("Hello") << std::endl;
    std::cout << heap.remove("not") << std::endl;
    heap.print(); // выводит: World is heap This a !
    
    return 0;
    

    }

  3. User

    добавь функцию сортировки кучи при ввводе входных данных

  4. Assistant

    Для добавления функции сортировки кучи при вводе входных данных, тебе понадобится:

    1. Добавить прототип функции void heapSort(), которая будет выполнять сортировку кучи.
    2. Реализовать эту функцию, с использованием данных структуры кучи.
    3. Вызвать функцию heapSort() после ввода всех элементов в кучу в функции main().

    Вот обновленный код:

    #include <iostream> // для вывода результатов
    #include <algorithm> // для использования std::sort
    
    template<typename T>
    class Heap {
    private:
        T* heap; // массив для хранения узлов кучи
        int size;  // размер кучи
    public:
        Heap(); // конструктор по умолчанию
        ~Heap(); // деструктор
    
        void insert(T value); // добавить узел в кучу
        bool search(T value); // найти узел в куче
        bool remove(T value); // удалить узел из кучи
    
        void print(); // вывод текущего состояния кучи
        
        void heapSort(); // сортировка кучи
    };
    
    template<typename T>
    Heap<T>::Heap() {
        heap = new T[100]; // создаем массив из 100 элементов
        size = 0; // инициализируем размер кучи
    }
    
    template<typename T>
    Heap<T>::~Heap() {
        delete[] heap; // освобождаем память, выделенную для массива
    }
    
    template<typename T>
    void Heap<T>::insert(T value) {
        int index = size; // индекс нового узла равен текущему размеру кучи
        heap[index] = value; // добавляем новый узел в массив
    
        size++; // увеличиваем размер кучи
    
        // выполняем восстановление свойства кучи (например, с помощью просеивания вверх)
        while (index > 0 && heap[(index - 1) / 2] < heap[index]) {
            std::swap(heap[(index - 1) / 2], heap[index]);
            index = (index - 1) / 2;
        }
    }
    
    template<typename T>
    bool Heap<T>::search(T value) {
        for (int i = 0; i < size; i++) {
            if (heap[i] == value) {
                return true; // значение найдено в куче
            }
        }
    
        return false; // значение не найдено
    }
    
    template<typename T>
    bool Heap<T>::remove(T value) {
        for (int i = 0; i < size; i++) {
            if (heap[i] == value) {
                // перемещаем последний узел вместо удаляемого
                heap[i] = heap[size - 1];
    
                size--; // уменьшаем размер кучи
    
                // выполняем восстановление свойства кучи (например, с помощью просеивания вниз)
                while (true) {
                    int left = 2 * i + 1;
                    int right = 2 * i + 2;
    
                    int largest = i;
    
                    if (left < size && heap[left] > heap[largest]) {
                        largest = left;
                    }
    
                    if (right < size && heap[right] > heap[largest]) {
                        largest = right;
                    }
    
                    if (largest != i) {
                        std::swap(heap[i], heap[largest]);
                        i = largest;
                    }
                    else {
                        break;
                    }
                }
    
                return true; // узел удален из кучи
            }
        }
    
        return false; // узел не найден
    }
    
    template<typename T>
    void Heap<T>::print() {
        for (int i = 0; i < size; i++) {
            std::cout << heap[i] << " ";
        }
    
        std::cout << std::endl;
    }
    
    template<typename T>
    void Heap<T>::heapSort() {
        std::sort(heap, heap + size);
    }
    
    int main() {
        Heap<double> heap;
    
        heap.insert(1.23);
        heap.insert(1);
        heap.insert(222);
        heap.insert(0.9992);
    
        heap.heapSort(); // сортировка кучи
    
        heap.print(); // выводит: 0.9992 1 1.23 222
    
        std::cout << heap.search(222) << std::endl; // выводит: 1 (значение найдено)
        std::cout << heap.search(1) << std::endl; // выводит: 0 (значение не найдено)
    
        std::cout << heap.remove(4) << std::endl;
        std::cout << heap.remove(1) << std::endl;
        heap.print(); // выводит: 0.9992 1.23 222
    
        return 0;
    }
    
  5. User

    Перепиши функцию сортировки heapSort с исползованием стандартных циклов и логических конструкций

  6. Assistant

    Без использования стандартной функции std::sort, функцию heapSort можно переписать вручную с использованием циклов и логических конструкций. Вот обновленная реализация:

    template<typename T>
    void Heap<T>::heapSort() {
        // Построение кучи
        for (int i = size / 2 - 1; i >= 0; i--) {
            int parent = i;
            while (true) {
                int leftChild = 2 * parent + 1;
                if (leftChild >= size) {
                    break;
                }
                int maxChild = leftChild;
                if (leftChild + 1 < size && heap[leftChild + 1] > heap[leftChild]) {
                    maxChild = leftChild + 1;
                }
                if (heap[parent] >= heap[maxChild]) {
                    break;
                }
                std::swap(heap[parent], heap[maxChild]);
                parent = maxChild;
            }
        }
    
        // Сортировка кучи по возрастанию
        for (int i = size - 1; i > 0; i--) {
            std::swap(heap[0], heap[i]);
            int parent = 0;
            while (true) {
                int leftChild = 2 * parent + 1;
                if (leftChild >= i) {
                    break;
                }
                int maxChild = leftChild;
                if (leftChild + 1 < i && heap[leftChild + 1] > heap[leftChild]) {
                    maxChild = leftChild + 1;
                }
                if (heap[parent] >= heap[maxChild]) {
                    break;
                }
                std::swap(heap[parent], heap[maxChild]);
                parent = maxChild;
            }
        }
    }
    

    В этой реализации сначала строится куча, затем происходит сортировка путем последовательного извлечения максимального элемента из корня и восстановления свойства кучи. Таким образом, куча будет отсортирована по возрастанию.