

配列ヒープのプログラムを作りました。実際にテストしてみると期待どうりに動くのですが、なぜか最後の75だけ表示されるのに時間がかかります。何が原因かわかりますでしょうか。

**main.cpp**

[code]

    #include <iostream>
    #include "Heap.h"
    
    using namespace std;
    
    
    
    int main() {
    
        const int NUM_VALUES = 15;
    
        int heapVals[NUM_VALUES] = {10, 5, 30, 15, 20, 40, 60, 25, 50, 35, 45, 65, 70, 75, 55};
    
        cout << "Creating heap of default size (10)" << endl;
        Heap pile;
    
        // load the heap with values
        cout << "Now filling it with 15 values, should cause doubling of size" << endl << endl;
        for(int i = 0; i < NUM_VALUES; i++)
            pile.addItem(heapVals[i]);
    
        // remove values, should be in ascending order
        cout << "Now removing values to see if properly ordered" << endl;
        cout << " In order s/b: 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75" << endl;
        cout << " Actual order: ";
        for(int i = 0; i < NUM_VALUES; i++)
            cout << pile.getItem() << " " ;
        cout << endl << endl;
    }
    
    
[/code]

**Heap.cpp**

[code]

    #include "Heap.h"
    
    #include <iostream>
    
    //default constructor
    Heap::Heap()
    {
        //the array size is STANDARD + 1
        arraySize = STANDARD + 1;
        //create an array it starts from 0 and ends at N(size+1)
        array = new int [arraySize];
        for(int i = 1; i < arraySize; i++)
        {
            array[i] = EMPTY;
        }
    }
    
    //overloaded constructor
    Heap::Heap(int size)
    {
        //the array size is size + 1
        arraySize = size + 1;
        //create an array it starts from 0 and ends at N(size+1)
        array = new int[arraySize];
        for(int i = 1; i < arraySize; i++)
        {
            array[i] = EMPTY;
        }
    }
    
    void Heap::addItem(int value)
    {
        bool done = false;
        int parentIndex;
        int childIndex;
    
        //preincrement
        counter++;
    
        //if the array will be full by adding new value, double the array size
        if(counter >= arraySize)
        {
            arraySize *= 2;
            resize(arraySize);
        }
    
        //save the first index
        childIndex = counter;
    
        //add value at the next available index (counter)
        array[counter] = value;
    
        //if it's the first added value, do nothing
        if(counter == 1)
        {
            return;
        }
    
        //if there're more than one value, place it correct position
        while(!done)
        {
            //get an index of parent
            parentIndex = childIndex / 2;
    
            //if child value >= parent value, finish the loop
            if(array[childIndex] >= array[parentIndex])
            {
                done = true;
            }
    
                //otherwise(child value < parent value)
            else
            {
                //save the parent value
                int temp = array[parentIndex];
                //store child value to parent
                array[parentIndex] = array[childIndex];
                //now, child shold have the saved parent value
                array[childIndex] = temp;
    
                //store parentIndex to childIndex for the next loop
                childIndex = parentIndex;
    
                //if the value became the root, stop the loop
                if(childIndex == 1)
                {
                    done = true;
                }
            }
    
        }
    }
    
    void Heap::resize(int size)
    {
        //resize the array to the new size that is passed in
    
        //create new array to store previous values in it
        int *newArray = new int[size];
    
        for(int i = 1; i < arraySize; i++)
        {
            newArray[i] = EMPTY;
        }
    
        //move the previous values to new array
        for(int i = 1; i <= counter-1; i++)
        {
            newArray[i] = array[i];
        }
    
        //we don't need the old array anymore
        delete[] array;
    
        //array points to newArray so that the array gets new spaces
        array = newArray;
    }
    
    int Heap::getItem()
    {
        //if array is empty
        if(counter == 0)
        {
            return -1;
        }
    
        //save the smallest value in the array
        int smallest = array[1];
    
        //get the last added value
        int lastAdded = array[counter];
        //lastValue will be the root temporarily
        array[1] = lastAdded;
        array[counter] = EMPTY;
        //track the index of parent
        int parentIndex = 1;
    
        int done = false;
    
        //decrement counter
        counter--;
    
        //get the first index of the deepest level
        int height;
        int firstLeaf;
        if(counter == 1)
        {
            height = 1;
            firstLeaf = 1;
        }
        else
        {
            height = getHeight(counter);
            firstLeaf  = getLeafFirst(height);
        }
    
    
        //loop while done is true
        while(!done)
        {
            //get child index
            int childIndex = parentIndex * 2;
    
            //if both sides are empty, finish the loop
            if(array[childIndex] == EMPTY && array[childIndex+1] == EMPTY)
            {
                done = true;
            }
            else
            {
                //if both sides have value, compare, and get an index whose value is smaller
                if(array[childIndex+1] != EMPTY )
                {
                    //get an index that has smaller value
                    if(array[childIndex] >= array[childIndex+1])
                    {
                        childIndex = childIndex + 1;
                    }
                }
    
                //compare lastAdded and the value in the index
                //if the value in childIndex >= lastAdded, finish the loop
                if(array[childIndex] >= lastAdded)
                {
                    done = true;
                }
                    //otherwise(value < lastValue), swap the value
                else
                {
                    //save the value
                    int temp = array[childIndex];
                    //array[childIndex] = lastAdded
                    array[childIndex] = lastAdded;
                    //array[parentIndex] =  the saved value
                    array[parentIndex] = temp;
                    //parentIndex should be childIndex for the next loop
                    parentIndex = childIndex;
                    //if parent reaches leaf, finish the loop
                    if(parentIndex >= firstLeaf )
                    {
                        done = true;
                    }
    
                }
            }
        }
        //std::cout << std::endl << listElements() << " height and first: " << height << " " << firstLeaf << std::endl;
        //return the saved smallest value
        return smallest;
    }
    
    int Heap::getHeight(int value)
    {
        int height = log2(value) + 1;
        return height;
    }
    
    int Heap::getLeafLast(int height)
    {
        int num = 1;
        for(int i = 0; i < height-1; i++)
        {
            num = num * 2 + 1;
        }
        return num;
    }
    int Heap::getLeafFirst(int height)
    {
        int num = getLeafLast(height-1) + 1;
        return num;
    }
    
    
