[Snippet] Binary Heap

[Nestharus]

This resource has moved here.

--

gone

 

[Magtheridon96]

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]

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

 

[Magtheridon96]

I have an idea!
This could be used for a multiboard that sorts values like a leaderboard

 

[Nestharus]

no mag >.<, you'd use a BST for that.

 

[Nestharus]

Updated

Graveyard other

 

[Bribe]

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]

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]

Improved algorithm of delete

Added modify method


Please change thread title to Binary Heap : )

 

[HINDYhat]

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]

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]

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

... and then move the last node into that empty position

Or perhaps I misunderstood. This is a trivial operation anyway.

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

EDIT: Sorry, I was wrong. Let me think about this.
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]

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]

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.

 

[Bribe]

Opening thread.

 

[Nestharus]

And updated

 

[Fingolfin]

Finally something i have use for.
Will use it to sort nodes in A* searches and to get closest ports in WiF.

 

[Hashjie]

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

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

the library clearly states:

/*   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 :/?

 

[Nestharus]

Look up what an interface is : )

 

[Arhowk]

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

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

>>

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

 

[Nestharus]

no..

look up interface in programming >.<

edit
http://msdn.microsoft.com/en-us/library/87d83y5b(v=vs.80).aspx

 

[Magtheridon96]

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:

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

If you a maximum heap, define this:

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

 

[Hashjie]

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

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?

 

[Arhowk]

no..

look up interface in programming >.<

edit
http://msdn.microsoft.com/en-us/library/87d83y5b(v=vs.80).aspx

lol i so good programmer

 

[Nestharus]

struct Heap extends array
    private static method compare takes integer value1, integer value2 returns boolean
        return value1 >= value2
    endmethod

    implement BinaryHeap
endstruct

 

[Hashjie]

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