'How to correctly space out an array that's treated like a binary heap tree?
The project I'm working on is to create an array that stores elements in the same order that a binary max-heap tree would, the code is provided below. So far I have it where it can correctly print out the different rows with the correct elements, but I struggle to add the correct spacing in front and between each element to make them stored correctly, I've tried various for loops combined with iomanip, but to no avail. Here's an example of what I want:
45
30 28
15 10 18 20
10 2 3 4 5 6 7 8
each parent is located in the middle of each child. The big issue I have is that the spaces are not only determined by the amount of items, but also by how many digits each child has. Below is the code I have, currently it prints out the items in a basic pyramid shape
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void swap(int& a, int& b){
int temp = a;
a = b;
b = temp;
}
void makeHeap(int a[], int i){
int parent = (i - 1)/2;
if(a[parent] > 0){
if(a[i] > a[parent]){
swap(a[i], a[parent]);
makeHeap(a,parent);
}
}
}
void insert(int a[],int& index, int value){
index++;
a[index-1] = value;
makeHeap(a,index - 1);
}
void printHeap(int a[], int size){
int spaces = size;
int rows = ceil(log2(size));
for(int i = 0; i < size; ++i){
if(ceil(log2(i + 1)) - log2(i+1) < 0.001){// calculating if we are on the start of a new row, we have to check the difference for small cases where we may false positives. Possibly not needed for this language/ case
cout <<'\n';
for(int space = 1; space <= rows-i; space++)
cout <<" ";
}
cout << a[i] << " ";
}
}
int main() {
int amount = 5;
int size = 7;
int heap[100] = {45,30,28,15,10,18,20};
cout << "Enter the values to be stored on the heap: ";
while(true){
int temp;
cin >> temp;
insert(heap,size, temp);
if(cin.peek() == '\n')
break;
}
// int i = 3;
// int w = static_cast<int>(ceil((log2(i + 1)))) % 2;
// cout << w;
printHeap(heap, size);
}
Some info that may be helpful: The left child is calculated by 2*k+1 the right child is calculated by 2*k+2 and the parent is calculated by (k-1)/2 using int division.
Solution 1:[1]
When you look at the desired output and at each column (with 1 character width), you see there is exactly 1 digit in that column. In other words, when you visit the nodes in the tree in an in-order sequence, you'd fill those columns from left to right without any additional spacing.
So let's visit those nodes in that order, and adapt a single x-coordinate by adding to it the width of the current node's number (its number of digits). That will give us the absolute offset (from the left margin) for each number. We could store that offset in a second array called offsets, so that a[i] should be displayed at offsets[i].
We then still need to determine the vertical offset, but that is easier, as the array has the values in level order, and we know how many values can fit on one level (it doubles each time). So with that information we know when to output a newline character.
Here is the code for that:
int inorder_successor(int size, int i) {
if (i*2+2 < size) { // has right child
i = i*2+2; // right
while (i*2 + 1 < size) { // has left child
i = i*2 + 1; // left
}
} else { // has no right child
while (i > 0 && i % 2 == 0) { // is right child of parent
i = (i - 1) >> 1; // get parent
}
if (i == 0) return -1; // no successor
i >>= 1; // get parent
}
return i;
}
void printHeap(int a[], int size){
int offsets[size];
int i = -1;
int x = 0;
while (true) {
i = inorder_successor(size, i);
if (i < 0) break; // all nodes visited
offsets[i] = x;
x += to_string(a[i]).length();
}
x = 0;
int newline_before = 1;
for (int i = 0; i < size; i++) {
if (i == newline_before) {
cout << "\n";
x = 0;
newline_before = newline_before * 2 + 1;
}
cout << string(offsets[i] - x, ' ') << a[i];
x = offsets[i] + to_string(a[i]).length();
}
cout << "\n";
}
Solution 2:[2]
Try this code
Idk if this is what you wanted but you can try it and you can see if it was the thing you looked for
* {
margin: 0;
padding: 0;
box-sizing: border-box;
max-width: 100vw;
list-style: none;
scroll-behavior: smooth;
}
body {
height: 100%;
margin: 0;
background-color: white;
font-family: Poppins;
min-height: 100vh;
}
a {
color: black;
}
/* ----------------------------------------------------------Landing Page -------------------------------------*/
.full-height-grow {
height: 100%;
display: flex;
flex-direction: column;
}
section {
display: flex;
height: 100vh;
width: auto;
max-width: 80vw;
min-width: 75vw;
justify-content: center;
align-items: center;
margin: 0 auto;
}
.about-container {
padding-top: 100px;
height: 100vh;
width: 90vw;
max-width: 90vw;
display: flex;
flex-direction: column;
align-items: center;
text-align: center;
}
.about-img {
border-radius: 50%;
height: calc(80px + 40%);
width: auto;
}
.about-h1 {
font-family: 'Poppins', sans-serif;
color: rgb(255, 42, 95);
margin-top: 30px;
margin-right: -30px;
margin-left: -30px;
font-size:calc(12px + 0.8vw) ;
}
.about-h2 {
font-family: 'Poppins', sans-serif;
color: rgb(17, 17, 17);
margin-right: -30px;
margin-left: -30px;
font-size:calc(15px + 2vw) ;
font-weight: 500;
opacity: 0.9;
}
.about-desc {
font-family: Lora;
font-size:calc(10px + 1.2vw);
line-height: 1.8;
color: #888888;
text-align: center;
margin-left: 25vw;
margin-right: 25vw;
overflow:hidden;
z-index: 2;
width: auto;
}
.about-tasks-container {
align-self: center;
background-color: blanchedalmond;
max-width: 100vw;
width: 100vw;
display: flex;
justify-content: space-evenly;
text-align: center;
flex-direction: row;
flex-grow: 0;
}
.about-task-heading {
font-size: 30px;
}
.about-tasks-resources {
}
.about-tasks-learning {
}```
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | trincot |
| Solution 2 | Griphcode |