Memleaks in Tree made by Nodes

I implemented a whole Skew Heap in C++11, but reviewing the code I noticed some memory leaks. I made a MCVE and tracked down the function that was causing (at least some of) them, but I don't understand the reason. While I tried to keep the code as simple as possible, the example is still a little bulky due to the OOP, sorry for that.

The structure has a pointer to the root of the heap, and then each node has a value and pointers to his sons and his father. I am assuming that I don't need to iterate the whole structure when deleting, according to this post and also that deleting already removed pointers is all right.

The code:

#include <iostream>   // log
#include <algorithm>  // swap
#include <cstdlib>

template <class T>
class SkewHeap {
    class Node {  // SkewHeap's inner class
    public:
        // Constructors:
        Node(T n, Node* f = nullptr, Node* l = nullptr, Node* r = nullptr)
          : key(n), father(f), left(l), right(r) {}
        ~Node() {
            delete father;
            delete left;
            delete right;
        }

        T key;
        Node* father;
        Node* left;
        Node* right;
    };

    // Attributes:
    Node* head;

    // Auxiliar functions:
    Node* merge(Node* n1, Node* n2, Node* p = nullptr) {
        // Base case
        if (n1 == nullptr || n2 == nullptr) {
            if (n1 == nullptr)
                std::swap(n1, n2);
            //else
                //n1->father = p;
        }

        // Recursive step
        else {
            if (n2->key < n1->key)
                std::swap(n1, n2);

            std::swap(n1->left, n1->right);
            //n1->father = p;
            n1->left = merge(n1->left, n2, n1);
        }
        return n1;
    }

public:
    // Constructors:
    SkewHeap(T root) : head(new Node(root)) {
        std::clog << "***Default construction" << std::endl;
    }
    ~SkewHeap() {
        delete head;  // Should I iterate the whole data structure?
    }

    // Operations:
    void merge(SkewHeap* h) {
        head = merge(head, h->head);  // recursive function
    }

    void insert(T k) {
        SkewHeap<T>* h = new SkewHeap(k);
        merge(h);
    }

};

int main() {
    SkewHeap<int>* h1 = new SkewHeap<int>(5);
    SkewHeap<int>* h2 = new SkewHeap<int>(4);
    h1->merge(h2);
    h1->insert(3);
    exit(EXIT_SUCCESS);
} 

At first I thought that the memleaks came from the merge() function, but apparently came from the insert() one. When I run the code without using the insertion, I only get still reachable blocks in valgrind, which as far as I know it's OK. On the other hand, inserting gives me a block definitely lost.

Now my questions are:

• Shouldn't the insert() allocation get cleaned as soon as it goes out of scoop?
• How could I link the parent node when merging without potential memory leaks? (This is a more secondary thing)

In case someone want to see the full code, I (wrongly) posted it on Code Review