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;
}
  • @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"

    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)

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;
    }

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.