0

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

main.cpp

#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;
}

Heap.cpp

#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;
}

Heap.h

#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);
};
6
  • 1
    配列ヒープが期待(テスト)と異なった結果をかえす。のコメントの内容と同じ質問でしょうか?
    – user20098
    Commented 2021年11月9日 13:46
  • 最後の75だけ表示されるのに時間がかかるのではなく、Actual order: の表示が遅れるという意味なのでしたら、stdout への出力がバッファリングされているためで、cout << " Actual order: "; の直後に std::flush(std::cout); が必要です。
    – metropolis
    Commented 2021年11月9日 15:48
  • 3
    「コンパイルに時間がかかる」と「実行に時間がかかる」では意味合いが違ってきます。
    – cubick
    Commented 2021年11月9日 16:55
  • 同じ質問でしたが、質問が変わってしまっていると判断してこちらに載せさせていただきました。 Commented 2021年11月10日 5:01
  • Creating heap of default size (10) Now filling it with 15 values, should cause doubling of size Now removing values to see if properly ordered In order s/b: 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 Actual order: 5 10 15 20 25 30 35 40 45 50 55 60 65 70                 のように75だけ、時間がたった後に表示されるのですが、これはcout << " Actual order: "; の直後に std::flush(std::cout);を置くことによって解決されるということなのでしょうか。 Commented 2021年11月10日 5:02

1 件の回答 1

0

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

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

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。