Heapsort simply skips over sorting step with large arrays

[Steve the Pocket]

I'm writing a heapsort program. It asks for a value for "max" and creates an array of "max" # random numbers from 1-100, and then enqueues them all into a Priority Queue. Then it asks if you want to print the resulting list, and if you say yes, it dequeues them each into the cout one by one. (I initially made it so it automatically dequeues into another array, and then if you say yes it prints all elements of that array, but I kept getting seg. faults on that.) The problem is, for some bizarre reason, it literally does not sort the elements if the array is big enough. Here's my code:

#include<iostream>
#include<string>
#include<cstdlib>
using namespace std;
 
void Swap(short& item1, short& item2);
 
template<class ItemType>
class PQType
{
public:
  PQType(long maxItems);
  ~PQType();
  void MakeEmpty();
  bool IsEmpty() const;
  void Enqueue(ItemType newItem);
  short Dequeue();
private:
  long length;
  short* items;
  void ReheapDown(short root, short bottom);
  void ReheapUp(short root, short bottom);
};
 
template<class ItemType>
PQType<ItemType>::PQType(long maxItems)
{
  items = new short[maxItems];
  length = 0;
}
 
template<class ItemType>
void PQType<ItemType>::MakeEmpty()
{
  length = 0;
}
 
template<class ItemType>
PQType<ItemType>::~PQType()
{
  delete [] items;
}
 
template<class ItemType>
void PQType<ItemType>::ReheapDown(short root, short bottom)
{
  short maxChild;
  short rightChild;
  short leftChild;
 
  leftChild = root*2+1;
  rightChild = root*2+2;
  if (leftChild <= bottom)
  {
    if (leftChild == bottom)
      maxChild = leftChild;
    else
    {
      if (items[leftChild] <= items[rightChild])
        maxChild = rightChild;
      else
        maxChild = leftChild;
    }
    if (items[root] < items[maxChild])
    {
      Swap(items[root], items[maxChild]);
      ReheapDown(maxChild, bottom);
    }
  }
}
 
template<class ItemType>
void PQType<ItemType>::ReheapUp(short root, short bottom)
{
  short parent;
 
  if (bottom > root)
  {
    parent = (bottom-1) / 2;
    if (items[parent] < items[bottom])
    {
      Swap(items[parent], items[bottom]);
      ReheapUp(root, parent);
    }
  }
}
 
template<class ItemType>
void PQType<ItemType>::Enqueue(ItemType newItem)
{
  length++;
  items[length-1] = newItem;
  ReheapUp(0, length-1);
}
 
template<class ItemType>
short PQType<ItemType>::Dequeue()
{
  short item = items[0];
  items[0] = items[length-1];
  length--;
  ReheapDown(0, length-1);
  return item;
}
 
template<class ItemType>
bool PQType<ItemType>::IsEmpty() const
{
  return length == 0;
}
 
void Swap(short& item1,short& item2)
{
  short tempnum = item1;
  item1 = item2;
  item2 = tempnum;
}
 
int main()
{
  long max, bin;
  char cr, listYN;
  string nullstring;
  cout << "\nHeapsort Program\n\n";
  cout << "Enter # of elements to generate: ";
  cin >> max;
  short* unsortedList = new short[max];
  short* sortedList = new short[max];
 
  cout << "Generating list of integers...";
  for (long x=0; x<max; x++)
  {
    unsortedList[x] = (rand()%100)+1;
  }
  cout << " done. Press Enter to continue.\n";
  cin.ignore();
  cin.get(cr);
  cout << "Initializing sort...";
  PQType<short> Heap(max);
  for (long y=0; y<max; y++)
  {
    Heap.Enqueue(unsortedList[y]);
  }
  cout << " done. Display list (y/n)? ";
  cin >> listYN;
  if (listYN == 'y' || listYN == 'Y')
  {
    for (long z=0; z<max; z++)
    {
      cout << Heap.Dequeue() << "  ";
    }
  }
}
 

To give a simple example, it will show them in their proper order when the list is a million elements or less (though it segfaults after the first, like, 200), but it shows them in random order when it's 50 million long (and also segfaults after maybe a couple thousand).

Incidentally it also waits until after it has performed an action (generating original array, sorting into heap) to tell you it's starting it, and I have no idea why.

This is using G++ in Ubuntu, by the way.

[Banfa]

template<class ItemType>
void PQType<ItemType>::ReheapUp(short root, short bottom)
{
  short parent;
 
  if (bottom > root)
  {
    parent = (bottom-1) / 2;
    if (items[parent] < items[bottom])
    {
      Swap(items[parent], items[bottom]);
      ReheapUp(root, parent);
    }
  }
}
 

You have made you class use recursive function calls. When you are talking about using millions of entries you are very likely to run out of stack space at some point.

Also you logic for this particular (and possibly other) function is wrong. the parameter root is never used, but parent is meant to be a binary chop between root and bottom. The Swap does the wrong thing, when items[parent] < items[bottom] what also holds true is that items[parent] < items[parent+1] and items[parent] < items[bottom-1] (assuming more than 2 entries in the list).

By swapping items[parent] and items[bottom] items[parent] ends up in the wrong place.

[Steve the Pocket]

Well, it seems both of the above conclusions were wrong. In searching through the code looking for some way to resolve the use of recursion, we discovered a fatal flaw: I was using shorts to hold most of the values that would be equal to or approaching my max length (a side effect from when I converted all my ints to shorts to keep the array small... I was trying to just make the items themselves shorts but inadvertently replaced all my ints). I changed them all back to ints and I seem to be good for it.

Thanks anyway. :)