• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • Cascade Heap: Towards Time-Optimal Extractions
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2028
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
September 11, 2026
How to Assess Students Knowledge in the Age of AI
A researcher at HSE University has proposed a flowchart to help lecturers decide how to assess students who use artificial intelligence. It shows where the use of AI should be restricted and where it can be incorporated into the learning process. The article has been published in IT Professional.
September 9, 2026
‘Balkan Hospitality Opens Doors: Studying Dialects on the Verge of Extinction
You cannot study spoken dialects from books. Instead, you need to go to a village, seek out its elders, and earn the trust of local residents before you can record hours of spontaneous stories. This is how Natalia Muravleva, Associate Professor at the Faculty of Humanities, conducts her research. Her internship in Serbia continued her long-standing study of dialects spoken by Macedonian settlers. In this interview, she discusses how diaspora cultural centres help researchers reach informants, why native speakers need to be interviewed only in their own language (otherwise, as she puts it, they may 'break'), and how a single field season helped her finalise her monograph. She also shares warm memories of autumn in Belgrade and of colleagues with whom grammar can be discussed in three languages at once.
September 9, 2026
Scientists Train Neural Network to Generate Process Plans from 3D Models
Researchers at the HSE FCS AI and Digital Science Institute have developed CAD2TechSpec, a framework that converts 3D models of mechanical parts into machining process plans—step-by-step instructions for machine tools. The solution aims to reduce the time required for the design and preparation of technical process documentation in mechanical engineering, aircraft manufacturing, and other high-tech industries. The study findings have been published in PeerJ Computer Science.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Cascade Heap: Towards Time-Optimal Extractions

Theory of Computing Systems. 2019. Vol. 63. No. 4. P. 637–646.
Babenko M. A., Kolesnichenko I., Smirnov I.

Heaps are well-studied fundamental data structures, having myriads of applications, both theoretical and practical. We consider the problem of designing a heap with an “optimal” extract-min operation. Assuming an arbitrary linear ordering of keys, a heap with n elements typically takes O(log n) time to extract the minimum. Extracting all elements faster is impossible as this would violate the Ω (nlog n) bound for comparison-based sorting. It is known, however, that is takes only O(n+ klog k) time to sort just k smallest elements out of n given, which prompts that there might be a faster heap, whose extract-min performance depends on the number of elements extracted so far. In this paper we show that this is indeed the case. We present a version of heap that performs insert in O(1) time and takes only O(log ∗ n+ log k) time to carry out the k-th extraction (where log ∗ denotes the iterated logarithm). All the above bounds are worst-case. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

