First time poster. I'm having trouble identifying the way to represent a heap tree as a pennant forest, I understand that each pennant is a subtree of the heap but When i looked at an example i simply didn't understand how it works. Any help is appreciated, thanks.
2026-04-23 06:24:34.1776925474
Heap tree to Pennant forest
402 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
Ok so this is coming up on an assignment I'm working on, and I think I have the answer ou're looking for. Hopefully I can explain it ok enough.
First, draw out the heap you want to turn into a pennant forest. It's just a binary tree, and pretty straightforward. Pay attention to which element of the tree is the last one you add.
Then, work your way from the root of the tree to that last element you took note of. Every time you go from node to node, put a little line through the edge between those two nodes.
Now below the actual tree, draw out all the subtrees that you get from "cutting" the edges" from largest to smallest subtrees. I know that's not especially cler, but like the first one will be the half of the tree you didn't go down to get to that last element, and then you keep working down the tree.
Maybe an example would help idk: say the heap has 15 nodes. So, to get to the last one, you go right, right, right. So, the first pennant is the left half of the whole tree. Then, you're looking for the next biggest subtree, so you go down a level, and hey you went right again so the next pennant is going to be the left half of the subtree, etc.
The descriptor for a pennant tree goes like D(x1, x2, ... xn), where n is the height of the tree, and all the xs are either 0, 1 or 2, and correspond to the number of pennants in the pennant tree that have that height. Sooo for the heap of 15 nodes, the pennant descriptor is D(1,1,1,1).