CareerCup

Pseudo Code:

/* Bottom Up recursive code.
* Basic Idea: Swap the right child to its parent bottom up to make it a Max Heap.
*/

NODE* BSTMaxHeapify(NODE* Tree)
{
if(Tree==NULL)
return Tree;
BSTMaxHeapify(Tree->left);
BSTMaxHeapify(Tree->right);
return(BSTMaxHeapSwap(Tree,Tree->right));
}

NODE* BSTMaxHeapSwap(NODE* Root, NODE* RootRight)
{
if(RootRight==NULL)
return Root;
else
Swap the Root and RootRight Node;
return RootRight;
}

Plz comment if I have made any mistake

How about just doing a simple in-order traversal of the BST. It would produce a sorted array which is indeed a max-heap!

max_heapify_bst(Tree *root) 
{
    if (!root) return;
    max_heapify_bst(root->left);
    max_heapify_bst(root->right);
    sift_down(root, root->right);
}

Do it same as Menaheap to BST. Will that not work? Please comment.

How about this approach?
O(n) to convert BST to sorted LL, and O(n) to convert sorted LL to heap

node* previous;
BST2LL(node* n)
{
..if(n==null) return;
..BST2LL(n->rightChild);
..if(previous!=null)
....previous->rightChild = n; // in the linked list, the rightChild is like "next"
..else
....root=n;
..previous=n;
..BST2LL(n->leftChild);
}

//step 1. BST to Linked List
BST2LL(root);

//step 2. LL to heap
node* i1=root;
node* i2=root->rightChild;
node* i3;
if(i2!=null) i3=i2->rightChild;

while(i1!=null)
{
..node* next = i1->right;
..i1->left = i2;
..i1->right = i3;
..i1 = next;
..if(i2!=null) i2 = i2->right; if(i2!=null) i2=i2->right;
..if(i3!=null) i3 = i3->right; if(i3!=null) i3=i3->right;
}

Please comment if i have made any mistake

In a BST, all the left nodes are correct for a max heap, so you just have to swap all the right hand nodes, and bubble the right hand nodes up as the new roots:

swapRight(node, parent)
{
  if node.left
    keepLeft(node.left)

  rightHolder = node.right
  node.right = parent

  if rightHolder
    newRoot = swapRight(node.right, node)
  else
    newRoot = node

  return newRoot
}

keepLeft(node)
{
  if node.left
    keepLeft(node.left)

  if node.right
    newRoot = swapRight(node.right, node)
  else
    newRoot = node

  return newRoot
}

root = swapRight(root, null)

build-heap is already o(n) operation..

To do it inplace : convert the bst to a sorted list :
Here is the code convert a sorted linked list to min heap:
invoke with sortedLLtoMinHeap(head,head->right);

void sortedLLtoMinHeap(node* head, node* start)
{
	if( start)
	{
		head->left = start; 
		rightchild = start->right
		start->parent = head;
	head->right = rightchild;
	if( rightchild)
		rightchild->parent = head
		SortedLLtoMinHeap(head->left, rightchild->right);
	return head;
}
}

TreeNode* bstToMaxHeap(TreeNode* root)
{
    if (root == NULL) return ;
    bstToMaxHeap(root->left);
    bstToMaxHeap(root->right);
    swap(root, root->right);
    sink(root->right); 
}
void sink(TreeNode* root)
{
         while (root && root->left)
         {
                      TreeNode* swapNode = root->left;
                      if (root->right && root->right->val > root->left->val)
                                     swapNode = root->right;
                     root->val = swapNode->val;
                     root = swapNode;
         }
         
}

I would think that doing an inorder travesral and then creating a heap out of it should be the way to go... Traversal would be done in O(n) and so should be building a heap out of the array.

Also, the extra memory would be with the array. One question: Does having an array not actually tantamount to the implicit usage of the stack in recursive calls?

Idea: revert the right-most path
For example,

10
     5     16
   1  3  14  20

to

20
           16
       10    14
     5     
   1  3

node* bst2maxheap(node *root, node *&min) {
  if (root == nullptr) {
    min = nullptr;
    return nullptr;
  }

  node *left_heap = bst2maxheap(root->left, min);

  node *right_min = nullptr;
  node *right_heap = bst2maxheap(root->right, right_min);

  root->right = left_heap;
  root->left = nullptr;

  if (right_min) {
    right_min->left = root;
    return right_heap;
  }

  return root;
}