Heap implementation using pointer

Question

I know heaps are commonly implemented by an array. But, I wanted to share my pointer implementation and have your feedback(s) :)

General idea:

1. I convert the index to its binary value and then trace the heap (0 = leftChild & 1 = rightChild)] Note: The first 1 is for entering the root.

2. I do the push at the same time.

Example: for the 12th element, 12 = 1100. The first 1 is for entering the root. Now I trace the heap by following 100.

    struct Node{
         Node *leftChild;
         Node *rightChild;
        int data;
    };

    bool insertHeap(Node **heap, int data, short index){
        Node *newNode, *temp, *parent;
        int tempData;
        short mask = 0x80;

    try{
        newNode = new Node;
    }
    catch (bad_alloc& e) {
        cerr << "Memory allocation error: " << e.what() << endl;
        return false;
    }

    while (!(index & mask)) index <<= 1;

    index <<= 1;
    parent = NULL;
    temp = *heap;

    while (temp){
        if (data > temp->data){
            tempData = temp->data;
            temp->data = data;
            data = tempData;
        }       
        parent = temp;

        if (!(index & mask)) temp = temp->leftChild; 
        else temp = temp->rightChild;

        if (temp) index <<= 1;
    }

    newNode->leftChild = NULL;
    newNode->rightChild = NULL;
    newNode->data = data;

    if(!parent){
        *heap = newNode;
        return true;
    }

    if (!(index & mask)) parent->leftChild = newNode;
    else parent->rightChild = newNode;

    return true;
}

This is my main():

#include <iostream>
using namespace std;

int main (){
    Node *heap = NULL;
    int arr[13] = {3,6,8,1,5,9,4,2,0,7,11,14,13}; 

    for (int i=0; i<13; i++) insertHeap(&heap, arr[i], i+1);   
    return 0;
}

Answer 1

You could also use a map, associative array, or dictionary to implement a heap (like the following):

class Heap(dict):

    "Heap() -> Heap instance"

    def retrieve(self, address):
        "Get the virtual value stored at the address."
        return self.get(address, 0)

    def store(self, value, address):
        "Set the virtual value meant for the address."
        if value:
            self[address] = value
        else:
            self.pop(address, None)

Answer 2

This class uses a member variable and hides the size completely. As you can see there is no need to know the index value. It can be hidden from the user. (Note: This class is not complete. It's necessary to have ~cHeap() to free up all the allocated memories)

#include <iostream>
using namespace std;

struct Node{
    Node *leftChild;
    Node *rightChild;
    int data;
};

class cHeap{
protected:
    short size;
    Node *heap;

public:
    cHeap();
    bool insertHeap(int data);
};

cHeap::cHeap(){
    heap = NULL;  
    size=0; // here we initialise size
}

    bool cHeap::insertHeap(int data){
        Node *newNode, *temp = heap, *parent = NULL;
        int tempData, index;
        short mask = 0x80;

        try{
            newNode = new Node;
        }
        catch (bad_alloc& e) {
            cerr << "Memory allocation error: " << e.what() << endl;
            return false;
        }

        size++; // here we increment size by one (for each insertion)
        index = size;
        while (!(index & mask)) index <<= 1;    
        index <<= 1;

        while (temp){
            if (data > temp->data){
                tempData = temp->data;
                temp->data = data;
                data = tempData;
            }       
            parent = temp;

            if (!(index & mask)) temp = temp->leftChild; 
            else temp = temp->rightChild;

            if (temp) index <<= 1;
        }

        newNode->leftChild = NULL;
        newNode->rightChild = NULL;
        newNode->data = data;

        if(!parent){
            heap = newNode;
            return true;
        }

        if (!(index & mask)) parent->leftChild = newNode;
        else parent->rightChild = newNode;
        return true;
    }

    int main(){
        cHeap myHeap;

        int arr[13] = {3,6,8,1,5,9,4,2,0,7,11,14,13}; 

        for (int i=0; i<13; i++) myHeap.insertHeap(arr[i]);  // as you can see you have nothing to do with size tracking
        return 0;
    }