# [Snippet] Binary Heap

#### Nestharus

Level 31
This resource has moved here.

--

gone

Last edited by a moderator:

#### Magtheridon96

Level 36
You made so many new submissions, it took my computer 9 seconds to load the page (Jass section loaded in 2 seconds)

Anywho, this could be very useful if I ever plan on making a UnitsInRange Tree

#### Nestharus

Level 31
I don't suggest using this for UnitsInRange...

#### Bribe

Level 51
So if this is to be used for timers, you'd want to use something like R2I(time * 1000) to pass the value to be sorted? Then you'd use the return value of "insert" as the timer instance. It makes sense, and from what I can see it's approve-worthy.

#### Nestharus

Level 31
Bribe, not quite =).

You'd keep an integer and 2 real values and sort by those (to keep accuracy). One real value would be remaining time and the integer/real value would be a timestamp.

From here, you'd actually have a binary heap of queues of remaining times. A timer would only move to a different queue when paused/resumed. This allows nodes to just move to the back of the heap like a timer queue, meaning that there are less operations on the heap (faster).

You'd either want to use a table or an array to access the heap nodes via the remaining time or timeout. I'd almost recommend a table as that would give you accuracy of up to 6 decimal places pretty easily. An array would only do 2 and would be limited to between 0 seconds and 81.91 seconds.

You'd sort by (intTimestamp1-intTimeStamp2)+(realTimeStamp1-realTimeStamp2)+(realTimeRemaining1-realTimeReamining2)

Another thing is that you want to inline this directly into a timer system and use its nodes directly as the timer queue nodes.

When evaluating a trigger, in the get data method, you want to move down the queue (no need for end flags or anything).

In the resume method, move the current timer to the back of a queue or to another queue and update its timestamp.

In the expire method, loop through heap until remaining time > 0. To do this, add .001 to the current time and loop until current time is greater than the expected expiring time of the timer.

timer expire time: intTimestamp+realTimestamp+realRemainingTime.

intTimestamp+realTimestamp+realRemainingTime<currentTimestamp

Also, for a timer system, you'd really want to stress all variable names that are as short as possible and put these variable names into a globals block and keep them in a short library name. This is to maximize the speed of the timer system.

After doing all of this, you could have a timer system that is faster than regular timers and that definitely owns KT2.

Also, as you add timers, adds its boolexpr to the trigger that it belongs to. Do not build the triggers or clear the triggers in the expire method!!!

#### Nestharus

Level 31
Improved algorithm of delete

#### HINDYhat

Level 20
I'm not sure what exactly you're doing with delete because I'm tired and haven't read code in a long time and cba to try, but you seem to be using the typical bubble-down DELETEMIN/MAX algorithm (i.e., swap root with last element and then heapify from the root). This is clearly O(log n), but it rates at 2log n comparisons on average.

My algorithms professor from last semester said it was possible to do DELETEMIN/MAX with log n + O(1) comparisons on average. My technique for DELETEMIN (and I'm guessing what he was asking for) goes like this: empty the root element, and move the smallest of the root's children to the root. Continue this until you've reached the bottom of the heap, and then move the last node into that empty position.

If that doesn't make sense I'll try to write up some shitty pseudocode, but the jist of it is: you used to do 2 comparisons, and now you do 1. gg

#### Nestharus

Level 31
HINDYhat, you still have to index the last element into the empty position-

set foundPosition=lastElement

Then you'd have to bubble the last element up.

#### HINDYhat

Level 20
Nestharus said:
HINDYhat, you still have to index the last element into the empty position
HINDYhat said:
... and then move the last node into that empty position
Or perhaps I misunderstood. This is a trivial operation anyway.

Nestharus said:
Then you'd have to bubble the last element up.
Well, fair enough, but it won't bubble up very far usually, considering it's already on the heap's last level. Using the bubble-down algorithm, you replace the root with a node of relatively large key, so it is likely that you will have it bubble down further. I know that this is entirely informal, but it still sounds better than the bubble-down method. Maybe it wasn't what my professor had in mind (I never asked him personally).

#### Nestharus

Level 31
well, the bubble down is rather standard and guarantees O(log n) whereas the other method could possibly be 2*O(log n)-1.

And HINDYhat, thank you very much for commenting on algorithm : ).

