Heap

using namespace std;

void heapify(Movie_Vertex * arr, int x, int j);
void createHeap(Movie_Vertex * arr, int x);

int main() {
  vector < Movie_Vertex > ex;
  for (int i = 0; i < 50; i++) {
    string movie = "Movie ";
    Movie_Vertex a(movie.append(to_string(i + 1)), "Horror", 1 + ((double) rand() / RAND_MAX) * 9);
    ex.push_back(a);
  }

  Movie_Vertex * arr[ex.size()];
  for (int i = 0; i < ex.size(); i++) {
    arr[i] = & ex.at(i);
  }

  for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {
    cout << arr[i] -> getTitle() << " ";
  }
  
  createHeap( * arr, 25);
  cout << " HEAP CREATED " << endl;

  for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {
    cout << arr[i] -> getTitle() << " ";
  }

  return 0;
}

void heapify(Movie_Vertex * arr, int x, int j) {
  int max = j;
  int left = 2 * j + 1;
  int right = 2 * j + 2;
  if (arr[left].getRating() > arr[max].getRating() && left < x) {
    max = left;
  }
  if (arr[right].getRating() > arr[max].getRating() && right < x) {
    max = right;
  }
  if (max != j) {
    swap(arr[j], arr[max]);
    heapify(arr, x, max);
  }
}

void createHeap(Movie_Vertex * arr, int x) {
  int firstIndex = (x / 2) - 1;
  for (int j = firstIndex; j >= 0; j--) {
    heapify(arr, x, j);
  }
}