12,397,805 members (55,043 online)
Rate this:
See more:
For part of a class assignment I must play around with this code for a max heap, and then convert that sorting order so that the smallest numbers, rather than the largest numbers are at the top. For example, all numbers under 100 are children of that node, and should be under that number 100 adhering to the shape rule of a binary tree heap.

I hope this makes sense. Also, I am only a novice programmer, so if you talk to me like a third grader, that would be okay!

Here's the code.
```#include <iostream>
#include <stdio.h>
using namespace std;

// a simple random number generator (so we don't need to include stdlib.h)
int linearCongruentialNumberGenerator()
{
static unsigned long x=123456789;
return (x=69069*x+362437) & 0x7fffffff;
}

struct HeapNode
{
int value;
HeapNode * left;
HeapNode * right;
HeapNode(int a_value):value(a_value),left(0),right(0){}
/** adds a number to the heap tree, ensuring that the tree stays balanced, and the largest value stays nearest the top */
{
// if the new value is bigger than this value
if(child->value > value)
{
// the bigger value belongs here... give the new value this value.
int temp = value;
value = child->value;
child->value = temp;
}
// fill immidiate children first
if(left == 0)
left = child;
else if(right == 0)
right = child;
// if both children are filled, add to the least filled child.
else if(right->size() > left->size())
else
}
/** @return the number of nodes down this tree */
int size()
{
int total = 1;	// count itself as 1
if(left) total += left->size();
if(right)total += right->size();
}
/** @return a node that is no longer needed in the heap, with the top value in it */
HeapNode * removeTopNode()
{
HeapNode * toReturn = 0;
int temp = value;
// if the left value exists, and the right one doesnt OR the left one is bigger
if(left != 0 && (right == 0 || left->value >= right->value))
{
// pull up the left value (pushing this value down)
value = left->value;
left->value = temp;
// and ask the left child to keep pushing this value down, and pulling the next highest up
toReturn = left->removeTopNode();
// if the next highest IS the left one (after this value is pushed down)
if(toReturn == left)
// the left one will be returned as the extra tree node. remove its reference, its a goner
left = 0;
}
// if the right value is bigger than the left
else if(right != 0 && (left == 0 || right->value >= left->value))
{
// same logic as above, but for the right this time
value = right->value;
right->value = temp;
toReturn = right->removeTopNode();
if(toReturn == right)
right = 0;
}
// if there are no children passed along a better node to remove
if(toReturn == 0)
// this must be the node to remove
toReturn = this;
}
/** uses depth-first to print the heap as a line */
void printDepthFirst()
{
cout << value << " ";
if(left)left->printDepthFirst();
if(right)right->printDepthFirst();
}
/** @return how deep the heap goes (how many levels) */
int getDepth()
{
int d = 1;
int leftDepth = 0, rightDepth = 0;
if(left)	leftDepth = left->getDepth();
if(right)	rightDepth = right->getDepth();
d += (leftDepth > rightDepth)?leftDepth:rightDepth;
return d;
}
/** recursive delete function */
void release()
{
if(left)
{
left->release();
delete left;
left = 0;
}
if(right)
{
right->release();
delete right;
right = 0;
}
}
};

/** manages the Heap Binary Tree via a root node */
class MaxHeap_UsingBinaryTreeNodes
{
HeapNode * root;
public:
MaxHeap_UsingBinaryTreeNodes():root(0){}
~MaxHeap_UsingBinaryTreeNodes()
{
if(root)
root->release();
delete root;
}
{
HeapNode * newNode = new HeapNode(a_value);
if(root == 0)
root = newNode;
else
}
int removeTopNode()
{
int value = 0;
HeapNode * n = root->removeTopNode();
if(n == root)
root = 0;
value = n->value;
delete n;
return value;
}
int size()
{
if(root == 0)
return 0;
return root->size();
}
void printDepthFirst()
{
if(root != 0)
root->printDepthFirst();
}
void printTree()
{
if(root == 0)
return;
// determine how big the pyramid needs to be
int depth = root->getDepth();
int maxElements = 1;//depth
int inRow = 1;
for(int i = 0; i < depth; ++i)
{
maxElements += inRow;
inRow *= 2;
}
int * pyramidBuffer = new int[maxElements];
int defaultValue = 0xb44df00d;
for(int i = 0; i < maxElements; ++i)
{
pyramidBuffer[i] = defaultValue;
}
inRow = 1;
int index = 0;
bool couldHaveAValue;
int value;
HeapNode * cursor;
// fill data into the pyramid
for(int d = 0; d < depth; ++d)
{
for(int col = 0; col < inRow; ++col)
{
cursor = root;
couldHaveAValue = true;
for(int binaryDigit = 0; couldHaveAValue && binaryDigit < d; binaryDigit++)
{
if( ((col >> (d-binaryDigit-1)) & 1) == 0)
cursor = cursor->left;
else
cursor = cursor->right;
couldHaveAValue = cursor != 0;
}
value = (couldHaveAValue)?cursor->value:defaultValue;
pyramidBuffer[index++] = value;
}
if(d+1 < depth)
inRow *= 2;
}
int NUMCHARS = 2;
int maxWidth = (NUMCHARS+1)*inRow;
inRow = 1;
int betweenValues;
index = 0;
// print the pyramid
for(int d = 0; d < depth; ++d)
{
betweenValues = (maxWidth/inRow)-NUMCHARS;
for(int i = 0; i < leadSpace; ++i)
putchar(' ');
for(int n = 0; n < inRow; ++n)
{
if(pyramidBuffer[index] != defaultValue)
printf("%02d", pyramidBuffer[index]);
else
printf("..");
index++;
if(n+1 < inRow)
{
for(int i = 0; i < betweenValues; ++i)
putchar(' ');
}
}
putchar('\n');
inRow *= 2;
}
delete [] pyramidBuffer;
}
int getDepth()
{
if(root == 0)return 0;
return root->getDepth();
}
};

class MaxHeap_UsingArray
{
int * m_data;
int m_allocated;
int m_size;
int m_depth;
void allocateSize(int a_depth)
{
int perRow = 1;
int total = 0;
for(int i = 0; i < a_depth; ++i)
{
total += perRow;
perRow *= 2;
}
int * newData = new int[total];
if(m_data)
{
int min = (total<m_allocated)?total:m_allocated;>
for(int i = 0; i < min; ++i)
newData[i] = m_data[i];
delete [] m_data;
}
m_data = newData;
m_allocated = total;
m_depth = a_depth;
}
inline int parentOf(int a_index)
{
return (a_index - 1) / 2;
}
inline int leftChild(int a_index)
{
return (a_index * 2) + 1;
}
void bubbleUp(int a_index)
{
int cursor = a_index;
int parent = parentOf(a_index), value = m_data[a_index];
while (cursor > 0 && value > m_data[parent])
{
m_data[cursor] = m_data[parent];
cursor = parent;
parent = parentOf(cursor);
}
m_data[cursor] = value;
}
void bubbleDown(int a_index)
{
int cursor = a_index, child = leftChild(a_index);
int value = m_data[a_index];
while (child < m_size)
{
if (child < (m_size - 1) && m_data[child] < m_data[child+1])
++child;
if(value < m_data[child])
{
m_data[cursor] = m_data[child];
cursor = child;
child = leftChild(cursor);
}
else break;
}
m_data[cursor] = value;
}
public:
MaxHeap_UsingArray():m_data(0),m_allocated(0),m_size(0),m_depth(0){}
{
if(m_size >= m_allocated)
allocateSize(m_depth+1);
m_data[m_size] = a_value;
bubbleUp(m_size++);
}
int removeTopNode()
{
int value = m_data[0];
m_data[0] = m_data[--m_size];
bubbleDown(0);
return value;
}
int getDepth()
{
return m_depth;
}
int size()
{
return m_size;
}
void printTree()
{
int inRow = 1;
for(int d = 0; d < m_depth; ++d)
{
if(d+1 < m_depth)
inRow *= 2;
}
int NUMCHARS = 2;
int maxWidth = (NUMCHARS+1)*inRow;
int betweenValues;
int index = 0;
inRow = 1;
// print the pyramid
for(int d = 0; d < m_depth; ++d)
{
betweenValues = (maxWidth/inRow)-NUMCHARS;
for(int i = 0; i < leadSpace; ++i)
putchar(' ');
for(int n = 0; n < inRow; ++n)
{
if(index < m_size)
printf("%02d", m_data[index]);
else
printf("..");
index++;
if(n+1 < inRow)
{
for(int i = 0; i < betweenValues; ++i)
putchar(' ');
}
}
putchar('\n');
inRow *= 2;
}
}
};

#include <conio.h>	// for _getch()

void main()
{
int num;
int numRandomValues = 31;
//	MaxHeap_UsingBinaryTreeNodes
MaxHeap_UsingArray
heap;
for(int i = 0; i < numRandomValues; ++i)
{
num = linearCongruentialNumberGenerator() % 100;
if(heap.size() > 0)
{
printf("----------\n");
heap.printTree();
}
printf("[adding %2d] (%d of %d)\n", num, i+1, numRandomValues);
_getch();
}
while(heap.size() > 0)
{
printf("----------\n");
heap.printTree();
num = heap.removeTopNode();
printf("[removing %2d] (%d left)\n", num, heap.size()+1);
_getch();
}
cout << "done!" << endl;
}
```
Ignore the "end conio.h, stdio.h, and end iostream tags at the end. These are generated by this automatic text to html converter and do not belong in this program.Fixed now[/Edit]"
I am using Microsoft visual Studio 2010 under C++ dev environment. Thanks for all of your help.
Posted 28-Sep-11 12:13pm
Updated 28-Sep-11 14:01pm
v3
Legor 29-Sep-11 2:55am

You didnt state where you have problems. Nobody will look through this pile of code for you. Please specify what isnt working or where you need help exactly.

Rate this:

## Solution 1

At a glance, I'd say you should change
```void add(HeapNode * child)
{
// if the new value is bigger than this value
if(child->value > value)
```
to
```void add(HeapNode * child)
{
// if the new value is smaller than this value
if(child->value < value)
```

Top Experts
Last 24hrsThis month
 OriginalGriff 380 Richard Deeming 244 Richard MacCutchan 200 Karthik Bangalore 190 ppolymorphe 100
 OriginalGriff 6,508 Karthik Bangalore 2,572 ppolymorphe 2,480 F-ES Sitecore 1,977 Richard MacCutchan 1,952