merging two heaps in psedo code

[henri]

there is T a binary tree, for each z node (not a leaf) we define
NPL(z) (null path length) as the length of the shortest path from the node to the leaf.
we add npl[z] to each node.
binary tree T is called left tree if npl[left[z]]>=npl[right[z]]

the left tree H is called left heap if for every node z
key[parent[z]]<=key[z]
k- represents the priority if the heap

there are two left heaps
H1 with n1 nodes and H2 with n2 nodes
the merging operation is defined as follwed:
we choose the heap with the largest key in the rood
and merge it (recursevly) with the right side of the other heap.

and rearange it so the product will be a "left tree"
???

and prove that the complexity of the code is theta(lg n1 +lg n2)


how i tried:

first of all, do i represent the heaps as arrays?

[anduril462]

Read:
Forum guidelines
Homework policy
Help Vampires
How to Ask Questions the Smart Way

And don't start 3 threads for the same question. Duplicates:
heap data structure question..
number of nodes in a data structure proof..

[anduril462]

As for your question, the underlying representation is irrelevant.

For the merging algorithm, you should design your heap code so that it has a good interface, functions like heap_insert, heap_remove and maybe heap_peek, that do exactly what the names say. Whether it is an array or binary tree underneath wont matter to your merging algorithm.

As for the proof, no implementation is necessary, so the question of "representing it as an array" doesn't matter.

I have no idea why you included the stuff about left trees and NPL, I don't see how it relates to your heap merging algorithm.

First you need to understand heaps. If you can't do that, then you have no hope of doing this problem. Read your text book and class notes. Google for lots of tutorials and examples. Implement a min heap and a max heap as a tree, then do the same thing implementing them with arrays.