Skip to main content
Software Engineering

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

6
  • The difference with this is that you must know the size of the array before creating it. With my implementation, you can put any arbitrary number of elements in, either at the beginning or at any point later on. It is true that all inserted elements will end up as leaf nodes, but since popping the top causes random percolation, they might not stay down there. It means that a recently added element is less likely to reappear right away, which is not necessarily a bad thing. (Think of the shuffle feature on an MP3 player - you don't WANT the same song twice in a row.) Commented Jul 31, 2013 at 14:57
  • But you've explained that under the covers, you use an array that gets resized. The same method can be used to resize the array here. It means an amortized cost on insertion of...hmm. I suspect it's O(1). Commented Jul 31, 2013 at 16:41
  • I'm not sure your example about the orc's 30% hit rate is the best example - you could get close to that simply by calculating a random number at the time of attack. (e.g. if (rand(100) < 30)) It might not end up being exactly 30% due to randomness, but nobody would notice. If the Ace of Spades turns up twice in a deck of cards, however, it's a bigger problem. Of course you know the size of a standard deck in advance: 52 cards. But imagine a scenario where you don't know that, and it might change frequently over time. I'd say both methods have valid use-cases. Commented Jul 31, 2013 at 19:07
  • 1
    Darrel, the distinction is important. Players don't want randomness--they want fairness. A really random number may miss 100% of the time despite the probability being 30%. Players often want (when you press on it) a guaranteed 30% hit rate over some number of swings--which is decidedly NOT random. Commented Aug 1, 2013 at 14:07
  • It's a fine balance, though - Over how many hits should the 30% hit rate be a guarantee? Over too small a range (e.g. 3 out of 10), and it's only slightly random, almost predictable. Make the range too large (300 out of 1000), and it's almost no different from just purely random. In either case, it'd be very different to tell whether the chances were calculated ahead of time or on the fly. Do you expect the average player to sit and count exactly how many hits per 100 swings occur? A few might, but most wouldn't care. Commented Aug 2, 2013 at 2:12