Email Gateway (Aug 22 2022 at 19:59): Email Gateway (Aug 22 2022 at 19:59):From: Tobias Nipkow <nipkow@in.tum.de>
Binary Heaps for IMP2
Simon Griebel
In this submission array-based binary minimum heaps are formalized. The
correctness of the following heap operations is proved: insert, get-min,
delete-min and make-heap. These are then used to verify an in-place heapsort.
The formalization is based on IMP2, an imperative program verification framework
implemented in Isabelle/HOL. The verified heap functions are iterative versions
of the partly recursive functions found in "Algorithms and Data Structures – The
Basic Toolbox" by K. Mehlhorn and P. Sanders and "Introduction to Algorithms" by
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein.
https://www.isa-afp.org/entries/IMP2_Binary_Heap.html
Enjoy!
smime.p7s
Last updated: Nov 04 2025 at 04:25 UTC