一类分配的一部分，我必须发挥各地与此代码为最大堆，然后将其转换，排序顺序，使最小的数字，而不是最大的数字，在顶端。例如，在100所有的数字是该节点的孩子，应该是一个二叉树堆的形状规则，数量100秉承。
我希望这是有道理的。此外，我只是一个初学者，所以如果你跟我像一个小学三年级，这将是好呀！
下面的代码。
#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)
{