Research target: Computer Science
Language: English
DOI
Text on another site
Keywords: computer sciencedata structureslinear orderHeaps
Similar publications
What Do Text-to-Image Models Know About the Languages of the World?
Фирсанова В. И., Journal of Mathematical Sciences 2024 Vol. 285 No. 1 P. 112–125
Text-to-image models use user-generated prompts to produce images. Such text-to-image models as DALL-E 2, Imagen, Stable Diffusion, and Midjourney can generate photorealistic or similar to human-drawn images. Apart from imitating human art, large text-to-image models have learned to produce combinations of pixels reminiscent of captions in natural languages. For example, a generated image might contain ...
Added: September 9, 2026
Разработка интерфейса виртуального ассистента преподавателя на основе технологий вызова функций и инженерии инструкций для больших языковых моделей
Фирсанова В. И., Человек: образ и сущность. Гуманитарные аспекты 2025 Vol. 2 No. 62 P. 203–214
Abstract. The paper highlights prompt engineering in academic setting to reduce plagiarism and increase students' interest. The research problem is the lack of a unified methodology for using artificial intelligence in education. The paper aims to create a generative artificial intelligence user interface, the Virtual Teaching Assistant. Teachers were interviewed, the first collection of presets ...
Added: September 9, 2026
Анализ согласованности голосования стран ЕАЭС и ОДКБ в ГА ООН с помощью иерархической кластеризации
Вохминцев И. В., Вестник международных организаций: образование, наука, новая экономика 2026 Т. 21 № 2
The EAEU and the CSTO are Russia’s principal regional international organisations. Understanding, assessing, and analysing the foreign-policy positions of the countries that belong to them is a matter of the state’s national interests. This determines the purpose of the study: to identify the level and the form of cohesion in the voting of EAEU and ...
Added: September 7, 2026
Pupillometry and autonomic nervous system responses to cognitive load and false feedback: an unsupervised machine learning approach
Alshanskaia E., Portnova G., Liaukovich K. et al., Frontiers in Neuroscience 2024 Vol. 18
Added: September 7, 2026
Oil Spill Segmentation in SAR Data Using ViT-UNet: Performance and Practical Insights
Зуенко Д. О., Trofimova E., Хайдарова И., IEEE Access 2026 Vol. 14 P. 121339–121357
Oil spill segmentation in Synthetic Aperture Radar (SAR) images is limited by noisy annotations in publicly available datasets and by architectural choices that interact with label quality in opposing directions. First, we introduce a manually refined version of the Deep-SAR Oil Spill (SOS) dataset, in which 36.25% of masks are corrected for false positives, missed ...
Added: September 7, 2026
Variational representation of weighted divergencies and error exponent function
Kelbert M., Statistics 2026 Vol. 60
We present variational representations for the weighted divergencies and exponential error function, and discuss implications for the statistical inference and entropic optimal transport. ...
Added: September 7, 2026
Scalable machine learning approach to disordered s-wave superconductors
Неверов В. Д., Красавин А. В., Vagov A. et al., Physical Review B: Condensed Matter and Materials Physics 2026 Vol. 113 P. 1–6
We develop a neural network approach to solve the self-consistent Bogoliubov-de Gennes equations in strongly disordered s-wave superconductors. The method accurately reproduces inhomogeneous gap distributions and generalizes to system sizes far larger than those used in training. It reduces computational scaling from O(N6 ) to O(N2), enabling quantitative analysis of percolation phenomena and the superconductor-insulator ...
Added: September 5, 2026
On the rate of Gaussian approximation for online linear regression problems
Sheshukova M., Durmus A., Khusainov M. et al., Statistics 2026 P. 1–25
In this paper, we consider the problem of Gaussian approximation for the online linear regression task. We derive the corresponding rates for the setting of a constant stepsize and study the explicit dependence of the convergence rate on the problem dimension d and quantities related to the design matrix. When the number of iterations n is known in advance, ...
Added: September 4, 2026
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence (UAI), PMLR Volume 337, 17-21 August 2026, KIT, Amsterdam, the Netherlands
Proceedings of Machine Learning Research , 2026.
Added: September 4, 2026
A unified frequency-domain framework for tilted slice localization and ischemic stroke detection
Khodadoust J., Kulikova S., Khodadoust F., Biomedical Signal Processing and Control 2027 Vol. 129 P. 111284–111284
Acute ischemic stroke (AIS) analysis from two-dimensional (2D) clinical imaging is hindered by uncontrolled slice tilt and geometric inconsistencies that violate the assumptions of pose-agnostic deep learning (DL) models. This paper proposes a unified geometry-aware, frequency-domain framework for tilted slice localization and ischemic stroke segmentation that explicitly decouples pose estimation from lesion analysis. The method ...
Added: September 2, 2026
Proceedings of the 2026 Fourth International Conference on Distributed Computing and High Performance Computing (DCHPC)
IEEE, 2026.
On behalf of the Organizing Committee, it is my great pleasure to extend a warm welcome to all participants of the Fourth International IEEE Conference on Distributed Computing and High-Performance Computing (DCHPC 2026), held in Tehran from May 10–11, 2026. This conference is jointly organized by the School of Computer Science at the Institute for Research in Fundamental Sciences (IPM) ...
Added: September 2, 2026
Discrete Markowitz Portfolio Optimization with Open-Source Classical and Quantum-Inspired Solvers: A Cross-Market Walk-Forward Study
S.M. Avdoshin, Patrushev K. A., Proceedings of the Institute for System Programming of the RAS 2026 Vol. 38 No. 4-2 P. 245–256
The cardinality-constrained Markowitz problem is NP-hard and traditionally solved with commercial MIQP solvers. Following the 2022 export restrictions that rendered both commercial MIQP software and cloud quantum platforms (IBM Quantum, D-Wave Leap) inaccessible from the Russian Federation, practitioners require open-source alternatives. This paper systematically compares three solver families for the discrete mean-variance problem: two open-source ...
Added: August 27, 2026
Benchmarking Synolitic Graphs for Autism Classification from Multisite Resting-State fMRI
Zaikin A., Vlasenko D., Zakharov D. et al., Diagnostics 2026 Vol. 16 No. 17 P. 1–15
Background/Objectives: Synolitic graphs (SGs) were developed for task-based fMRI, where edge weights encode the discriminative power of pairwise regional features; whether similar information can be recovered from resting-state data was untested. We benchmarked SGs for autism spectrum disorder (ASD) classification using the multisite ABIDE-I dataset (871 subjects: 403 subjects with ASD, 468 typical controls; 17 sites; CC200 atlas). Methods: Using ...
Added: August 27, 2026
Алгебра, теория чисел, дискретная геометрия и многомасштабное моделирование. Современные проблемы, приложения и проблемы истории. Материалы XXIV Международной конференции, посвящённой 110-летию со дня рождения академика Юрия Владимировича Линника и 110-летию со дня рождения профессора Андрея Борисовича Шидловского и 80-летию со дня рождения профессора Геннадия Ивановича Архипова
Тула: Тульский государственный педагогический университет им. Л.Н. Толстого, 2025.
Сборник содержит материалы, представленные на XXIV Международной конференции «Алгебра, теория чисел, дискретная геометрия и многомасштабное моделирование: современные проблемы, приложения и проблемы истории», посвящённой 110-летию со дня рождения академика Юрия Владимировича Линника и 110-летию со дня рождения профессора Андрея Борисовича Шидловского и 80-летию со дня рождения профессора Геннадия Ивановича Архипова. Материалы конференции будут полезны научным работникам, ...
Added: August 27, 2026
Characterizing the Scheduling Performance of 5G NR Base Stations Under Signaling and Data Traffic Constraints
Eduard Sopin, Nazarin A., Begishev V. et al., IEEE Transactions on Vehicular Technology 2026 Vol. 75 No. 6 P. 10995–11007
Aimed at rate-greedy applications having extreme requirements for the data rate at the air interface, 5G New Radio (NR) systems may experience problems when the number of user equipment (UE) in the coverage of the cell increases due to limited capacity of the physical downlink control channel (PDCCH).The aim of this study is to explore ...
Added: August 26, 2026
Генерация исходного кода с использованием больших языковых моделей: систематический обзор методологии Вайб-кодинг
Джонов А. Т., Avdoshin S. M., Информационные технологии 2026 Т. 32 № 8 С. 421–427
This systematic review presents an analysis of the "Vibe Coding" methodology — a contemporary approach to the iterative software development process using Large Language Models (LLMs). Code generation tools are transforming software development by enabling programmers to formulate tasks and describe the desired behavior of software in natural language, while LLMs generate source code corresponding ...
Added: August 25, 2026
RatanSunPy: A robust preprocessing pipeline for RATAN-600 solar radio observations data
Князева И., Лысов И. И., Курочкин Е. et al., Astronomy and Computing 2025 Vol. 51 P. 100918–0
The advancement of observational technologies and software for processing and visualizing spectro-polarimetric microwave data obtained with the RATAN-600 radio telescope opens new opportunities for studying the physical characteristics of solar plasma at the levels of the chromosphere and corona. These levels remain some difficult to detect in the ultraviolet and X-ray ranges. The development of ...
Added: December 10, 2024
Some properties of Büchi Arithmetics
Zapryagaev A., / Series arXiv "math". 2023.
Büchi arithmetics BA_n, n≥2, are extensions of Presburger arithmetic with an unary functional symbol V_n(x) denoting the largest power of n that divides x. A rank of a linear order is the minimal number of condensations required to reach a finite order. We show that linear orders of arbitrarily large finite rank can be interpreted in BA_n. We also prove that the extension ...
Added: October 25, 2023
Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems
Rubtsov A. A., Vyalyi M., , in: Descriptional Complexity of Formal Systems: 23rd IFIP WG 1.02 International Conference, DCFS 2021, Virtual Event, September 5, 2021, Proceedings.: Springer, 2021. P. 150–162.
Added: February 2, 2022
Proceedings of the Workshop on Mathematical Modeling and Scientific Computing: Focus on Complex Processes and Systems — dedicated to the memory of Nikolai Botkin (MMSC 2020)
CEUR Workshop Proceedings, 2020.
Added: November 18, 2021
Algorithms and Data Structures. WADS 2019. Lecture Notes in Computer Science
Springer, 2019.
16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, Proceedings ...
Added: October 26, 2021
Multi-dimensional Interpretations of Presburger Arithmetic in Itself
Pahomov F., Zapryagaev A., Journal of Logic and Computation 2020 Vol. 30 No. 8 P. 1681–1693
Presburger arithmetic is the true theory of natural numbers with addition. We study interpretations of Presburger arithmetic in itself. The main result of this paper is that all self-interpretations are definably isomorphic to the trivial one. Here we consider interpretations that might be multi-dimensional. We note that this resolves a conjecture by Visser (1998, An ...
Added: November 12, 2020
Proceedings 16th International Symposium, ISBRA 2020, Moscow, Russia, December 1–4, 2020. Lecture Notes in Computer Science
Springer Publishing Company, 2020.
This book constitutes the proceedings of the 16th International Symposium on Bioinformatics Research and Applications, ISBRA 2020, held in Moscow, Russia, in December 2020. The 23 full papers and 18 short papers presented in this book were carefully reviewed and selected from 131 submissions. They were organized in topical sections named: genome analysis; systems biology; computational ...
Added: November 3, 2020
Artificial Intelligence and Natural Language. AINL 2020. Communications in Computer and Information Science
Springer, 2020.
Added: September 8, 2020
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit