lab10.tar

solution.cpp0000600006513700162730000000603614337332223013212 0ustar  lsmit248lsmit248// Lab 10: kth smallest numbers
// Name: Laura Smith 

//Hi Blake hope ya doing good buddy and have a good break with lots of sleep :)

// Brief description: This makes a heap which is a tree that
// has each child greater than it's parent. It then takes in a 
// value and finds the kth smallest number in the heap.

// This code reads in a number of ints...

#include <iostream>
#include <vector>
#include <cstdio>
#include <iostream>

using namespace std;

void Percolate_Down(int index, vector <int> &values){
    /*This function takes in the tree as a vector and 
    compares the children to the parents in order to 
    make sure the tree is ordered correctly*/
   
    int length = values.size();

    int leftChild = index * 2 + 1;  //place of left child based on where the parent(index) is
    int rightChild = index * 2 + 2; // same but for right child
    
    int minIndex = index; //start the min as the parent

    //check if index is a leaf
    if (leftChild >= length)  
      return;

    //if the index/parent is greater than the left child the child is the new min
    if (values[index] > values[leftChild])  
      minIndex = leftChild;

    //check if there is a right child, and if it's less than the parent
    if ((rightChild < length) && (values[minIndex] > values[rightChild]))
      minIndex = rightChild;

    //if the min index has changed, we need to swap some values
    if (minIndex != index){
      int temp = values[index];
      values[index] = values[minIndex];
      values[minIndex] = temp;
      Percolate_Down(minIndex, values);
    }
}

void Build(vector <int> &values){
  //runs percolate for the whold length of the vector

  int length = values.size();

  for (int i = length - 1; i >=0; --i){
    Percolate_Down(i, values);
  }
}

int Pop(vector <int> &values, int k){
  //pops values off until the kth smallest number is reached
  //it then returns the value

  for (int i = 0; i < k-1; i++){
    values[0] = values[values.size() - 1];
    values.pop_back();

    Percolate_Down(0, values);
  }

  return (values[0]);

}

bool maxHeapCheck(vector <int> &values){
  //checks if it's max heap

  int length = values.size();

  //goes the whole length checking if it's max heap for left and right child
  for (int i = 0; i < length; i++ ){
        if ((2 * i + 1 < length) && (values[i] < values[i * 2 + 1])) {
            return false;
        }    
        if ((2 * i + 2 < length) && (values[i] < values[i * 2 + 2])) {
            return false;
        }
  }

    return true;
}

int main(int argc, char *argv[]) {
    
  int n = 0;
  int k = 0;
  int val = 0;

  while (cin >> n){
    cin >> k;
    vector <int> values(n);

    //creates the vector of values
    for (int i = 0; i < n; i++){
      cin >> val;
      values[i] = val;
    }

    //checks if max heap Y if it is N if not
    if (maxHeapCheck(values) == false)
      cout << "N  ";
    else if (maxHeapCheck(values) == true)
      cout << "Y  ";

    //builds the heap
    Build(values);

    //prints out the kth smallest value
    cout << Pop(values, k) << endl;
  }
    
    return 0;

}