{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:59:35Z","timestamp":1740142775078,"version":"3.37.3"},"reference-count":11,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T00:00:00Z","timestamp":1707868800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"funder":[{"name":"Northrop Grumman Information Systems"},{"DOI":"10.13039\/100005014","name":"Northrop Grumman Corporation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100005014","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100009883","name":"California State University Dominguez Hills","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100009883","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,4,14]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>This paper completes analysis of the worst-case running time of $ {\\tt{Heapsort}}$ measured by the number of comparisons of keys performed while sorting. A derivation of an exact formula for the maximum number of comparisons of keys performed by $ {\\tt{Heapsort}} $ on any array of size $ N \\geq 2 $ is presented. It is equal to $$ \\begin{align}&amp; \\nonumber 2(N-1)\\lceil \\lg N \\rceil - 2 ^{\\lceil \\lg N \\rceil +1} - 2 s_2(N) - e_2(N) + \\min (\\lceil \\lg N \\rceil, 3) + 5 + c, \\end{align} $$ where $s_2(N)$ is the sum of digits of the binary representation of $N$, $e_2(N)$ is the exponent of $2$ in the $N$\u2019s prime factorization and $ c $ is a binary function on the set of positive integers defined by $$ \\begin{align}&amp; \\nonumber c = \\left\\{ \\begin{array}{@{}ll} 1 \\text{ if} \\; N \\leq 2 ^{\\lceil \\lg N \\rceil} - 4 \\\\[4pt] 0 \\text{ otherwise}. \\end{array} \\right. \\end{align} $$ The above formula allows for deciding, in $ O(N \\log N) $ time, if any given $ N $-element array is a worst-case array for $ {\\tt{Heapsort}} $. Its proof yields an algorithm for construction, in $ O(N \\log N) $ time, of worst-case arrays of arbitrary sizes $ N \\geq 2 $ for $ {\\tt{Heapsort}} $.<\/jats:p>","DOI":"10.1093\/comjnl\/bxad007","type":"journal-article","created":{"date-parts":[[2024,2,17]],"date-time":"2024-02-17T01:47:00Z","timestamp":1708134420000},"page":"812-824","source":"Crossref","is-referenced-by-count":0,"title":["Worst-Case Analysis of Heapsort, Exactly"],"prefix":"10.1093","volume":"67","author":[{"given":"Marek A","family":"Suchenek","sequence":"first","affiliation":[{"name":"Department of Computer Science , California State University Dominguez Hills, 1000 E. Victoria St., Carson, CA 90747, USA. URL: http:\/\/csc.csudh.edu\/suchenek\/"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2024,2,14]]},"reference":[{"key":"2024041716571536900_ref1","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","article-title":"Algorithm 232: heapsort","volume":"7","author":"Williams","year":"1964","journal-title":"Commun. ACM"},{"volume-title":"The Art of Computer Programming","year":"1997","author":"Knuth","key":"2024041716571536900_ref2"},{"key":"2024041716571536900_ref3","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1006\/jagm.1993.1031","article-title":"The analysis of heapsort","volume":"15","author":"Schaffer","year":"1993","journal-title":"J. Algorithm."},{"volume-title":"A worst case analysis of heap-sort, Technical Report 018","year":"1979","author":"Kruskal","key":"2024041716571536900_ref4"},{"key":"2024041716571536900_ref5","doi-asserted-by":"crossref","first-page":"75","DOI":"10.3233\/FI-2012-751","article-title":"Elementary yet precise worst-case analysis of Floyd\u2019s heap-construction program","volume":"120","author":"Suchenek","year":"2012","journal-title":"Fundam. Inform."},{"key":"2024041716571536900_ref6","article-title":"A complete worst-case analysis of heapsort with experimental verifcation of its results (MS)","volume-title":"arXiv","author":"Suchenek","year":"2015"},{"volume-title":"Hereditary worst-case heaps","year":"2014","author":"Suchenek","key":"2024041716571536900_ref7"},{"key":"2024041716571536900_ref8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic Combinatorics","author":"Flajolet","year":"2009"},{"volume-title":"Introduction to Algorithms","year":"2009","author":"Cormen","key":"2024041716571536900_ref9"},{"volume-title":"Heapsort in Java","author":"WWW","key":"2024041716571536900_ref10"},{"key":"2024041716571536900_ref11","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/355588.365103","article-title":"Algorithm 245: Treesort 3","volume":"7","author":"Floyd","year":"1964","journal-title":"Commun. ACM"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/67\/3\/812\/57231635\/bxad007.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/67\/3\/812\/57231635\/bxad007.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,17]],"date-time":"2024-04-17T19:58:58Z","timestamp":1713383938000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/67\/3\/812\/7606364"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,14]]},"references-count":11,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2024,2,14]]},"published-print":{"date-parts":[[2024,4,14]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxad007","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2024,3]]},"published":{"date-parts":[[2024,2,14]]}}}