Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
In-place heap construction with optimized comparisons, moves, and cache misses
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Faculty 3-Mathematics and Computer Science, University of Bremen.
Department of Computer Science, University of Copenhagen.
Department of Computer Science, University of Copenhagen.
2012 (English)In: Mathematical foundations of computer science 2012: 37th international symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012 : proceedings / [ed] Branislav Rovan; Vladimiro Sassone ; Peter Widmayer, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2012, p. 259-270Conference paper, Published paper (Refereed)
Abstract [en]

We show how to build a binary heap in-place in linear time by performing ~ 1.625n element comparisons, at most ~ 2.125n element moves, and ~ n/B cache misses, where n is the size of the input array, B the capacity of the cache line, and ~ f(n) approaches f(n) as n grows. The same bound for element comparisons was derived and conjectured to be optimal by Gonnet and Munro; however, their procedure requires Θ(n) pointers and does not have optimal cache behaviour. Our main idea is to mimic the Gonnet-Munro algorithm by converting a navigation pile into a binary heap. To construct a binary heap in-place, we use this algorithm to build bottom heaps of size and adjust the heap order at the upper levels using Floyd's sift-down procedure. On another frontier, we compare different heap-construction alternatives in practice.

Place, publisher, year, edition, pages
Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2012. p. 259-270
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 7464
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-27310DOI: 10.1007/978-3-642-32589-2_25Scopus ID: 2-s2.0-84864976736Local ID: 0b993c78-df53-4868-92c0-a861554a87a6ISBN: 9783642325885 (print)OAI: oai:DiVA.org:ltu-27310DiVA, id: diva2:1000493
Conference
International Symposium on Mathematical Foundations of Computer Science : 27/08/2012 - 31/08/2012
Note
Validerad; 2012; 20120827 (andbra)Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2018-07-10Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Chen, Jingsen

Search in DiVA

By author/editor
Chen, Jingsen
By organisation
Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 242 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf