Create a c++ program follow the following instructions, below the instructions, i also include a minheap implementation that you can use in the program
Game Description:
Doublet is a word transformation puzzle where the goal is to transform a start word into an end word by changing one letter at a time. Each intermediate word formed during the transformation must be a valid word from a provided list and must maintain the same length as the original words.
Objective:
Find the shortest possible sequence of valid word transformations from the start word to the end word.
Example Transformation:
Transforming HEAD to TAIL:

HEAD → HEAL → TEAL → TELL → TALL → TAIL
Program Specifications

Source File:
doublet.cpp
Executable Name:
doublet
Program Invocation:
The program is executed via the command line with three parameters:

./doublet <start_word> <end_word> <word_list_file>
Example:

./doublet head tail words.txt
Case Sensitivity:
All operations are case-insensitive. For instance, "HEad" and "heAD" are treated equivalently to "HEAD".
Word List File Format (words.txt):

First Line:
An integer n representing the number of words in the file.
Next n Lines:
Each line contains one valid word. Words may have trailing whitespace.
Additional Notes:
No Duplicate Words: Each word is unique.
Guaranteed Inclusion: Both the start and end words are guaranteed to be present in the word list.
File Size: Files may contain up to 1 million words.
Formatting: The file is properly formatted with no malformed entries. There may be blank lines at the end of the file.
Example words.txt:

7
head
heAl
hem
Tail
tell
taLL
teal
Algorithm Implementation

Search Algorithm:
A* (A-Star) Search Algorithm
Heuristic Function (h):
Incorrect Letters Count:
Counts the number of letters in the current word that do not match the corresponding letters in the end word. Example:
Current word: DATA
End word: SALT
Heuristic (h) = 3 (letters D→S, A→A, T→L, A→T → 3 mismatches)
Cost Function (f):
[
f = g + h
]
g:
The number of transformations (or steps) taken from the start word to the current word.
h:
The heuristic value as defined above.
Priority Calculation for Tie-Breaking:
[
\text{priority} = f \times (n + 1) + h
]
n: Length of the word.
Purpose:
Ensures that:
Primary: Moves with the smallest f-value are prioritized.
Secondary: If multiple words have the same f-value, the one with the smallest h-value is chosen.
Tertiary: If both f and h values are identical, the word that is lexicographically smaller (based on fully capitalized versions) is selected.
Graph Construction:
Nodes:
Each word in the word list is a node.
Edges:
An edge exists between two nodes (words) if they differ by exactly one letter.
Efficiency Considerations:
Avoid O(n²) Complexity:
Instead of comparing each word with every other word to find neighbors, generate all possible one-letter variations of each word and lookup their existence in the word list using an efficient data structure (e.g., hash tables).
Data Structures:
Utilize sophisticated data structures (like hash maps) to enable fast lookup of valid words during graph construction.
Heap Implementation:
Custom MinHeap:
Implement a custom min-heap (from previous assignments) to manage nodes during the A* search. STL priority_queue is prohibited.
Handling Multiple Paths:
Duplicate Nodes:
If a node is reached via multiple paths, it can be re-added to the heap with updated priorities.
Recognition of Processed Nodes:
Ensure that nodes already removed and processed from the heap are not reconsidered, even if duplicates exist in the heap.
Tie-Breaking Rules

When multiple nodes have the same priority during the A* search, resolve ties as follows:
Primary Tie-Breaker:
Choose the node with the smallest f-value.
Secondary Tie-Breaker:
If f-values are identical, select the node with the smallest h-value (equivalent to the largest g-value).
Tertiary Tie-Breaker:
If both f and h values are identical, choose the node with the lexicographically smaller string, using fully capitalized versions for comparison.
Performance Tracking

Expansions Count:
Definition:
The number of unique words that the algorithm considers (i.e., removes from the heap).
Tracking Rules:
Increment the expansions count each time a word is removed from the heap.
Do Not Increment for duplicate removals of the same word.
The start word is counted as an expansion (starts from 1).
The end word is not counted.
Output Specifications

Upon successful completion, the program should output exactly two lines to stdout:
First Line (<steps>):
The minimum number of transformations required to convert the start word to the end word.
Second Line (<expansions>):
The total number of expansions performed by the A* algorithm to find the solution.
Example Output:

6
15
(Here, 6 represents the number of steps in the transformation, and 15 represents the number of expansions.)
Compilation and Execution

Makefile Target:
Typing make doublet should compile the program and produce an executable named doublet within the hw3 directory.
Execution Example:

