JUCS - Journal of Universal Computer Science 6(2): 240-255, doi: 10.3217/jucs-006-02-0240
Potential-Function_Based Analysis of an Off-Line Heap Construction Algorithm
expand article infoAlan Roberts‡, Antonios Symvonis‡
‡ Department of Computer Science, University of Sydney, Australia

Corresponding author: Alan Roberts ( alanr@cs.usyd.edu.au )

© Alan Roberts, Antonios Symvonis.
This article is freely available under the J.UCS Open Content License.
Citation: Roberts A, Symvonis A (2000) Potential-Function_Based Analysis of an Off-Line Heap Construction Algorithm. JUCS - Journal of Universal Computer Science 6(2): 240-255. https://doi.org/10.3217/jucs-006-02-0240
Open Access
Abstract
In this paper we examine the problem of heap construction on a rooted tree T from a packet routing perspective. Each node of T initially contains a packet which has a key-value associated with it. The aim of the heap construction algorithm is to route the packets along the edges of the tree so that, at the end of the routing, the tree is heap ordered with respect to the key values associated with the packets. We consider the case where the routing is performed according to the matching model and we present and analyse an off-line algorithm that heap orders the tree within 2h(T) routing steps, where h(T ) is the height of tree T. The main contribution of the paper is the novel analysis of the algorithm based on potential functions. It is our belief that potential functions will be the main vehicle in analysing fast non-recursive routing algorithms.
Keywords
heap construction, matching routing model, off-line/on-line algorithms, packet routing, potential functions