An Algorithm for k-insertion into a Binary Heap

Abstract

In this thesis, we present an algorithm for k-insertion into a binary heap running in worst-case time O(k+log(k)·log(n+k)), improving the standard k-insertion algorithm for binary heaps in terms of worst-case running time. The algorithm combines two routines called Heapify and Walk down. We assess the performance of the algorithm in theory and practice and compare it to some well-known k-insertion methods. We do this by implementing the algorithms and measuring and comparing their running times on different datasets. Through practical tests, we conclude that the algorithm performs better than the standard k-insertion algorithm on worst-case input while being slightly slower on randomized input. We, therefore, conclude that it can be better in real-world applications.