# Sorting tuples with respect to multiple criteria

Given $n$ rows with $k$ columns, is there a storage mechanism/data-structure and/or algorithm that enables dynamic restructuring such that I can get the top $t=\mathcal{O}(1)$ results efficiently?

### Example strategy 0

$$k_0 \le k_1 \le \cdots \le k_{n-2} \le k_{n-1}$$

### Example strategy 1

$$k_{n-1} \le k_{n-2} \le \cdots \le k_1 \le k_0$$

Given [ [0,1] [2,3] [1,2] ] strategy 0 returns: [ [0,1], [1,2] ], where $t=2$.

Restructuring with strategy 1 returns: [ [2,3], [1,2] ]. New strategies can be provided "at runtime".

Given a data-structure solution, here are the methods that it should expose:

• insert_row (*row) -> inserts a row of $k$ elements into the structure
• delete_row (*row) -> delete the precisely specified row from structure
• new_strategy(*k_prioritisation) -> rebalances the structure given the specified strategy
• top_rows() -> provides top rows after a strategy has been "installed". Number of rows to return is specified at compile time (as a source-code constant).

PS: Bonus points if you can enables strategies like $k_0 \le [\text{all other } k \text{ except } k_0]$, with embedded strategies of much the same.

• I don't understand your question. What is the input (including the runtime constraints), and what is the output? Your example can be solved using sorting in various ways. Feb 27 '15 at 4:27
• @YuvalFilmus Better now?
– Raphael
Mar 4 '15 at 12:27
• What do you mean by "the weights should propagate down"? What criteria should be used to determine which weights to change, and how? What do you mean by "conflicts are resolved through strict priorities"? Can you define what you mean by "optimal row"? Optimal in what sense? The problem does not seem to be well-specified. Before one can start thinking about an algorithm, the very first step is to make sure you have a precise specification of the algorithmic problem you want solved.
– D.W.
Mar 6 '15 at 11:47
• @Raphael, no, unfortunately, I still find it unclear (however I can no longer vote to put it on hold until it is clarified, now that it's been re-opened). The question still does not describe what is the desired output and what are the running time constraints (as Yuval suggested).
– D.W.
Mar 6 '15 at 11:48
• @D.W. I find it clear now; in essence, the goal is to sort w.r.t. an order relation specified by "in column x, smaller/larger is better". There is no runtime restriction, but there does not have to be one.
– Raphael
Mar 6 '15 at 17:45