StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The specific datastructure you want is probably the <i>implicit heap</i>. The raw datastructure is just an array; for convenience, say that it is N=2^n elements in size, and that you want to maintain the largest N-1 elements.</p> <p>The idea is to treat the array (call it A) as a complete binary tree of depth n:</p> <ul> <li> ignore A[0]; treat A[1] as the root node <li> for each node A[k], the children are A[2*k] and A[2*k+1] <li> nodes A[N/2..N-1] are the leaves </ul> <p>To maintain the tree as a "heap", you need to ensure that each node is smaller than (or equal to) its children. This is called the "heap condition":</p> <ul> <li> A[k] <= A[2*k] <li> A[k] <= A[2*k+1] </ul> <p>To use the heap to maintain the largest N elements:</p> <ul> <li> note that the root A[1] is the smallest element in the heap. <li> compare each new element (x) to the root: if it is smaller (x<A[1]), reject it. <li> otherwise, insert the new element into the heap, as follows: <ul> <li> remove the root (A[1], the smallest element) from the heap, and reject it <li> replace it with the new element (A[1]:= x) <li> now, restore the heap condition: <ul> <li> if x is less than or equal to both of its children, you're done <li> otherwise, swap x with the smallest child <li> repeat the test&swap at each new position until the heap condition is met </ul> </ul> </ul> <p>Basically, this will cause any replacement element to "filter up" the tree until it achieves its natural place. This will take at most n=log2(N) steps, which is as good as you can get. Also, the implicit form of the tree allows a very fast implementation; existing bounded-priority-queue libraries will most likely use an implicit heap.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload