current community

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite

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;
}
share|improve this question
 
Heap insert should take 2 arguments: the heap and the value. What is the 3rd one? –  Barry Oct 28 '13 at 3:56
 
@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 Ghaboosi Oct 28 '13 at 4:10
 
Doesn't seem like a good implementation if the user has to keep track of your object's size externally... –  Barry Oct 28 '13 at 11:58
 
@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 Ghaboosi Oct 28 '13 at 12:29
add comment

2 Answers

up vote 1 down vote

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)
share|improve this answer
add comment
up vote 0 down vote

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;
    }
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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