

今回の問題は配列ヒープがテストと異なった結果を返してしまうことです。うまくいくと、main.cppのテストと結果が一致するようになります。しかし、今の自分のプログラムは結果が一致しません。addItemメソッドは問題なさそうなのですが、おそらくgetItemメソッドに問題があると思われます。以下のプログラムを実行すると一回しか取り出されるはずの内60が3回も表示されてしまいます。教えていただきたいことはなぜ60が3回も表示されてしまうのかとどのようにコードを書けばテストと同じ結果が返ってくるのかが知りたいです。プログラムは以下の通りです。

**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;
        //track the index of parent
        int parentIndex = 1;
    
        int done = false;
    
        //decrement counter
        counter--;
    
        //get the first index of the deepest level
        int height = getHeight(counter);
        int 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[parentIndex] == 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-09T07:17:33.540
83512
2021-11-09T13:42:16.043
45177
question
c++
配列ヒープが期待（テスト）と異なった結果をかえす。


**Heap.cpp**
のgetItem()内のarray[parentIndex]がarray[childIndex+1]になっていないといけませんでした。

[code]

    if(array[childIndex] >= array[parentIndex])
            {
                done = true;
            }
    
[/code]

そしてさらに、`array[1] = lastAdded;`の下付近に`array[counter] = EMPTY`を入れれば解決しました。


CC BY-SA 4.0
2021-11-09T11:01:48.770
83518
2021-11-09T11:01:48.770
45177
83512
answer


`Heap::getItem()`のwhileループで

[code]

    int childIndex = parentIndex * 2;
    
[/code]

と`childIndex`を算出していますが、`childIndex`が`counter`(要素数)を超えるケースがあり、  
データ構造を破壊しているように見受けます。そのため、「60」が3回出力されていると思います。

`childIndex`が`counter`を超える場合、ループを打ち切ってはどうでしょうか。  
具体的には、上記処理に続けてif文で判定する感じです。

[code]

    int childIndex = parentIndex * 2;
    if (childIndex > counter) {
        break;
    }
    
[/code]

* * *

なお、最後の1要素の状態で`getItem()`を呼び出した場合、`getHeight()`を引数「0」で  
呼び出すことになり、`getHeight()`内で呼び出している`log2()`がエラーになるので、  
`counter`が「1」の場合は、`getHeight()`を呼び出す前に最初の要素を返すようにすべきと思います。

### 追記

コメントに回答します。

  1. `counter`が1のときの対応ですが、コメント記載の内容でよいと思います。

コメント抜粋:

[code]

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

  2. 

> 確かに、最後の75以降を表示するのに時間がかかってしまいます。これはそれが問題なのでしょうか

断定はできませんが、その可能性は高いと思います。  
(`getLeafLast()`では`height`分ループしているので、意図しない大きな値になっている場合、時間がかかる)


CC BY-SA 4.0
2021-11-09T11:05:04.883
83519
2021-11-09T13:42:16.043
2021-11-09T13:42:16.043
20098
20098
83512
answer