配列ヒープのプログラムを作りました。実際にテストしてみると期待どうりに動くのですが、なぜか最後の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);
};
Actual order:
の表示が遅れるという意味なのでしたら、stdout
への出力がバッファリングされているためで、cout << " Actual order: ";
の直後にstd::flush(std::cout);
が必要です。