{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T07:43:28Z","timestamp":1648885408366},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1994,6]]},"abstract":"<jats:p> In this paper, we introduce a new variant of implicit heaps, called relaxed inorder heaps. The structure is semi-implicit due to the use of 1 extra bit per node to maintain heap order and the allowance of some systematically controlled extra space. We show that relaxed inorder heaps are asymptotically more efficient than other known variants of implicit heaps. In particular, relaxed inorder heaps are especially efficient for heap merging and splitting operations, which are known to be problematic operations for implicit heaps. <\/jats:p><jats:p> Using amortized analysis, we derive several improved time bounds. Heap creation can be done in O(n) comparisons and node movements. Finding the minimum node and node insertion can each be done in O(1) comparisons and node movements. Key updating and node deletion can each be done in O(log n) comparisons and node movements. As for merging, we show that O(1) comparisons and 2k+O(1) node movements are sufficient for merging two heaps of sizes n and k. For splitting, we show that O(log n) comparisons and 1.5k+O(log n) node movements are sufficient for splitting an n-node implicit heap into two heaps of sizes k and n\u2212k. The amount of extra space in a relaxed inorder heap is O(log n) if splitting does not occur, and O(n) otherwise. <\/jats:p><jats:p> The significance of our results is that small sophistication in the structure of implicit heaps can produce large improvements in efficiency. We have implemented the algorithms for operations on relaxed inorder heaps. The simulation results strongly indicate that relaxed inorder heaps are practical, since the constant factors recorded for the heap operations are all very small. <\/jats:p>","DOI":"10.1142\/s0129054194000074","type":"journal-article","created":{"date-parts":[[2004,11,19]],"date-time":"2004-11-19T02:21:13Z","timestamp":1100830873000},"page":"111-128","source":"Crossref","is-referenced-by-count":0,"title":["RELAXED INORDER HEAPS"],"prefix":"10.1142","volume":"05","author":[{"given":"C.M.","family":"KHOONG","sequence":"first","affiliation":[{"name":"Information Technology Institute, National Computer Board, 71 Science Park Drive, Singapore  0511, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H.W.","family":"LEONG","sequence":"additional","affiliation":[{"name":"Department of Information Systems and Computer Science, National University of Singapore, Lower Kent Ridge Road, Singapore 0511, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054194000074","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:53:19Z","timestamp":1565139199000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054194000074"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,6]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1994,6]]}},"alternative-id":["10.1142\/S0129054194000074"],"URL":"https:\/\/doi.org\/10.1142\/s0129054194000074","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,6]]}}}