Given a max-heap represented as an array, return the kth largest element without modifying the heap.

  Here are all the header files included to make the compilation successful.
 

    
#include <iostream>
#include <vector>
#include <stack>

#include <math.h>
using namespace std;
 

    
  This is how we heapify the given array of elements.
  

#define SWAP(x,y) \
  x = x ^ y;      \
  y = x ^ y;      \
  x = x ^ y;      \

void siftDown(vector<int> &v, int start, int end)
{
  int root = start;

  while (root*2+1 <= end){
    int child = root*2+1;
    int swap = root;

    if (child <= end && v[swap] < v[child]) {
      swap = child;
    }
    if(child+1 <= end && v[swap] < v[child+1]) {
      swap = child+1;
    }

    if (swap != root) {
      SWAP(v[root], v[swap]);
      root = swap;
    } else {
      return;
    }
  }
}

void heapify(vector<int> &v, int count)
{

  int start = floor((count-2)/2);

  while (start >=0 ) {
    siftDown(v, start, count-1);
    start = start - 1;
  }
}

 

    
  We modify the stack functionality a little to maintain the element order in the stack with the incoming elements.
  

void insertToStack(vector<int> &v, stack<int> &s, int val)
{
  /* Temporary vector to keep the order from the stack */
  vector<int> tmp;

  /* Pop the elements till new value finds its place */
  while(!s.empty() && v[s.top()] > v[val]){
    tmp.insert(tmp.begin(), s.top());
    s.pop();
  }

  /* push the new value into the stack */
  s.push(val);

  /* Push all the elements in the same order 
     which are previously popped out */
  vector<int>::iterator it;
  for (it=tmp.begin(); it<tmp.end(); it++) {
    s.push(*it);
  }
}

 

    
  This function traverses the heap to find the Kth element in log time
  

int find(vector<int> &v, stack<int> &s, int index, int pos, int count)
{
  /* If current element is smaller than the element in the stack,
     update the current element with the top of the stack and 
     push the current element into the stack*/
  if (!s.empty() && v[s.top()] > v[index]) {
    insertToStack(v, s, index);
    index = s.top();
  }

  if (pos == count) {
    /* If the count reaches pos, return the current element */
    return v[index];
  } else {
    int lchild = index*2+1;
    int rchild = lchild+1;

    /* Check if the current element has right child */
    if (rchild > v.size()-1) {
      
      /* Check if the current element has left child */
      if (lchild > v.size()-1) {
        
        /* The current element is the leaf node. Get the top of 
           the stack to proceed further */
        index = s.top();
        s.pop();
      } else {
        
        /* The current element has only left child. */
        if (s.empty() || v[lchild] > v[s.top()]) {
          index = lchild;
        } else {
          index = s.top();
          s.pop();
          insertToStack(v, s, lchild);
        }
      }
    } else {
      
      /* Find the max and min from the child nodes */
      int max = 0;
      int min = 0;
      if (v[lchild] > v[rchild]) {
        max = lchild;
        min = rchild;
      } else {
        min = lchild;
        max = rchild;
      }

      /* Find the highest element among the child nodes & the top
         of the stack, Update the current element with the highest 
         element and push the other two elements into the stack */
      if (s.empty()) {
        insertToStack(v, s, min);
        index = max;
      } else {
        int top = s.top();
        if (v[max] < v[top]) {
          index = top;
          s.pop();
          insertToStack(v, s, min);
          insertToStack(v, s, max);
        } else {
          index = max;
          if (v[min] > v[top]) {
            insertToStack(v, s, min);
          } else {
            s.pop();
            insertToStack(v, s, min);
            insertToStack(v, s, top);
          }
        }
      }
    }
    
    /* Call "find" recursively till "count" reaches "pos" */
    return find(v, s, index, pos, count+1);
  }
}

int findElement(vector<int> &v, int pos)
{
  /* Start with am empty stack */
  stack<int> s;
  return find(v, s, 0, pos, 1);
}
 

  You are NOT A FAN of recursion? Here you go,
 

@@ -1,5 +1,6 @@
 int find(vector<int> &v, stack<int> &s, int index, int pos, int count)
 {
+  while (count <= v.size()) {
   /* If current element is smaller than the element in the stack,
      update the current element with the top of the stack and 
      push the current element into the stack*/
@@ -74,8 +75,7 @@
         }
       }
     }
-    
-    /* Call "find" recursively till "count" reaches "pos" */
-    return find(v, s, index, pos, count+1);
+    }
+    count++:
   }
 }
 

  Here is the main function
    

int main(int argc, char **argv)
{

  /* Store the inputs into a vector */
  vector<int> input;
  int total= stoi(argv[1]);
  for(int c=0; c<total; c++){
    input.insert(input.end(), stoi(argv[c+2]));
  }

  /* Print them */
  vector<int>::iterator it;
  cout << "     my vector contains:";
  for (it=input.begin(); it<input.end(); it++)
    cout << ' ' << *it;
  cout << endl;

  /* Heapify the input vector */ 
  heapify(input, total);
  cout << "my heap vector contains:";
  for (it=input.begin(); it<input.end(); it++)
    cout << ' ' << *it;
  cout << endl << endl;

  for (int count=1; count<=total; count++) {
    int ret = findElement(input, count);
    cout << "(" << count << "):  " << ret << endl;
  }
  return 0;
}

Output:

$ ./kthInHeap 4 10 6 9 1
     my vector contains: 10 6 9 1
my heap vector contains: 10 6 9 1

(1):  10
(2):  9
(3):  6
(4):  1


$ ./kthInHeap 7 5 6 1 3 8 9 2
     my vector contains: 5 6 1 3 8 9 2
my heap vector contains: 9 8 5 3 6 1 2

(1):  9
(2):  8
(3):  6
(4):  5
(5):  3
(6):  2
(7):  1


$ ./kthInHeap 8 6 5 3 1 8 7 2 4
     my vector contains: 6 5 3 1 8 7 2 4
my heap vector contains: 8 6 7 4 5 3 2 1

(1):  8
(2):  7
(3):  6
(4):  5
(5):  4
(6):  3
(7):  2
(8):  1