c++ | Help converting max heap to a min heap

See more:

C++

sorting

binary

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 */
	void add(HeapNode * child)
	{
		// 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())
			right->add(child);
		else
			left->add(child);
	}
	/** @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 total;
	}
	/** @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;
		return toReturn;
	}
	/** 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;
	}
	void add(int a_value)
	{
		HeapNode * newNode = new HeapNode(a_value);
		if(root == 0)
			root = newNode;
		else
			root->add(newNode);
	}
	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 leadSpace;
		int betweenValues;
		index = 0;
		// print the pyramid
		for(int d = 0; d < depth; ++d)
		{
			betweenValues = (maxWidth/inRow)-NUMCHARS;
			leadSpace = (betweenValues)/2;
			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){}
	void add(int a_value)
	{
		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 leadSpace;
		int betweenValues;
		int index = 0;
		inRow = 1;
		// print the pyramid
		for(int d = 0; d < m_depth; ++d)
		{
			betweenValues = (maxWidth/inRow)-NUMCHARS;
			leadSpace = (betweenValues)/2;
			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();
		heap.add(num);
	}
	printf("---------- DONE ADDING ");
	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.[Edit]Fixed now[/Edit]"
I am using Microsoft visual Studio 2010 under C++ dev environment. Thanks for all of your help.