how do i implement heap data structure using c++?

Question

Using this simple example of a binary heap. How would i implement this data structure using c++ code.

                               1
                              / \
                             3   6
                            /\   /\
                           5  9 8  

Also apart from being able to gain easy access to the max or min values in an array, how is this data structure useful?

the example come from the following link: http://www.algolist.net/Data_structures/Binary_heap

Answer 1

Here is my simplest C++ implementation for heap. The code is well-commented.

/*
Usage:
heap Heap;
Heap.clear();
Heap.insert(value);
Heap.remove();
Heap.print();
*/
struct heap {
    int myarray[NN+1]; // myarray to store the numbers as heap, 1 indexed
    int n;  // the number of nodes in my array
    heap() { // constructor
        clear(); // we clear the heap
    }
    void clear() { // initialize the heap
        n = 0; // initially there are no nodes in the heap
    }
    void insert( int K ) { // inserting an element K in the heap
        if( n == NN ) { // the heap is full
            printf("cannot insert any more element, the heap is full\n");
            return;
        }
        ++n; // so, we have a new element, we increased n before adding
        // the element because we start from index 1
        myarray[n] = K; // inserted the element at the rightmost position
        int p = n; // for keeping the current position
        while( p > 1 ) { // p = 1 means we are on the root, and its a heap
            int pr = p / 2; // pr is the parent of p
            if( myarray[pr] > myarray[p] ) { // parent is greater than child
                swap( myarray[pr], myarray[p] );
                p = pr; // now the new position of the current element is pr
            } else break; // otherwise its a heap, so we can stop here
        }
    }
    int remove() { // removing the minimum element from the heap
        if( n == 0 ) { // is the heap is empty
            printf("The heap is empty, cannot delete.\n");
            return -1;
        }
        int K = myarray[1]; // first element in the heap is the minimum
        myarray[1] = myarray[n]; // brought the last element in 1st position
        n--; // as we removed one element, now we need to maintain the heap

        int p = 1; // as we moved the rightmost element in index 1
        while( 2 * p <= n ) { // means p has at least one child, if 2*p > n
            // we are sure that p is in the last level
            int ch = 2 * p; // contains the index of the child
            if( 2 * p + 1 <= n ) { // right child exists
                if( myarray[ch] > myarray[ch+1] ) // right child is smaller
                    // than left child
                    ch++; // ch contains the index of the right child
            }
            if( myarray[p] > myarray[ch] ) { // so, current node is larger
                // than its child
                swap( myarray[p], myarray[ch] );
                p = ch; // new position of the current element
            } else break; //current node is smaller than its children, so heap
        }
        return K; // as we stored the minimum element in K
    }

    void print() { // printing the heap
        printf("Number of elements: %d\n", n);
        for( int i = 1; i <= n; i++ ) printf("%d ", myarray[i]);
        printf("\n");
    }

    // Time: O(nlogn)
    // Extra space: O(1) as we will pass the input array as res here
    void heapSort(int* res) {
        for(int i = 0, len = n; i < len; ++i) {
            res[i] = remove();
        }
    }
};