Copy the page URI to the clipboard
Kent, Carmel; Lewenstein, M. and Sheinwald, D.
(2012).
DOI: https://doi.org/10.1016/j.tcs.2011.12.001
Abstract
On-demand string sorting is the problem of preprocessing a set of strings to allow subsequent queries for finding the k lexicographically smallest strings (and afterward the next k etc.) This on-demand variant strongly resembles the search engine queries which give you the best k-ranked pages recurringly.
We present a data structure that supports this in O (n) preprocessing time, where n is the number of strings, and answer queries in O (log n) time. There is also a cost of O (N) time amortized over all operations, where N is the total length of the strings.
Our data structure is a heap of strings, which supports heapify and delete-mins. As it turns out, implementing a full heap with all operations is not that simple. For the sake of completeness, we propose a heap with full operations based on balanced indexing trees that supports the heap operations in optimal times.