# Heap implementation using pointer

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;

try{
newNode = new Node;
}
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;
}

• @Barry: it's the element counter. For example, 12 means the entered data will be the 12th element (at this time it has 11 elements). In its class version, you can have a protected 'int size' variable and increment it at the end of the insertHeap function. In that way, the function will have only two arguments. – Nejla Oct 28 '13 at 4:10
• @Barry: As I said above, the user doesn't need to track the size externally. I can't write it here due to characters limit. I write it as an answer – Nejla Oct 28 '13 at 12:29

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

class Heap(dict):

"Heap() -> Heap instance"

"Get the virtual value stored at the address."

"Set the virtual value meant for the address."
if value:
else:


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;

try{
newNode = new Node;
}
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;
}