i need to make a program that implements a heapsort using a binary tree. i understand the algorithm for how to do the sort, and i understand how it would be done using an array, but for my class i have to use a binary tree. The problem i am having is that nodes dont have a getParent, and although the finding a parents "index" in the tree is either n-1/2 or n-2/2, i dont understand how to get the index of the current node.
for example in a binary tree that has 10 nodes, with the index at the root being 0, and going until 9 in level order, if i have the node the is at the index 9 for example, how do i know that that is where the node is? I cant filter back up the tree because the node doesnt have a getParent(), and im not sure how to filter down from the root to find it because i dont even know which side of the tree the node would be on?
Im probably just over complicating this but for the moment i am really confused so any help would be much appreciated. Thanks.