Algorithm to maintain a sorted (numerically) list of numbers/doubles-CodePudding

Say I am generating random numbers using Math.random(), maybe 1000 of them, and I want to have them in ascending order (at all times). Is there a data structure of some variety that can keep them sorted the whole time, without ever having to call a sort routine? The only thing I can think of is a heap? but there might be a better way.

Some code will help:

const numContainer = {};

for(let i = 0; i < 1000; i  ){
   const r = Math.random();  // I generate a new RV
   numContainer[r] = {r};   // I want to store it in order, but this isn't helping :-)
}

clearly the above is not really going to maintain any numerical order for the keys etc. I am looking to have them be sorted as I go.

CodePudding user response：

You can generate your numbers in sorted order in linear time. The paper describing how to do this is: Generating Sorted Lists of Random Numbers by Bentley & Saxe

https://pdfs.semanticscholar.org/2dbc/4e3f10b88832fcd5fb88d34b8fb0b0102000.pdf

/**
 * Generate an sorted list of random numbers sorted from 1 to 0, given the size
 * of the list being requested.
 * 
 * This is an implementation of an algorithm developed by Bentley and Sax, and
 * published in in ACM Transactions on Mathematical Software (v6, iss3, 1980) on
 * 'Generating Sorted Lists of Random Numbers'.
 */
public class SortedRandomDoubleGenerator {
    private long       valsFound;
    private double     curMax;
    private final long numVals;

    /**
     * Instantiate a generator of sorted random doubles.
     * 
     * @param numVals the size of the list of sorted random doubles to be
     *        generated
     */
    public SortedRandomDoubleGenerator(long numVals) {
        curMax = 1.0;
        valsFound = 0;
        this.numVals = numVals;
    }

    /**
     * @return the next random number, in descending order.
     */
    public double getNext() {
        curMax = curMax
                * Math.pow(Math.E, Math.log(RandomNumbers.nextDouble())
                        / (numVals - valsFound));
        valsFound  ;
        return curMax;
    }
}

CodePudding user response：

A heap is only partially ordered: nodes are only ordered with respect to their parents. Perhaps you were thinking of a binary search tree.

A typical implementation of a self-balanced binary search tree is the red-black tree, and it can be implemented using an array with some empty spaces (at most n-2 if you have n elements).

The whole operation will still run in the same amount of time, complexity-wise, as just populating an array and sorting it at the end, although I would bet the latter option is almost always faster.

CodePudding user response：

You did not specify any constraint on the data structure, so an elementary solution is an array, combined with insertion of the new elements.

Or a linked list.

Or a binary search tree.

But not a heap !