Computational power of deterministic versus nondeterministic min-heap automata
It seems that for this model, non-deterministic machines are not equivalent to deterministic ones, for basically the same reason that deterministic PDAs are not equivalent to non-deterministic ones.

Consider the language
$$L =\\{ x\$y \mid |x|=|y| \wedge x\ne y\\}$$
(where $\$$ is a special sign not contained in $x$ and $y$).

I claim that a non-deterministic machine $N$-$HAL$ can decide this language: It performs the same as the PDA for $L$. The standard PDA solution uses the stack only to count offsets: it nondeterministically guesses an offset $i$, remembers the value of $x_i$ (adding a symbol to the stack at each step), then the PDA ignores the input until it find the $\$$, and then it pops symbols out of the stack until it is empty. At this stage we are exactly at $y_i$ and he PDA can check if $x_i \ne y_i$. (if anything goes wrong in the middle, the PDA "dies"). 
Since the stack alphabet is unary, it can be simulated with a min-heap machine. 
Actually: any $L$ that is is accepted by a PDA with a unary alphabet can be accepted by a min-heap machine. (I'm ignoring, maybe, another special sign added to identify an empty stack, but an equivalent sign can be added to the heap)

For the other direction, I don't have the formal proof, but here are my thoughts:

I claim that a deterministic machine $D$-$HAL$ is incapable of deciding this language. Intuitively, the content of the heap can not be correlated with $x$ (otherwise, permute $x$. the content of the heap remains the same..). This suggests that only thing that matters is the number of elements in the heap, but then, if $D$-$HAL$ can decide $L$, so can a deterministic-$PDA$.

Edit: more details about the "permute $x$" claim. Assuming Raphael's conjecture 
there exist $x_1$ and $x_2$ that after reading them, the content of the heap is the same.
Then consider the words $x_1\$x_1$ and $x_2\$x_1$. The content of the heap is the same when the HAL gets to the dollar sign, thus it must either accept both or reject both. contradiction.

anyone sees an immediate proof for the conjecture?