So I've been trying to implement an algorithm to output a heap array in tree format. For instance if I have an array like A[10,6,8,2,4,3,6,0,1,3,2,2,1,0,2] I would like the output to be:
10-----6-----2-----0
| | |--1
| |--4-----3
| |--2
|--8-----3-----2
| |--1
|--6-----0
|--2
Update: Solved my question, I made an answer with the code for those interested.
A possible solution is to insert placeholders into the array and thus form a MxN matrix out if it. Then you can simply loop over it, insert a line feed after every row and indent cells having a placeholder.
This C++11 program outputs heap in a little bit different format:
// 10
// ||--------------||
// 6 8
// ||------|| ||------||
// 2 4 3 6
//||--|| ||--|| ||--|| ||--||
// 0 1 3 2 2 1 0 2
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<cmath>
#include<iomanip>
// http://stackoverflow.com/questions/994593/how-to-do-an-integer-log2-in-c
// will be used to compute height of the heap
size_t IntegerLogarithm2(size_t arg) {
size_t logarithm = 0;
while (arg >>= 1) ++logarithm;
return logarithm;
}
// will be used to compute number of elements at the level i
size_t IntegerPower2(size_t arg) {
if(arg)
return (size_t)2 << (arg-1);
else
return 1;
}
// returns total line length for the level
size_t LineLength(size_t level, size_t item_width, size_t spaces_between) {
return IntegerPower2(level) * (item_width + spaces_between) - spaces_between;
}
int main()
{
// The input heap array
std::vector<int> A = {10, 6, 8, 2, 4, 3, 6, 0, 1, 3, 2, 2, 1, 0, 2};
// The heap array split by levels
std::vector<std::vector<int> > levels;
// Height of the heap
size_t levels_number = IntegerLogarithm2(A.size() + 1);
levels.resize(levels_number);
// Now fill the levels
for (size_t i = 0; i < levels.size(); ++i) {
size_t elements_number = IntegerPower2(i);
levels[i].resize(elements_number);
for (size_t j = elements_number - 1, p = 0; p < elements_number; ++j, ++p)
levels[i][p] = A[j];
}
if (levels_number < 1) return 0;
int magnitude = (abs(A[0]) <= 1 ? 1 : abs(A[0]));
size_t tab_width = (size_t)floor(log(double(magnitude)) / log(10.0)) + 1;
// size_t longest_line = LineLength(levels_number - 1, tab_width, tab_width);
std::vector<std::string> text;
text.reserve(levels_number * 2 - 1);
// Do the aligned output to the strings array
for (size_t i = 0; i < levels_number; ++i) {
size_t outer_space_width = IntegerPower2(levels_number - 1 - i) - 1;
size_t inner_space_width = outer_space_width * 2 + 1;
std::string outer_space(outer_space_width * tab_width, ' ');
std::string inner_space(inner_space_width * tab_width, ' ');
std::ostringstream line;
line << outer_space;
if (i > 0) {
std::ostringstream branchline;
std::string joint(tab_width, '|');
std::string branch(inner_space_width * tab_width, '-');
branchline << outer_space;
if (levels[i].size() > 0) {
branchline << joint;
}
bool isline = true;
for (size_t j = 1; j < levels[i].size(); ++j, isline = !isline) {
if(isline)
branchline << branch << joint;
else
branchline << inner_space << std::setfill(' ') <<
std::setw(tab_width) << joint;
}
branchline << outer_space;
text.push_back(branchline.str());
}
if (levels[i].size() > 0) {
line << std::setfill(' ') << std::setw(tab_width) << levels[i][0];
}
for (size_t j = 1; j < levels[i].size(); ++j) {
line << inner_space << std::setfill(' ') <<
std::setw(tab_width) << levels[i][j];
}
line << outer_space;
text.push_back(line.str());
}
// Output the text
for (auto& i : text)
std::cout << i << std::endl;
return 0;
}
Yap, harder than it initially seemed. Effectively does what Sebastian Dressler proposed.
Here is the final implementation. Formatting scales with number length.
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
std::string do_padding (unsigned index, unsigned mlength){
std::string padding;
if (int((index-1)/2) != 0){
return (int((index-1)/2) % 2 == 0) ?
(do_padding(int((index-1)/2),mlength) + std::string(mlength+4,' ') + " ") :
(do_padding(int((index-1)/2),mlength) + std::string(mlength+3,' ') + " |") ;
}
return padding;
}
void printer (std::vector<int> const & tree, unsigned index, unsigned mlength){
auto last = tree.size() - 1 ;
auto left = 2 * index + 1 ;
auto right = 2 * index + 2 ;
std::cout << " " << tree[index] << " ";
if (left <= last){
auto llength = std::to_string(tree[left]).size();
std::cout << "---" << std::string(mlength - llength,'-');
printer(tree,left,mlength);
if (right <= last) {
auto rlength = std::to_string(tree[right]).size();
std::cout << "\n" << do_padding(right,mlength) << std::string(mlength+ 3,' ') << " | ";
std::cout << "\n" << do_padding(right,mlength) << std::string(mlength+ 3,' ') << " └" <<
std::string(mlength - rlength,'-');
printer(tree,right,mlength);
}
}
}
void print_tree (std::vector<int> & tree){
unsigned mlength = 0;
for (int & element : tree){
auto clength = std::to_string(element).size();
if (clength > mlength) {
mlength = std::to_string(element).size();
}
}
std::cout << std::string(mlength- std::to_string(tree[0]).size(),' ');
printer(tree,0,mlength);
}
int main() {
std::vector<int> test;
for(auto i =0; i<50; ++i){
test.push_back(rand() % 1000 + 1);
}
std::make_heap(test.begin(),test.end());
std::cout << "\n";
print_tree(test);
}