./doublet head tail words.txt
Additional Constraints and Notes

Large Word Lists:
The program must efficiently handle word lists containing approximately 1 million words.
No Valid Transformation:
In cases where no valid transformation path exists between the start and end words, the program should handle this gracefully (specific handling behavior may need to be defined, such as outputting a specific message or a predefined number).
Assumptions:
The word list file is properly formatted as per the specifications.
There are no duplicate words in the word list.
Both the start and end words exist within the word list.
Implementation Restrictions:
No STL priority_queue:
Must use a custom heap implementation for managing the priority queue in the A* algorithm.
No STL maps:
Avoid using std::map; instead, consider using hash-based structures for efficient lookups.
Summary of Key Requirements

Functionality:
Transform a start word to an end word by changing one letter at a time.
Each intermediate word must be valid and present in the provided word list.
Achieve the transformation in the fewest number of steps.
Algorithm:
Implement the A* search algorithm with the specified heuristic.
Use a custom min-heap for managing nodes during the search.
Performance:
Efficiently handle large word lists (up to 1 million words).
Optimize graph construction to avoid excessive computational complexity.
Output:
Display the number of transformation steps and the number of expansions performed.
Coding Constraints:
Case-Insensitive: All operations should disregard letter casing.
No Use of Certain STL Components: Must implement required data structures manually or use alternatives.

#ifndef MINHEAP_H
#define MINHEAP_H

#include <vector>
   
template <class T>
struct Heap { //struct to hold heaps data and priority
       T data;
       int priority;
       Heap(T d, int prio) :  data(d), priority(prio) {};
};

template <class T>
class MinHeap {
    public:
        MinHeap(int d);
        /* Constructor that builds a d-ary Min Heap
        This should work for any d >= 2,
        but doesn't have to do anything for smaller d.*/
        ~MinHeap();

        void add(const T& data, int priority);
        /* adds the item to the heap, with the given priority. */

        const T & peek() const;
        /* returns the element with smallest priority.  
        Break ties however you wish.  
        Throws an exception if the heap is empty. */

        void remove();
        /* removes the element with smallest priority.
        Break ties however you wish.
        Throws an exception if the heap is empty. */

        bool isEmpty();
        /* returns true iff there are no elements on the heap. */

    private:
        // whatever you need to naturally store things.
        // You may also add helper functions here.
        std::vector<Heap<T>> heap_; //store heaps
        int d_; //d-ary

        void bubbleUp (size_t i);
        void trickleDown (size_t i);        
};


 //implementatition
template <class T>
MinHeap<T>::MinHeap (int d) : d_(d) {
    if (d <2){ //check for invalid d
        throw ("d must be greater than 2");
    }
}

template <class T>
MinHeap<T>::~MinHeap() {} //no dynamic mem


template <class T>
void MinHeap<T>::add(const T& data, int priority) {
    //create a new help and add to back
    Heap<T> newHeap(data, priority);
    heap_.push_back(newHeap);

    bubbleUp(heap_.size()-1); //maintain heap property
}

template <class T>
const T& MinHeap<T>::peek() const {
    if (heap_.empty()) {
        throw ("Heap is empty");
    }
    return heap_[0].data; 
}

template <class T>
void  MinHeap<T>::remove() {
    if (heap_.empty()) {
        throw ("Heap is empty");
    }

    //swap  root with last element then remove root
    heap_[0] = heap_[heap_.size()-1];
    heap_.pop_back();

    trickleDown(0); //maintain heap property
}

template <class T>
bool MinHeap<T>::isEmpty() {
    return heap_.empty();
}

template <class T>
void  MinHeap<T>::bubbleUp(size_t i) {
    if (i>0){ //check if there is a parent
        if (heap_[i].priority < heap_[(i-1)/d_].priority){
            std::swap(heap_[i], heap_[(i-1)/d_]);
            bubbleUp((i-1)/d_);
        }
    }
}

template <class T>
void  MinHeap<T>::trickleDown(size_t i) {
    size_t child = d_*i + 1;
    if (child >=  heap_.size()) { //check if there is children
        return;
    }    

    //since there are many children, find the smallest child
    size_t minChild = child;
    for (size_t j = child+1; j < heap_.size()  && j < child + d_; j++) {
        if(heap_[j].priority < heap_[minChild].priority){
            minChild = j;
        }
    }
    
    if (heap_[minChild].priority < heap_[i].priority) {
        std::swap(heap_[minChild], heap_[i]);
        trickleDown(minChild);
    }
}
   #endif