Может ли кто-нибудь помочь мне выяснить ошибку в куче min-max с помощью C++?

Меня просят создать кучу min-max с использованием C++ в моем назначении класса. Я пытался построить его, но он не складывается. Я проверял код много раз, он тоже не показывает никаких ошибок, но вывод пустой. Я предполагаю, что это ошибка сегментации, но я не могу понять свою ошибку. Может ли кто-нибудь помочь мне понять, что я делаю не так? Я реализовал это из черновика, доступного в Интернете.

         #include <iostream>
    using namespace std;


    #define left(i) (2*i)
    #define right(i) ((2*i) + 1)
    #define parent(i)  ((i)/2)


    void TrickleDown(int list[], int n);
    void TrickleDownMin(int list[], int n, int i);
    void TrickleDownMax(int list[], int n, int i);
    bool isMinLevel(int i, int n);
    void swap(int x, int y);
    void printHeap(int list[], int n);

   

    void TrickleDown(int list[],int n)
    {
        int i;
        for (i = n/2; i>0;i--)
        {
            if (isMinLevel(i,n) == true)
                TrickleDownMin(list, n, i);
            else
                TrickleDownMax(list, n,i);
        }
    }

    bool isMinLevel(int i, int n)
    {
        int height  = 2;
        if (i == 1)
            return true;
        while (true)
        {
            if (i >= pow(2, height) && i <= pow(2, (height + 1)) - 1)
                return true;
            else if (i > n || i < pow(2, height))
                return false;
            height += 2;
        }
    }

    void TrickleDownMin(int list[], int n, int i)
    {
        int leftChild = left(i);
        int rightChild = right(i);
        int m;
        int leftChildLeft = left(leftChild);
        int rightChildLeft = right(leftChild);
        int leftChildRight = left(rightChild); 
        int rightChildRight = right(rightChild);
        if (leftChild > n)
            return;
        else
        {
            //finding the index of smallest of children and grandchildren
            if (list[leftChild] > list[rightChild])
                m = rightChild;
            if (list[leftChild] < list[rightChild])
                m = leftChild;
            if (list[m] > list[leftChildLeft])
                m = leftChildLeft;
            if (list[m] > list[rightChildLeft])
                m = rightChildLeft;
            if (list[m] > list[leftChildRight])
                m = leftChildRight;
            if (list[m] > list[rightChildRight])
                m = rightChildRight;

            //if m is a grandchildren of i
            if (m == leftChildLeft || m == rightChildLeft || m == leftChildRight || m == rightChildRight)
            {
                if (list[m] < list[i])
                {
                    swap(list[i], list[m]);
                    if (list[m] > list[parent(m)])
                        swap(list[m], list[parent(m)]);
                }
                        TrickleDownMin(list, n,i);
            
            }
                else // m is a children of i
                {
                    if (list[m] < list[i])
                        swap(i, m);
                }
        }
    }

    void TrickleDownMax(int list[], int n, int i)
    {
        int leftChild = left(i);
        int rightChild = right(i);
        int m;
        //int mParent = parent(m);
        int leftChildLeft = left(leftChild);
        int rightChildLeft = right(leftChild);
        int leftChildRight = left(rightChild);
        int rightChildRight = right(rightChild);
        if (leftChild > n)
            return;
        else
        {
            //finding the index of largest of children and grandchildren
            if (list[leftChild] < list[rightChild])
                m = rightChild;
            if (list[leftChild] > list[rightChild])
                m = leftChild;
            if (list[m] < list[leftChildLeft])
                m = leftChildLeft;
            if (list[m] < list[rightChildLeft])
                m = rightChildLeft;
            if (list[m] < list[leftChildRight])
                m = leftChildRight;
            if (list[m] < list[rightChildRight])
                m = rightChildRight;

            //if m is a grandchildren of i
            if (m == leftChildLeft || m == rightChildLeft || m == leftChildRight || m == rightChildRight)
            {
                if (list[m] > list[i])
                {
                    swap(list[i], list[m]);
                    if (list[m] < list[parent(m)])
                        swap(list[m], list[parent(m)]);
                }
                    TrickleDownMin(list, n,m);
            }
            else // m is a children of i
            {
                if (list[m] > list[i])
                    swap(i, m);
            }
        }
    }

    void swap(int x, int y)
    {
        int temp;
        temp=x;
        x = y;
        y =temp;
    }

    void printHeap(int list[], int n)
    {
        cout << "Array representation of the min-max heap is: " << endl;
        for (int i = 0;i < n;i++)
        {
            cout << list[i] << " ";
        }
        cout << endl;
    }


    int main()
    {
        int numbers[] = { 25,65,80,8,15,37,5,57 };
        int size = sizeof(numbers) / sizeof(numbers[0]);
    
        TrickleDown(numbers, size);
        printHeap(numbers, size);

        return 0;
    }

0 ответов

Другие вопросы по тегам