If you ever want to review code of mine and find it hard to read, I can explain the algorithm I used ; P. After all, the algorithm is more important than the code : D.

#### HINDYhat

Level 20
well, the bubble down is rather standard and guarantees O(log n) whereas the other method could possibly be 2*O(log n)-1.

And HINDYhat, thank you very much for commenting on algorithm : ).

If you ever want to review code of mine and find it hard to read, I can explain the algorithm I used ; P. After all, the algorithm is more important than the code : D.

Both methods are O(log n) in the comparison model of time complexity. This should be clear, since in the worst case yours just bubbles all the way down the height of the heap doing 2 comparisons per level, and in the worst case mine goes down and then back up with 1 comparison per level. The expression "2O(log n) - 1" is just O(log n), but regardless that statement doesn't make sense.

But I'm not concerned with the algorithm's complexity; I'm counting actual comparisons here. I'm just curious because that one comment my professor made. I know that the bubble-down method is standard, but that doesn't make it the best. My last correction seems to make sense in that, both algorithms will perform equally badly in the worst case, but in the average case mine will be faster.

I'd be interested to see a benchmark though, because Jass might just be silly and take a whole lot of time on some instructions I'd say are trivial that are more present in my algorithm than in yours. The key is that mine would reduce the number of comparisons, but might increase other stuff.

#### Hashjie

Level 14
Is it me, or does it say that the compare method does not exist when implementing this allocator?

JASS:
``exitwhen (0 == parent or compare(parent.node.value, value))``

the library clearly states:
JASS:
``````/*   Interface:
*       private static method compare takes thistype value1, thistype value2 returns boolean
*           -   < for minimum heap
*           -   > for maximum heap
*/``````

but I can't see it inside the module :/?

#### Arhowk

Level 19
Is it me, or does it say that the compare method does not exist when implementing this allocator?

JASS:
``exitwhen (0 == parent or compare(parent.node.value, value))``

>>

JASS:
``exitwhen (0 == parent or parent.node.value > (or < o.O) value)``

#### Magtheridon96

Level 36
You have to write your own compare method in the struct so that the module would work with it.

This is what makes the Binary Heap resource very flexible. You can define how it decides whether something is "greater" or not.

Remember, this doesn't need to do it based on whether the actual values are greater or not

edit
If you want a minimum heap, inside your struct, define the following method:

JASS:
``````static method compare takes thistype value1, thistype value2 returns boolean
return integer(value1) < integer(value2)
endmethod``````

If you a maximum heap, define this:

JASS:
``````static method compare takes thistype value1, thistype value2 returns boolean
return integer(value1) > integer(value2)
endmethod``````

#### Hashjie

Level 14
Hmm odd, I'm getting a compiler error saying: Expected: create.
I'm using something like:

JASS:
``````interface myInterface
private static method compare takes thistype value1, thistype value2 returns boolean
endinterface

struct myStruct extends myInterface
static method compare takes thistype value1, thistype value2 returns boolean
return integer(value1) > integer(value2)
endmethod
endstruct``````

It's showing this error for the interface method. Am I using it in a wrong way? I've looked through some tutorials and couldn't figure out why.
Is it expecting a static create method :/? Because I tried adding that inside both my struct and my interface, the error still pops up.

I know that it's useful to have interfaces as they can set standards for your structs.
Some structs may have different implementations of a specific method then the standard set through the interface, which is why you need to define them inside the struct right?
It's basically something like a parent with children, where the children inherit some of the parents properties and functions unless overridden by the child?

#### Nestharus

Level 31
JASS:
``````struct Heap extends array
private static method compare takes integer value1, integer value2 returns boolean
return value1 >= value2
endmethod

implement BinaryHeap
endstruct``````

#### Hashjie

Level 14
JASS:
``````struct Heap extends array
private static method compare takes integer value1, integer value2 returns boolean
return value1 >= value2
endmethod

implement BinaryHeap
endstruct``````

ooooh, I get it. Thanks

Replies
2
Views
972
Replies
5
Views
1K
Replies
6
Views
2K
Replies
5
Views
1K
Replies
4
Views
2K