[/code]

**Heap.h**

[code]

    #include <iostream>
    
    const int STANDARD = 10;
    const int EMPTY = -1;
    
    class Heap {
    private:
        int arraySize;
        int counter = 0;
        int *array;
    public:
        Heap();
        Heap(int size);
        void addItem(int value);
        void resize(int value);
        int getItem();
        int getHeight(int value);
        int getLeafLast(int value);
        int getLeafFirst(int value);
    };
    
[/code]


CC BY-SA 4.0
2021-11-09T13:34:07.560
83523
2021-11-10T06:43:36.183
45177
question
c++
やりたいことはできているが、なぜかコンパイルに時間がかかる。


Heap::getItem()でcounterが0になった場合に遅くなっていたみたいだったので以下の二つの変更を行ったところうまくいきました。if(counter
!= 0)をheightとfirstLeafを求めるところに追加。while(!done)をwhile(!done && counter !=
0)に変更し、0の時にこのループに入らないようにした。(※`while(!done && counter !=
0)`)は変更しなくても問題ないとおもいます。)

[code]

    if(counter != 0)
        {
            if(counter == 1)
            {
                height = 1;
                firstLeaf = 1;
            }
            else
            {
                height = getHeight(counter);
                firstLeaf  = getLeafFirst(height);
            }
        }
    
[/code]


CC BY-SA 4.0
2021-11-10T06:43:36.183
83539
2021-11-10T06:43:36.183
45177
83523
answer