Demo entry 6645064

Heapsort.cpp

   

Submitted by anonymous on Oct 09, 2017 at 05:28
Language: C++. Code size: 5.4 kB.

#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <string>
using namespace std;

/**************** Heapsort Class *******************/
class Heapsort
{
private:
  /* Private Member Variables */
  int rootIndex;
  int leftChild;
  int rightChild;
  int parentIndex;
  int minChildIndex;
  int arraySize;
  int* heapAry;

public:
  /* Single Arg Constructor */
  Heapsort(int size)
  {
    rootIndex = 1;
    leftChild = 0;
    rightChild = 0;
    parentIndex = 0;
    minChildIndex = 0;
    arraySize = size + 1;
    heapAry = new int[arraySize]();
    heapAry[0] = 0;
  }


  /* Inserts Elements into Heap */
  void buildHeap(ifstream& in, ofstream& out)
  {
    //Reinitializing input file
    in.clear();
    in.seekg(0, in.beg);

    //Resetting while loop, this time making use of data
    int data = 0;
    while (in >> data)
    {
      //Print the newly created heap for debugging
      if (!isHeapFull())
      {
        insertOneDataItem(data);
      }
      printHeap(out);
    }
  }


  /* Deconstructs Heap and Prints Sorted Array */
  void deleteHeap(ofstream& out)
  {
    //oss to concatenate the elements for "pretty print"
    ostringstream oss;
    while (!isHeapEmpty())
    {
      //take value at root, concatenate to oss and print
      int data = getRoot();
      oss << data << " ";
      string s = oss.str();
      out << s << endl;

      //Deletion and bubbling of the new root
      deleteRoot();
      parentIndex = rootIndex;
      bubbleDown(parentIndex);

      //Printing the new array state after bubbling
      printHeap(out);
      out << endl;
    }
    delete[] heapAry;
    heapAry = NULL;
  }


  /* Inserting the element into the right location */
  void insertOneDataItem(int data)
  {
    heapAry[0]++;
    heapAry[heapAry[0]] = data;
    bubbleUp(heapAry[0]);
  }


  /* Returns value at the root node */
  int getRoot(){
    return heapAry[rootIndex];
  }


  /* 0th index keeps track of elements, so decrement
    to keep track, and replace the root with the
    last element in the array which represents the
    bottom right-most node in the tree */
  void deleteRoot()
  {
    heapAry[1] = heapAry[heapAry[0]];
    heapAry[heapAry[0]] = 0;
    heapAry[0]--;
    arraySize--;
  }


  /* To reposition the newly inserted element */
  void bubbleUp(int childIndex)
  {
    //Continue percolating until the new node is the root
    if (isRoot(childIndex)){  return; }
    else
    {
      parentIndex = childIndex / 2;

      //Checking if the new node can be a valid parent
      //and swaps accordingly
      if (heapAry[childIndex] < heapAry[parentIndex])
      {
        int swap = heapAry[childIndex];
        heapAry[childIndex] = heapAry[parentIndex];
        heapAry[parentIndex] = swap;
      }
      bubbleUp(parentIndex);
    }
  }


  /* To reposition the newly created root */
  void bubbleDown(int parent)
  {
    //If the new root's position is at the end, we're done
    if (isLeaf(parent)){ return; }
    else{
      leftChild = parent * 2;
      rightChild = (parent * 2) + 1;

      //Otherwise we check which node is the smallest
      if (leftChild > heapAry[0]){  minChildIndex = rightChild; }
      else if (rightChild > heapAry[0]){  minChildIndex = leftChild;  }
      else{ minChildIndex = findMinChildIndex(leftChild, rightChild); }

      //And swap the new root appropriately (using recursion)
      if (heapAry[minChildIndex] < heapAry[parent])
      {
        int swap = heapAry[minChildIndex];
        heapAry[minChildIndex] = heapAry[parent];
        heapAry[parent] = swap;
        bubbleDown(minChildIndex);
      }
    }
  }


  //Checks if parent is actually a leafNode
  bool isLeaf(int index)
  {
    leftChild = index * 2;
    rightChild = (index * 2) + 1;
    return (leftChild > heapAry[0]) && (rightChild > heapAry[0]);
  }


  /* Test if an node is the root node */
  bool isRoot(int index)
  {
    return index == 1;
  }


  /* Returns the smaller of two children nodes */
  int findMinChildIndex(int left, int right)
  {
    if (heapAry[left] > heapAry[right]){  return right; }
    else{ return left; }
  }


  /* Checks whether there are more elements in the array */
  bool isHeapEmpty()
  {
    return heapAry[0] == 0;
  }


  /* Checks if we can insert more elements */
  bool isHeapFull()
  {
    return heapAry[0] == arraySize;
  }


  /* Prints out our heap in the form of an array */
  void printHeap(ofstream& out)
  {
    for (int i = 0; i < arraySize; i++)
    {
      if (i == 0)
      {
          out << "[" << heapAry[0] << "] -> ";
      }
      else if (!heapAry[i] == 0)
      {
        out << "[" << heapAry[i] << "]";
      }
    }
    out << endl;
  }


  /* Heap Destructor */
  ~Heapsort()
  {
    delete heapAry;
  }
};
/**************** Heapsort Class End *******************/
/*********** Main Driver Class ***********/
int main(int argc, char* argv[])
{
  // Initialize file streams for I/O
  int data = 0;
  ifstream in(argv[1]);
  ofstream out1(argv[2]);
  ofstream out2(argv[3]);

  //Count the number of elements so we can declare a size
  //for our array
  int elementCounter = 0;
  while (in >> data)
  {
    elementCounter++;
  }

  //Initialize, Build, and Delete our Heap
  Heapsort hs(elementCounter);
  hs.buildHeap(in, out1);
  hs.deleteHeap(out2);

  return 0;
}
/*********** Main Driver END ************/

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).