Question

I need step by step instructions of inserting these into a heap. this, is, the, house, that, jack, built. They should be inserted in this sequence. THen swap the first and last variables and do it again. I know the answer is suppose to be but not sure how I'm suppose to get that answer.   

2nd iteration would be.   built, is, the house, that jack, this.

I know the ansers in array format would be just keep getting it wrong on my own:

1. built | is | house | this | that | the | jack
2. built | house | jack | is | that | the | this

Answer 1

#include <bits/stdc++.h>
using namespace std;
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(string arr[], int n, int i)
{
        int largest = i; // Initialize largest as root
        int l = 2 * i + 1; // left = 2*i + 1
        int r = 2 * i + 2; // right = 2*i + 2

        // If left child is larger than root
        if (l < n && arr[l] > arr[largest])
                largest = l;

        // If right child is larger than largest so far
        if (r < n && arr[r] > arr[largest])
                largest = r;

        // If largest is not root
        if (largest != i)
        {
                swap(arr[i], arr[largest]);

                // Recursively heapify the affected sub-tree
                heapify(arr, n, largest);
        }
}

// main function to do heap sort
/* A utility function to print array of size n */
void printArray(string arr[], int n)
{
        for (int i = 0; i < n; ++i)
                cout << arr[i] << " ";
        cout << "\n";
}
void heapSort(string arr[], int n)
{
        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
                heapify(arr, n, i);

        // One by one extract an element from heap
        for (int i = n - 1; i > 0; i--)
        {
                printArray(arr, n);

                // Move current root to end
                swap(arr[0], arr[i]);

                // call max heapify on the reduced heap
                heapify(arr, i, 0);
        }
}


// Driver program
int main()
{
        string arr[] = { "this", "is", "the", "house", "that", "jack", "built"};
        int n = sizeof(arr) / sizeof(arr[0]);

        heapSort(arr, n);

        printArray(arr, n);
}

OUTPUT: