C ++ |帮助将最大堆转换为最小堆 [英] c++ | Help converting max heap to a min heap
本文介绍了C ++ |帮助将最大堆转换为最小堆的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
对于类分配的一部分，我必须使用此代码进行最大堆操作，然后转换排序顺序，以便最小的数字而不是最大的数字在顶部.例如，所有小于100的数字都是该节点的子代，并且应遵循二进制树堆的形状规则，小于100.
我希望这是有道理的.而且，我只是一个新手程序员，所以如果您像三年级生一样跟我说话，那就没关系！
这是代码.
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;
}
忽略结尾处的"end conio.h，stdio.h和end iostream标记.这些标记是由此自动文本转换为html转换器生成的，不属于此程序. 已修复[/编辑]"
我在C ++开发环境下使用Microsoft visual Studio 2010.感谢您的所有帮助.
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.
推荐答案
一目了然，我说您应该更改
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)
到
void add(HeapNode * child)
{
// if the new value is smaller than this value
if(child->value < value)
这篇关于C ++ |帮助将最大堆转换为最小堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
