• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • ✅ Time to vote for the top 3 models! The POLL for Hive's 6th HD Modeling Contest: Mechanical is now open! 📅 Poll close on July 16, 2024! 🔗 Cast your vote now!
  • ✅ The POLL for Hive's Texturing Contest #33 is OPEN! Vote for the TOP 3 SKINS! 🔗Click here to cast your vote!

[Snippet] Binary Heap

Level 31
Joined
Jul 10, 2007
Messages
6,306
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!!!
 
Level 20
Joined
Apr 22, 2007
Messages
1,960
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
 
Level 20
Joined
Apr 22, 2007
Messages
1,960
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.
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).
 
Level 31
Joined
Jul 10, 2007
Messages
6,306
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.
 
Level 20
Joined
Apr 22, 2007
Messages
1,960
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.
 
Level 14
Joined
Apr 20, 2009
Messages
1,543
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 :/?
 
Level 19
Joined
Aug 8, 2007
Messages
2,765
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)
 
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
 
Level 14
Joined
Apr 20, 2009
Messages
1,543
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?
 
Top