title: C++ heap sort of vector<string,int>
body: <p>I can not figure out where I'm having my problem with my heap sort.<br>
  The program takes a filename from the command line, imports the words into a vector then that vector is turned into a vector pair of <code>vector&lt;string,int&gt;</code> where string is the word and int is the count of how many instances of that word are in the file.</p>
  
  <p>The <code>vector&lt;PAIR&gt;</code> is then sorted by either the string (value or v) or by int (key or k).  My sorting by Key works fine however sort by value is off.  I suspect I'm missing an if statement in max_heapify when sorting by value.  Here's my code:</p>
  
  <h3>main.cpp</h3>
  
  <pre><code>#include &lt;fstream&gt;
  #include &lt;iostream&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;vector&gt;
  #include &lt;string&gt;
  #include &lt;string.h&gt;
  #include &lt;stdio.h&gt;
  #include &lt;map&gt;
  #include &lt;time.h&gt;
  #include "readwords.h"
  
  using namespace std;
  
  readwords wordsinfile;
  vector&lt;string&gt; allwords;
  bool times;
  char *filename;
  timespec timestart,timeend;
  vector&lt; pair&lt;string,int&gt; &gt; allwords_vp;
  
  timespec diffclock(timespec start, timespec end);
  
  int main ( int argc, char *argv[] ) {
  
      filename = argv[1];
  
      //Lets open the file 
      ifstream ourfile2(filename);
  
      //Lets get all the words using our requirements
      allwords = wordsinfile.getwords(ourfile2);
      //Convert all the words from file and count how many times they 
      //appear.  We will store them in a vector&lt;string,int&gt; string 
      //being the word and int being how many time the word appeared
      allwords_vp = wordsinfile.count_vector(allwords);
  
      cout &lt;&lt; "HeapSort by Values" &lt;&lt; endl;
          if (times) {
          clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &amp;timestart);
                  wordsinfile.heapsort(const_cast&lt;char *&gt;("v"));
          clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &amp;timeend);
                  cout &lt;&lt; "HeapSort by Values ran in "
                       &lt;&lt; diffclock(timestart,timeend).tv_nsec &lt;&lt; " nanosecond or "
                       &lt;&lt; diffclock(timestart,timeend).tv_nsec/1000 &lt;&lt; " millisecond"
                       &lt;&lt; endl;
          } else {
                  wordsinfile.heapsort(const_cast&lt;char *&gt;("v"));
          }
  
      cout &lt;&lt; "HeapSort by Keys" &lt;&lt; endl;
          if (times) {
          clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &amp;timestart);
                  wordsinfile.heapsort(const_cast&lt;char *&gt;("k"));
          clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &amp;timeend);
                  cout &lt;&lt; "HeapSort by Keys ran in "
                       &lt;&lt; diffclock(timestart,timeend).tv_nsec &lt;&lt; " nanosecond or "
                       &lt;&lt; diffclock(timestart,timeend).tv_nsec/1000 &lt;&lt; " millisecond"
                       &lt;&lt; endl;
          } else {
                  wordsinfile.heapsort(const_cast&lt;char *&gt;("k"));
          }
  }
  
  timespec diffclock(timespec start, timespec end) {
      timespec temp;
      if ((end.tv_nsec-start.tv_nsec)&lt;0) {
          temp.tv_sec = end.tv_sec-start.tv_sec-1;
          temp.tv_nsec = 1000000000+end.tv_nsec-start.tv_nsec;
      } else {
          temp.tv_sec = end.tv_sec-start.tv_sec;
          temp.tv_nsec = end.tv_nsec-start.tv_nsec;
      }
      return temp;
  }
  </code></pre>
  
  <h3>readwords.h</h3>
  
  <pre><code>#ifndef READWORDS_H
  #define READWORDS_H
  
  #include &lt;vector&gt;
  #include &lt;map&gt;
  #include &lt;utility&gt;
  #include &lt;time.h&gt;
  
  typedef std::pair&lt;std::string, int&gt; PAIR;
  
  bool isasciifile(std::istream&amp; file);
  
  class readwords {
      private:
           std::vector&lt;PAIR&gt; vp;
      public:
           std::vector&lt;std::string&gt; getwords(std::istream&amp; file);
           std::vector&lt;PAIR&gt; count_vector(std::vector&lt;std::string&gt; sv);
           void print_vectorpair(std::vector&lt;PAIR&gt; vp);
           void print_vector(std::vector&lt;std::string&gt; sv);     
           void heapsort(char how[]);
           void buildmaxheap(std::vector&lt;PAIR&gt; &amp;vp, int heapsize, char how[]);
           void max_heapify(std::vector&lt;PAIR&gt; &amp;vp, int i, int heapsize, char how[]);
           void swap_pair(PAIR &amp;p1, PAIR &amp;p2);
  };
  </code></pre>
  
  <h3>readwords.cpp</h3>
  
  <pre><code>#include &lt;fstream&gt;
  #include &lt;iostream&gt;
  #include &lt;map&gt;
  #include "readwords.h"
  #include &lt;vector&gt;
  #include &lt;string&gt;
  #include &lt;utility&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;stdio.h&gt;
  #include &lt;string.h&gt;
  #include &lt;time.h&gt;
  
  //using std::vector;
  using namespace std;
  
  typedef pair&lt;string, int&gt; PAIR;
  
  // Do we have a ASCII file?
  // Lets test the second 10 chars to make sure
  // This method is flawed if the file is less than 10 chars
  bool isasciifile(std::istream&amp; file) {
      int c = 0;
      bool foundbin = false;
      for(c=0; c &lt; 10;c++) {
          if(!isprint(file.get())){
              // Looks like we found a non ASCII file, or its empty.
              foundbin = true;
          }
      }
      return foundbin;
  }
  
  // This is our workhorse as it splits up the words based on our criteria and
  // passes them back as a vector of strings.
  vector&lt;string&gt; readwords::getwords(std::istream&amp; file) {
      char c;
      string aword;
      vector&lt;string&gt; sv;
  
              //Let go through the file till the end  
                          while(file.good()) {
                                  c = file.get();
                                  if (isalnum(c)) {
                      //convert any uppercase to lowercase
                      if(isupper(c)) {
                                                  c = (tolower(c));
                                          }
                      //if its a space lets go onto the next char
                                          if(isspace(c)) { continue; }
                      //everything looks good lets add the char to our word
                                          aword.insert(aword.end(),c);
                                  } else {
                      //its not a alphnum or a space so lets skip it
                      if(!isspace(c)) { continue; }
                      //reset our string and increment
                                          if (aword != "") {sv.push_back(aword);}
                                          aword = "";
                                          continue;
                                  }
                          }
      return sv;
  }
  
  vector&lt;PAIR&gt; readwords::count_vector(vector&lt;string&gt; sv) {
      unsigned int i = 0;
      int j = 0;
      int match = 0;
  
      // cout &lt;&lt; "Working with these string: " &lt;&lt; endl;
      // print_vector(sv);
  
      for (i=0; i &lt; sv.size(); i++) {
          // cout &lt;&lt; "count of i: " &lt;&lt; i &lt;&lt; " word is: " &lt;&lt; sv.at(i) &lt;&lt; endl;
  
          match = 0;
          if(readwords::vp.size() == 0) {
              readwords::vp.push_back(make_pair(sv.at(i),1)); continue;
          }
  
          for (j=readwords::vp.size() - 1; j &gt;= 0; --j) {
              if (sv.at(i) == readwords::vp.at(j).first) {
                  // cout &lt;&lt; "Match found with: " &lt;&lt; sv.at(i) &lt;&lt; endl;;
                  readwords::vp.at(j).second = readwords::vp.at(j).second + 1;
                  match = 1;
              } 
  
              // cout &lt;&lt; "Value of j and match: " &lt;&lt; j &lt;&lt; match &lt;&lt; endl;
              if ( j == 0 &amp;&amp; match == 0) {
                  // cout &lt;&lt; "Match found at end with: " &lt;&lt; sv.at(i) &lt;&lt; endl;;
                  readwords::vp.push_back(make_pair(sv.at(i),1));
              }
          }
      }
  
      //Prob need to sort by first data type then second here, prior to sort functions.
      //Might not be the best place as the sort functions would alter it, if not here
      //then each sort requires to do secondary search
  
      return readwords::vp;
  }
  
  void readwords::print_vectorpair(vector&lt;PAIR&gt; vp) {
      unsigned int i = 0;
  
      for (i=0; i &lt; vp.size(); ++i) {
          cout &lt;&lt; vp.at(i).first &lt;&lt; " " &lt;&lt; vp.at(i).second &lt;&lt; endl;
      }
  }
  
  void readwords::print_vector(vector&lt;string&gt; sv) {
      unsigned int i = 0;
  
      for (i=0; i &lt; sv.size(); ++i) {
          cout &lt;&lt; sv.at(i) &lt;&lt; endl;
      }
  }
  
  void readwords::heapsort(char how[]) {
      int heapsize = (readwords::vp.size() - 1);
  
      buildmaxheap(readwords::vp, heapsize, how);
  
      for(int i=(readwords::vp.size() - 1); i &gt;= 0; i--) {
          swap(readwords::vp[0],readwords::vp[i]);
          heapsize--;
          max_heapify(readwords::vp, 0, heapsize, how);
      }
  
      print_vectorpair(readwords::vp);
  }
  
  void readwords::buildmaxheap(vector&lt;PAIR&gt; &amp;vp, int heapsize, char how[]) {
  
      for(int i=(heapsize/2); i &gt;= 0 ; i--) {
          max_heapify(vp, i, heapsize, how);
      }
  }
  
  void readwords::max_heapify(vector&lt;PAIR&gt; &amp;vp, int i, int heapsize, char how[]) {
      int left = ( 2 * i ) + 1;
      int right = left + 1;
      int largest;
  
      if(!strcmp(how,"v")) {  
          if(left &lt;= heapsize &amp;&amp; vp.at(left).second &gt;= vp.at(i).second ) {
              if( vp.at(left).first &gt;= vp.at(i).first ) {
                  largest = left;
              } else {
                  largest = i;
              }
          } else {
              largest = i;
          }
  
          if(right &lt;= heapsize &amp;&amp; vp.at(right).second &gt;= vp.at(largest).second) {
              if( vp.at(right).first &gt;= vp.at(largest).first) {
                  largest = right;
              }
          }   
      }
  
      if(!strcmp(how,"k")) {  
          if(left &lt;= heapsize &amp;&amp; vp.at(left).first &gt; vp.at(i).first) {
              largest = left;
          } else {
              largest = i;
          }
  
          if(right &lt;= heapsize &amp;&amp; vp.at(right).first &gt; vp.at(largest).first) {
              largest = right;
          }   
      }
  
      if(largest != i) {
          swap(vp[i], vp[largest]);
          max_heapify(vp, largest, heapsize, how);
      }
  }
  </code></pre>