Question

Steps and formula (if applied) are mandatory for all the questions.

1.   a) Sort the keys 66, 99, 23, 12, 98, 09, 45, 29, 31, 20 in ascending order using the Heap sort. Also write the algorithm.                                                  

                                                

                                                      

b) Sort the keys 20, 31, 29, 45, 09, 98, 12, 23, 99, 66 in descending order using the Heap sort. Also write the algorithm.

2.   Construct a Huffman coding tree using the given Letters and frequencies below. Also write the algorithm.

F: 5, E: 9, C: 12, B:13, D:16, A:45, G:35

Answer 1

If You have Any Query Regarding this please ask in comment section I will be there to solve all your query in comment section immediately hope you will like it

1.

A.)

Heap Sort Program

// Heap Sort in C++
  
  #include <iostream>
  using namespace std;
  
  void heapify(int arr[], int n, int i) {
    // Find largest among root, left child and right child
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
  
    if (left < n && arr[left] > arr[largest])
      largest = left;
  
    if (right < n && arr[right] > arr[largest])
      largest = right;
  
    // Swap and continue heapifying if root is not largest
    if (largest != i) {
      swap(arr[i], arr[largest]);
      heapify(arr, n, largest);
    }
  }
  
  // main function to do heap sort
  void heapSort(int arr[], int n) {
    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arr, n, i);
  
    // Heap sort
    for (int i = n - 1; i >= 0; i--) {
      swap(arr[0], arr[i]);
  
      // Heapify root element to get highest element at root again
      heapify(arr, i, 0);
    }
  }
  
  // Print an array
  void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
      cout << arr[i] << " ";
    cout << "\n";
  }
  
  // Driver code
  int main() {
    int arr[] = {66, 99, 23, 12, 98, 09, 45, 29, 31, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, n);
  
    cout << "Sorted array is \n";
    printArray(arr, n);
  }

B).

// C++ program for implementation of Heap Sort 
#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(int arr[], int n, int i) 
{ 

    int smallest = i; // Initialize smalles as root 

    int l = 2 * i + 1; // left = 2*i + 1 

    int r = 2 * i + 2; // right = 2*i + 2 

  

    // If left child is smaller than root 

    if (l < n && arr[l] < arr[smallest]) 

        smallest = l; 

  

    // If right child is smaller than smallest so far 

    if (r < n && arr[r] < arr[smallest]) 

        smallest = r; 

  

    // If smallest is not root 

    if (smallest != i) { 

        swap(arr[i], arr[smallest]); 

  

        // Recursively heapify the affected sub-tree 

        heapify(arr, n, smallest); 

    } 
} 

  
// main function to do heap sort 

void heapSort(int 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--) { 

        // Move current root to end 

        swap(arr[0], arr[i]); 

  

        // call max heapify on the reduced heap 

        heapify(arr, i, 0); 

    } 
} 

  
/* A utility function to print array of size n */

void printArray(int arr[], int n) 
{ 

    for (int i = 0; i < n; ++i) 

        cout << arr[i] << " "; 

    cout << "\n"; 
} 

  
// Driver program 

int main() 
{ 

    int arr[] = { 20, 31, 29, 45, 09, 98, 12, 23, 99, 66 }; 

    int n = sizeof(arr) / sizeof(arr[0]); 

  

    heapSort(arr, n); 

  

    cout << "Sorted array is \n"; 

    printArray(arr, n); 
}

2.)

// C++ program for Huffman Coding 
#include <bits/stdc++.h> 

using namespace std; 

  
// A Huffman tree node 

struct MinHeapNode { 

  

    // One of the input characters 

    char data; 

  

    // Frequency of the character 

    unsigned freq; 

  

    // Left and right child 

    MinHeapNode *left, *right; 

  

    MinHeapNode(char data, unsigned freq) 

  

    { 

  

        left = right = NULL; 

        this->data = data; 

        this->freq = freq; 

    } 
}; 

  
// For comparison of 
// two heap nodes (needed in min heap) 

struct compare { 

  

    bool operator()(MinHeapNode* l, MinHeapNode* r) 

  

    { 

        return (l->freq > r->freq); 

    } 
}; 

  
// Prints huffman codes from 
// the root of Huffman Tree. 

void printCodes(struct MinHeapNode* root, string str) 
{ 

  

    if (!root) 

        return; 

  

    if (root->data != '$') 

        cout << root->data << ": " << str << "\n"; 

  

    printCodes(root->left, str + "0"); 

    printCodes(root->right, str + "1"); 
} 

  
// The main function that builds a Huffman Tree and 
// print codes by traversing the built Huffman Tree 

void HuffmanCodes(char data[], int freq[], int size) 
{ 

    struct MinHeapNode *left, *right, *top; 

  

    // Create a min heap & inserts all characters of data[] 

    priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap; 

  

    for (int i = 0; i < size; ++i) 

        minHeap.push(new MinHeapNode(data[i], freq[i])); 

  

    // Iterate while size of heap doesn't become 1 

    while (minHeap.size() != 1) { 

  

        // Extract the two minimum 

        // freq items from min heap 

        left = minHeap.top(); 

        minHeap.pop(); 

  

        right = minHeap.top(); 

        minHeap.pop(); 

  

        // Create a new internal node with 

        // frequency equal to the sum of the 

        // two nodes frequencies. Make the 

        // two extracted node as left and right children 

        // of this new node. Add this node 

        // to the min heap '$' is a special value 

        // for internal nodes, not used 

        top = new MinHeapNode('$', left->freq + right->freq); 

  

        top->left = left; 

        top->right = right; 

  

        minHeap.push(top); 

    } 

  

    // Print Huffman codes using 

    // the Huffman tree built above 

    printCodes(minHeap.top(), ""); 
} 

  
// Driver program to test above functions 

int main() 
{ 

  

    char arr[] = { 'F', 'E', 'C', 'B', 'D', 'A' .'G'}; 

    int freq[] = { 5, 9, 12, 13, 16, 45, 35 }; 

  

    int size = sizeof(arr) / sizeof(arr[0]); 

  

    HuffmanCodes(arr, freq, size); 

  

    return 0; 
}